This is a companion site to the short course "Introduction to quantum simulation and simulability", given at ICTP-SAIFR/IFT-UNESP between October 15-19, 2018. Below you'll find a summary of the contents, and links to papers and other sources which are relevant to the course.

Lecturers:

• Leandro Aolita (IF-UFRJ, Rio de Janeiro & ICTP/SAIFR, São Paulo)
• Daniel J. Brod (UFF, Niterói)
• Ernesto F. Galvão (UFF, Niterói)

Slides for some of the lectures will be posted in the official course site (menu: files).

Course outline (with references and links):

Lecture 1 - General overview of the field (Daniel Brod)

1. Historical timeline of quantum computing, in three stages: (i) classical computing, (ii) quantum computing theory and (iii) quantum computing experiments. You can find a very complete timeline of quantum computing here. Of course, the standard textbook for quantum computing in general is Nielsen and Chuang's, but good alternatives are Mermin's and Rieffel and Polak's textbooks.
2. Very brief overview of Quantum Mechanics in the language of Quantum Computing;
   • P1: States as qubits;
   • P2: Discrete-time transformations;
   • P3: Measurements
   • P4: Tensor product for system composition;
3. Information-theoretic-flavored consequences of P1-P4.
   • Entanglement;
   • No-cloning theorem;
   • Teleportation;
   • Superdense coding;

Lecture 2: Quantum circuits and algorithms (Ernesto F. Galvão)

Basics of circuit model: input, unitaries (and their graphical notation), measurement. Single-qubit gates are rotations of the Bloch sphere. Sketch of proof that the gate-set {H, T, CNOT} is (approximately) universal. Approximating unitaries using the Solovay-Kitaev algorithm [Dawson/Nielsen review paper].

