Quantum Computation and Complexity course

15 July 2016 Lectured at the 2016 Autrans summer school on Stochastic Methods in Quantum Mechanics. The notes are adapted from the first half my Advanced Quantum Information Theory course.

The Arora-Barak book gives an excellent, modern treatment of the theory of computation and complexity, going far beyond what's covered in this short course. The proof of Kitaev's theorem closely follows the original from the Kitaev-Schen-Vyalyi book. The other references are review papers on Hamiltonian complexity, which may also be of interest.

The following is a selective and incomplete list of links to the arXiv versions of papers that proved key results in Hamiltonian Complexity post-Kitaev. (These are the papers I mentioned in the brief survey at the very end of the lecture course.)

QMA-completeness with stronger locality conditions, and related results

Proves QMA-completeness of the k-local Hamiltonian problem for $$k=3$$.

Proves QMA-completeness of the k-local Hamiltonian problem for $$k=2$$. Introduces the perturbation gadget technique.

Proves QMA-completeness of the k-local Hamiltonian problem for nearest-neighbour interactions ($$k=2$$) between qubits on a 2D square lattice. (Interactions are not translationally-invariant). Developes stronger perturbation gadget techniques.

Proves QMA-completeness of the k-local Hamiltonian problem for nearest-neighbour interactions ($$k=2$$) bewteen qu$$d$$its on a line, for $$d=13$$. (Interactions are not translationally-invariant.) Later improved to $$d=8$$ by Nagaj et al.

Proves QMAEXP-completeness of the local Hamiltonian problem for translationally-invariant, nearest-neighbour interactions ($$k=2$$) between qu$$d$$its on a line, with a fixed Hamiltonian and $$d\approx 10^6$$. (The only remaining parameter in the problem is the length of the chain!)

Proves the Gottesman-Irani result for $$d=42$$.

A computability theory rather than a complexity theory result. Proves undecidability of the spectral gap problem for translationally-invariant, nearest-neighbour interactions between qu$$d$$its on a 2D square lattice in the thermodynamic limit, with $$d\approx 10^100$$ (or maybe a bit smaller). Makes key use of ideas from the Gottesman-Irani result, amongst (many) other ingredients.

QMA-completeness with restricted types of interaction, and related results

Proves QMA-completeness of the 2-local Hamiltonian problem for qubit Hamiltonians containing only XZ, X and Z interactions (amongst other similar results).

Proves a complete complexity classification for the k-local Hamiltonian problem with 2-qubit interactions, according to the type of interactions allowed. (A quantum analogue of Schaeffer's dichotomy theorem for boolean constraint satisfaction problems.)

Tightens the Cubitt-Montanaro classification by proving one of the four classes in the classification is equal to stoqMA (a highly non-trivial improvement!), amongst other results. 