Quantum reading group

If you are not on the mailing list, click here.

Fall 2009

The topic for this Fall is Hamiltonian complexity. See this document for some initial references. We plan to start by discussing the QMA-completeness results for the local Hamiltonian problem, before turning to properties of the ground state of gapped Hamiltoninans.

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.

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.

Another series of papers deals with the complexity of local Hamiltonian problems

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.

Finally, a few keywords for properties of ground states we might explore (basically these are results that keep showing up, and that I'd like to understand!)

Area law
Lieb-Robinson bound
Lieb-Shultz Mattis theorem