Other universal sets of gates: {Toffoli, H} (actually, any non-basis preserving single-qubit unitary serves the purpose, together with Toffoli - [Shi paper, Aharonov paper with a simpler proof of this]. This gate-set consists of orthogonal matrices, which operating in the computational basis will never result in states with complex coefficients. So it must be possible to quantum-compute efficiently with no need for complex numbers (on "rebits"=qubits with real amplitudes), and this is indeed the case [Rudolph/Grover paper, McKague paper].

The concept of encoded universality (see paper by Bacon et al.). Other (encoded) universal gate-sets:{matchgates, SWAP}. A single interaction is sufficient: gates from the exchange interaction [ Kempe et al. paper], {generic two-qubit unitary} [see paper by Childs et al.].

Certain unitaries require an exponential number of gates to implement. Complexity class BQP consists of problems solvable by poly(n)-sized circuits (check out this introductory lecture by Scott Aaronson on the main complexity classes relevant to us). The problem with allowing general, global output measurements.

Our first restricted computer: one with gates only from the Clifford group of unitaries. Defining the Pauli and the Clifford group: normalizer of the Pauli group. Efficient simulation using the Heisenberg picture (the Gottesman-Knill theorem - see Gottesman's introductory paper).

Sometimes we can "upgrade" the computational power of a restricted quantum computer. Example: Clifford computer + magic states (Bravyi/Kitaev paper).

On weak and strong probabilistic simulations of quantum computers - see this paper by van den Nest, or this other one about many variations over Clifford circuits.

Lecture 3: Physical states and the (convenient?) illusion of Hilbert space (Leandro)

Exponentially many classical states versus doubly exponentially many quantum ones. Definition of physical states: local Hamiltonian dynamics over Poly(N) time. All classical states are physical. All physical states can be simulated efficiently on a universal quantum computer [for the case of slowly-varying Hamiltonians (including Trotter formulas, see Seth Lloyd seminal paper and Nielsen and Chuang's book on Quantum Computation Chapter IV; for the most general case of time-varying Hamiltonians, see Poulin et al paper paper for the pure state case and the Kliesch et al paper paper for the mixed-state case (not discussed in class)].

Counting the number of physical states (epsilon-nets): the vast majority of states in Hilbert space are non-physical [see Poulin et al paper paper and Nielsen and Chuang's book on Quantum Computation Chapter IV for the counting argument].

Computational complexity as a new fundamental physical axiom [see for instance Aharonov & Vazirani paper for a recent computational perspective on the foundations of Quantum Mechanics; and (for the adventurers!) see Hayden & Harlow conjecture (perhaps together with its comment by Leo Susskind) for quantum computational complexity limitations as possible explanations black-hole information paradoxes]

Lecture 4 - Introduction to computational complexity theory (I) (Daniel Brod)

1. Turing machines.
2. Decision problems.
   • Definition;
   • Not the only type of problem, but many problems can be reduced to decision problems (e.g. factoring). Some can’t, such as sampling problems, which we will address later in the course;
   • Decision problems can be grouped into complexity classes.
3. Complexity class: P.
   • Definition.
   • Examples: The determinant.
4. Complexity class: NP.
   • Witness-based definition;
   • Examples: Factoring, travelling salesman, 3-coloring, 3SAT and k-Clique.
5. NP-hardness.
   • Definition.
   • Example of a reduction (3-SAT to k-clique)
   • The fact NP-hard problems exist is adds structure to complexity classes. If we had to prove that every NP problems is in P, one by one, it would be hopeless.
   • NP-completeness. There are thousands of these!
6. BPP and BQP.
7. Advertisements: For more on these complexity classes, there are many good resources. Two interesting non-textbooks are Lance Fortnow’s and Scott Aaronson's. The student interested in learning this subject in detail can look at Arora and Barak's textbook. There is also the complexity zoo, a website hosted at the University of Waterloo that serves as a compendium of (almost) all known complexity classes and the relations between them.

Lectures 5 and 8: Introduction to Measurement-based quantum computation (Ernesto F. Galvão)

Description of model: this is an excellent review by Josza, this part of my lecture was based on section 2.1 of this paper by McKague. These short, self-contained lecture notes by Jozsa provide the best overview of the model for novices. Step by step we'll build the ingredients for MBQC. Single-bit Z teleportation. Gate teleportation idea by Gottesman and Chuang, simplified here using the 1-bit Z teleportation circuit. Concatenating series of single-bit gate teleportations we can apply an arbitrary single-qubit gate using teleportation (I skipped discussion about corrections for CZ gates, which is similar). Discussion about how corrections work and what's needed from the classical control computer.

Entanglement resources for MBQC: defining graph states. Cluster states, 3-qubit DFT example, role of Z measurements. Other known universal resources for MBQC (Gross et al.'s paper). Simulability of linear 1D cluster.

Time-ordering in MBQC, parallelizing Clifford gates in MBQC. We've seen that this parallelization carries over to the circuit model when we translate the MBQC implementation back into circuits.

Experimental implementations: topological error correction using eight-photon cluster state, single-site addressing of cold neutral atoms in Mott-insulator state in an optical lattice, percolation-inspired approach to MBQC with faulty CZs.

MBQC as a toy model for quantum spacetime (paper by Raussendorf et al.). How time-travel appears in MBQC (my paper with Elham Kashefi and Raphael Dias da Silva).

The so-called measurement-based classical computation (paper by Hoban et al.) discusses MBQC implementations of IQP circuits. The gate commutativity (in the circuit model) translates to MBQC as non-adaptativity.

Where does the power of MBQC comes from? Due to the neat separation between classical and quantum resources, it must come from the correlations exhibited by measurements of the cluster state. The connection with non-locality and contextuality has been studied in a few papers, for example this paper by Hoban et al. (on the relation with non-locality tests) and this paper by Raussendorf (relating MBQC with quantum contextuality).

In this paper of mine we show that arbitrarily small violations of non-contextuality inequalities are sufficient for reliable evaluation of general Boolean functions. In this paper Howard et al. show that contextuality is necessary for computation in the model of magic state distillation and injection.

Lecture 6: The physical corner of Hilbert space I - Tensor networks (Leandro)

Matrix product states (MPS): Definition of MPSs. Tensor-network graphical notation. Properties: Poly-many parameters, exponential decay of correlations, efficient contractions and calculations of local observables, MPS => entanglement area law in 1D, local gapped parent Hamiltonians, etc.

Area law in any 1D => MPS: Canonical decomposition of MPSs and the efficient classical simulation of states with low long-range entanglement (successive Schmidt decomposition). Essentials about higher spatial-dimensional generalizations: projected entangled pairs (PEPS) and tree tensor networks.

The best two references here are the excellent review by Román Orus (recent and very introductory) and review by Verstraete et al (a bit less recent but in some senses more technical, specially conserning tensor networks as variational Ansatz for optimizations). The original derivation of the canonical form of an MPS (successive Schmidt decomposition) is in the seminal paper by Gifré Vidal, but it is also explained in the review by Orus.

Lecture 7 - Introduction to computational complexity theory (II) (Daniel Brod)

1. Computational complexity conjectures.
   • The general philosophy. Showing things are different is hard!
   • The complexity (petting) zoo.
   • Many results in complexity theory have the form “If X was true, unexpected things would happen to the complexity classes. Therefore X probably isn’t true”.
2. The polynomial hierarchy.
   • A generalization of NP.
   • Definition in terms of quantifiers.
   • Motivate it in terms of point 1 above, i.e.: we expect it to be infinite, so we will use its infinitude as evidence that certain problems are hard.
3. postBQP and postBPP.
   • As with PH, these guys are very high-in-the-sky, but motivated in terms of giving evidence about the real word.
   • Quantum and classical computers use post-selection very differently.
   • The computational power of postBQP has been discussed by Aaronson.
4. The postselection argument for quantum supremacy.
   • A recipe for hard-to-simulate systems. It can be used for bosonsampling and IQP (which Ernesto will mention), as well as a few others. The original argument for this recipe is due to Bremner, Shepherd and Jozsa.
5. #P
   • Counting problems and the Permanent;

Lecture 9: The physical corner of Hilbert space II - Neural-network quantum states (Leandro)

Boltzmann machines and unsupervised learning notions: A good reference for the classical case is the Hinton & Salakhutdinov paper (you can find its pdf open access in the the wikipedia post about RBMs).

Quantum RBM states as non-local state Ansatz. The ansatz was first introduced in quantum information in the seminal paper by Carleo and Troyer.

Quantum RBM states can more efficiently describe long-range entanglement (volume law). For the example of a sparse RBM state with linearly many hidden units see the paper by the Das Sarma group. Also, for the connection between RBMs and tensor networks, see also Chen et al paper and paper by the Cirac group.

For RBMs representing graph states and Deep RBMs describing universal quantum computations see the Gao & Duan paper.

Lecture 10: Intermediate models of quantum computation (Ernesto F. Galvão)

What's a restricted quantum computer, motivations. Simulability notions (reference to Jozsa course, weak and strong simulations). A general recipe for proving that a restricted model is hard to simulate (using postselection).

Description of some restricted models:

10.1 IQP: commuting quantum computations. Description, hardness proof, possible applications. Relevant papers:

* First Shepherd/Bremner paper, defining IQP.

* Bremner/Jozsa/Shepherd original paper with an argument that exact simulation of IQP would collapse the Polynomial Hierarchy.

* Recent paper by Bremner/Montanaro/Shepherd relating the hardness of simulation with other (supposedly) hard problems. This paper by Fujii and Morimae was the first the make the connection with partition functions of the Ising model.

* Some applications of circuits with diagonal unitaries - paper by Nataka and Murao.

10.2 DQC-1: description of the model, what it's good for, proofs that it's hard to simulate, presence (or absence) of entanglement and other correlations.

* Original paper by Knill, Laflamme (1998)

* For Jones polynomials (Shor, Jordan 2007)

* Small entanglement in this model: Datta, Flammia, Caves 2005

* Application: fidelity decay (David Poulin, Robin Blume-Kohout, Raymond Laflamme, Harold Ollivier 2003).

* Hardness of simulation proof (Fujii et al. 2014)

* Difficulty of simulation due to increasing Schmidt rank (Datta, Vidal 2007)

* Discord in DQC1: Datta, Shaji, Caves PRL 2008.

How much entanglement is necessary to quantum compute? For pure-state quantum computation, Jozsa and Linden showed some non-zero amount is necessary. In DQC1, not much bipartite entanglement is present across all bipartitions. But universal quantum computation also needs not require much bipartite entanglement, as shown by Van den Nest in this 2013 paper.

I probably won't have time to cover the intermediate models below, but check the links. Matchgates: description, relationship with non-interacting fermions, simulability. How to upgrade matchgates to universal quantum computation (Brod/Galvão papers, Brod/Childs paper). Compressed simulation scheme of Barbara Kraus. Permutational quantum computation (Jordan paper).

Lecture 11 - Demonstrating quantum advantage (I) (Daniel Brod)

1. Previously…
   • Recap of the definition of quantum advantage (or "supremacy"), motivation and definition.
   • Last time we saw an argument, but it doesn’t really apply to the real word due to experimental imperfections.
2. BosonSampling.
   • Definition and physical motivation.
     • We know that linear optics can perform quantum computation if we allow adaptive measurements, due to the KLM scheme. BosonSampling is essentially linear optics without measurement adaptation.
   • Permanent formula.
     • The Hong-OU-Mandel effect as an example.
     • Contrast with fermions.
     • Different argument for quantum advantage, based on the complexity of the Permanent.
     • Very basic outline of proof.
       • The original BosonSampling paper due to Aaronson and Arkhipov is this one. However, beware. This is a very long and complicated paper. For beginners to this field, I would definitely recommend skipping secs. 5, 7, 8 and 9.
3. Random quantum circuits.
   • Definition and physical motivation.
   • This is the approach used by Google, IBM and Intel! It has by now surpassed bosonsampling as main candidate for a demonstration of quantum advantage.

Lecture 12: Other approaches to quantum simulation (Ernesto F. Galvão)

Wikipedia article on rejection sampling. This paper by Neville et al. describes two algorithms for (approximately) simulating boson sampling: one is the rejection sampling scheme I discussed in the lecture (section III of the Appendix), and the other uses Markov chains to obtain a good approximation scheme. Both algorithms were ultimately superseded by the exact and very efficient algorithm by Clifford and Clifford.

This paper by Aaronson and Chen describes the algorithms inspired by path integrals that I talked about, which can be used to provide simulations for small-depth, general quantum circuits. This paper by Pednault et al. (IBM) describes large-scale simulations of random quantum circuits which use simulation schemes similar to those of Aaronson/Chen, on top of other tricks which I maybe didn't have had time to talk about. This (rival!) paper by a Google research group uses similar techniques, simulating for example a random circuit on a grid of 7x8=56 qubits with depth 27.

At the end of this lecture I managed to talk a bit about quantum devices with indefinite time ordering (called 2-SWITCHes). You can read about an experimental implementation here, and more about the theory here. I also told you how post-selected teleportation can be used to model time travel (closed time-like curves). This paper describes the model.

Lecture 13 - Demonstrating quantum advantage (II) (Daniel Brod)

1. Experimental considerations.
   • The arguments from the previous lecture were supposed to help a bit with experimental imperfections. It was a major step beyond the argument in L7! But Unfortunately it still falls short of actual experimental reality.
2. Linear-optical experiments.
3. Noisy Boson-Samplers
   • List of common issues experimentalists have to deal with.
   • Theoretical state-of-the-art.
   • Many open questions (with focus on losses).
4. BosonSampling Simulations vs experiments
   • Idea: classical simulations set the bar that quantum experiments must clear.
   • BosonSampling: State-of-the-art simulations and experiments. Still a big gap!
5. Random circuits.
   • The IT octagon - tech companies and universities are racing on the sides of classical simulation and quantum experiments.
6. References.
   • Since this lecture was more research-level, the references are not websites, links or textbooks, but rather research papers form the last few years. I have collected them in their proper locations in the slides, but I also list them here:
     • 1 - Aaronson and Arkhipov, Theo. Comput. 4, 143 (2013)
     • 2-5 - Broome et al, Science 339, 794 (2013); Crespi et al, Nat. Photon. 7, 545 (2013); Spring et al, Science 339, 798 (2013); Tillmann et al, Nat. Photon. 7, 540 (2013).
     • 6 - Wang et al, Phys. Rev. Lett. 120, 230502 (2018)
     • 7 - Kolthammer, credited at https://www.scottaaronson.com/blog/?p=1579
     • 8 - Lund et al, PRL 113, 100502 (2014)]
     • 9 - Bentivegna et al, Sci. Adv. 1, e1400255 (2015)
     • 10-12 - He et al, PRL 118, 190501 (2017); Loredo et al, PRL 118, 130503 (2017); Gazzano et al, Nat. Comm. 4, 1425 (2013).
     • 13 - Aaronson and Brod, PRA 93 012335 (2016)
     • 14 - Brod and Oszmaniec, New J. Phys. 20 092002 (2018)
     • 15 - Rahimi-Keshari, Ralph, Caves, PRX 6 021039 (2016)
     • 16 - Renema, Shchesnovich, Garcia-Patron arXiv:1809.01953 (2018)
     • 17 - Neville et al, Nat. Phys. 13, 1153 (2017)
     • 18 - Clifford and Clifford, Proc. 29th Annual ACM-SIAM SODA p.146 (2018)
     • 19 - Chen et al, arXiv:1805.01450
     • 20 - https://en.wikipedia.org/wiki/List_of_quantum_processors