Quantum reading group

Fall 2009

We meet on Fridays, 1pm, in 410 HMB

• September 18th, Anand will present Kitaev's proof of the QMA-completness of the local Hamiltonian problems (this can apparently only be found in Kitaev's book), and improvements by Kitaev, Kempe and Regev (paper).
• September 23rd, Siu Man talked about the perturbation technique for the 2-local Hamiltonian.
• October 16th and 23rd, Piyush on the paper Perturbative Gadgets at Arbitrary Orders, which shows how perturbation theory can be used to transform any k-local Hamiltonian in a 2-local one, albeit with a large blow-up in norm.
• October 30th, Thomas on The complexity of quantum spin systems on a two-dimensional square lattice, which establishes that finding ground states of 2-local nearest-neighbor Hamiltonians on a 2D square lattice is QMA-complete.
• November 6th. Thomas finishes on 2D Hamiltonians, and Anand starts presenting the paper Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians , which gives a new way of constructing a 1-qubit clock for Hamiltonian quantum computing.
• November 13th. Anand continues his presentation of the paper by Nagaj.
• November 20th and 27th: no reading group due to BATS and Thanksgiving.
• December 1st. Anupam presents The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems , by D. Gottesman and S. Irani.
• December 4th. Daniel presents a Simple proof of equivalence between adiabatic quantum computation and the circuit model, by D. Lidar.
• December 11th. Last session of the semester: review, questions, perspective.

Some notes that we wrote up, covering some of the reading group talks:

• Notes on the k-to-2 perturbative gadgets by Jordan and Fahri
• Notes on the paper on 2D Hamiltonians, by Oliveira and Terhal.
• Notes on the Railroad-switch construction by Nagaj.
• Notes on the complexity of tiling problems.

Here is a suggestion of initial readings related to representations for the ground states of local Hamiltonians:

• A good starting point is the survey Matrix Product State Representations which introduces Matrix Product States, and gives some examples and properties. It also has lots of references of interest.
• The original short paper Efficient Simulation of one-dimensional quantum many-body systems by Vidal also gives a short, technical introduction, perhaps more easily understandable for computer scientists.
• To familiarize ourselves with the physics vocabulary, and learn some examples that will keep showing up, it would be worth studying the following examples: the AKLT model (see also this paper for a generalization - note that we are only interested in writing down these models in a language we understand, and maybe re-deriving some of their key properties), and the cluster state, for which this review could be a good starting point.
• A Ph.D. thesis on entanglement in gapped Hamiltonians, which could also provide a good introduction.

• There is a series of papers on quantum k-SAT by Bravyi, who also studies the quantum satisfiability threshold.
• Some QMA-completeness results for various classes of spin systems: here and here.

• Area law
• Lieb-Robinson bound
• Lieb-Shultz Mattis theorem