Lecture course on quantum complexity theory, encompassing (a brief intro to) computability and complexity theory, complexity theory in quantum physics, and computability theory in physics. Lectured at the

- Lecture 1, Computation and Complexity video and lecture notes
- Lecture 2: Complexity in Physics video and lecture notes
- Lecture 3: Computability in Physics video and lecture notes

The lecture notes are copyright ©Toby Cubitt, and are licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

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 in the course closely follows the original from the Kitaev-Schen-Vyalyi book. The other references in this list are review papers on Hamiltonian complexity, which may also be of interest.

- Arora and Barak, "Complexity Theory: A Modern Approach, Cambridge University Press
- Kitaev, A., Shen, A., and Vyalyi M. "Classical and Quantum Computation", American Mathematical Society
- Aharonov, D. and Naveh, T. "Quantum NP - a Survey"
- Gharibian, S., Huang, Y. and Landau, Z. "Hamiltonian Complexity"

The following is a selective and incomplete list of links to the arXiv versions of papers that proved key results in Hamiltonian Complexity and Computability theory post-Kitaev.

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.

- D. Aharonov, D. Gottesman, S. Irani and Julia Kempe, "The power of quantum systems on a line" (2007)

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 QMA_{EXP}-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\).

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.

Shows that questions about the dynamics of a particle bouncing around a 3D box with linear and parabolic reflectors is undecidable.

Contains all the technical details and proofs for the above result, and more.

- TC, D. Perez-Garcia and M. Wolf, "Undecidability of the Spectral Gap (full version)" and (short version)" (2015)

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.

## Leave a comment

All comments are moderated. Clicking submit will open your email client and let you send your comment by email. By submitting your comment you agree to license the content under a Creative Commons Attribution-ShareAlike 4.0 International License.