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.
Slides for some of the lectures will be posted in the official course site (menu: files).
Course outline (with references and links):
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.
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]
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.
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.
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.
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).
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.