[1]   Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe: The power of quantum systems on a line. Communications in Mathematical Physics, 287(1):41–65, 2009. Preliminary version in FOCS’07. [doi:10.1007/s00220-008-0710-3, arXiv:0705.4077]

[2]   Dorit Aharonov and Amnon Ta-Shma: Adiabatic quantum state generation and statistical zero knowledge. SIAM J. Comput., 37(1):47–82, 2007. Preliminary version in STOC’03. [doi:10.1137/060648829, arXiv:quant-ph/0301023]

[3]   Adam D. Bookatz: QMA-complete problems. Quantum Inf. Comput., 14(5-6):361–383, 2014. ACM DL. [arXiv:1212.6312]

[4]   Sergey Bravyi: Efficient algorithm for a quantum analogue of 2-SAT. Contemporary Mathematics, 536:33–48, 2011. [doi:10.1090/conm/536, arXiv:quant-ph/0602108]

[5]   Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, and Barbara M. Terhal: The complexity of stoquastic local Hamiltonian problems. Quantum Inf. Comput., 8(5):361–385, 2008. ACM DL. [arXiv:quant-ph/0606140]

[6]   Sergey Bravyi and Barbara Terhal: Complexity of stoquastic frustration-free Hamiltonians. SIAM J. Comput., 39(4):1462–1485, 2009. [doi:10.1137/08072689X, arXiv:0806.1746]

[7]   Nikolas P. Breuckmann and Barbara M. Terhal: Space-time circuit-to-Hamiltonian construction and its applications. Journal of Physics A, 47(19):195304, 2014. IOP Science. [arXiv:1311.6101]

[8]   Andrew M. Childs, David Gosset, and Zak Webb: Universal computation by multiparticle quantum walk. Science, 339(6121):791–794, 2013. [doi:10.1126/science.1229957, arXiv:1205.3782]

[9]   Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca: Quantum algorithms revisited. Proceedings of the Royal Society of London, Series A, 454(1969):339–354, 1998. [doi:10.1098/rspa.1998.0164, arXiv:quant-ph/9708016]

[10]   Toby S. Cubitt and Ashley Montanaro: Complexity classification of local Hamiltonian problems. Preprint, 2013-14. Extended abstract in FOCS’14. [arXiv:1311.3161]

[11]   Richard P. Feynman: Quantum mechanical computers. Optics News, 11(2):11–46, 1985. [doi:10.1364/ON.11.2.000011]

[12]   Matthew P. A. Fisher, Peter B. Weichman, G. Grinstein, and Daniel S. Fisher: Boson localization and the superfluid-insulator transition. Physical Review B, 40(1):546–570, 1989. [doi:10.1103/PhysRevB.40.546]

[13]   David Gosset and Daniel Nagaj: Quantum 3-SAT is QMA₁-complete. Preprint, 2013. Extended abstract in FOCS’13. [arXiv:1302.0290]

[14]   Daniel Gottesman and Sandy Irani: The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Theory of Computing, 9(2):31–116, 2013. Preliminary version in FOCS’09. [doi:10.4086/toc.2013.v009a002, arXiv:0905.2419]

[15]   Dominik Janzing: Spin-1/2 particles moving on a two-dimensional lattice with nearest-neighbor interactions can realize an autonomous quantum computer. Physical Review A, 75(1):012307, 2007. [doi:10.1103/PhysRevA.75.012307, arXiv:quant-ph/0506270]

[16]   Dominik Janzing and Pawel Wocjan: BQP-complete problems concerning mixing properties of classical random walks on sparse graphs, 2006. [arXiv:quant-ph/0610235]

[17]   Stephen P. Jordan and Edward Farhi: Perturbative gadgets at arbitrary orders. Physical Review A, 77(6):062329, 2008. [doi:10.1103/PhysRevA.77.062329, arXiv:0802.1874]

[18]   Stephen P. Jordan, David Gosset, and Peter J. Love: Quantum-Merlin-Arthur complete problems for stoquastic Hamiltonians and Markov matrices. Physical Review A, 81(3):032331, 2010. [doi:10.1103/PhysRevA.81.032331, arXiv:0905.4755]

[19]   Julia Kempe, Alexei Kitaev, and Oded Regev: The complexity of the local Hamiltonian problem. SIAM J. Comput., 35(5):1070–1097, 2006. Preliminary version in FSTTCS’04. [doi:10.1137/S0097539704445226, arXiv:quant-ph/0406180]

[20]   Julia Kempe and Oded Regev: 3-Local Hamiltonian is QMA-complete. Quantum Inf. Comput., 3(3):258–264, 2003. ACM DL. [arXiv:quant-ph/0302079]

[21]   Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi: Classical and Quantum Computation. Amer. Math. Soc., 2002. ACM DL.

[22]   Lev D. Landau and Evgenii M. Lifshitz: Quantum Mechanics: Non-Relativistic Theory. Pergamon Press, 1994.

[23]   Yi-Kai Liu, Matthias Christandl, and Frank Verstraete: Quantum computational complexity of the N-representability problem: QMA complete. Physical Review Letters, 98(11):110503, 2007. [doi:10.1103/PhysRevLett.98.110503, arXiv:quant-ph/0609125]

[24]   Chris Marriott and John Watrous: Quantum Arthur-Merlin games. Computational Complexity, 14(2):122–152, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0194-x, arXiv:cs/0506068]

[25]   Ari Mizel, Daniel A. Lidar, and Morgan Mitchell: Simple proof of equivalence between adiabatic quantum computation and the circuit model. Physical Review Letters, 99(7):070502, 2007. [doi:10.1103/PhysRevLett.99.070502]

[26]   Bojan Mohar: Eigenvalues, diameter, and mean distance in graphs. Graphs and Combinatorics, 7(1):53–64, 1991. [doi:10.1007/BF01789463]

[27]   Daniel Nagaj and Shay Mozes: New construction for a QMA complete three-local Hamiltonian. Journal of Mathematical Physics, 48(7):072104, 2007. [doi:10.1063/1.2748377, arXiv:quant-ph/0612113]

[28]   Roberto Oliveira and Barbara M. Terhal: The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Inf. Comput., 8(10):900–924, 2008. ACM DL. [arXiv:quant-ph/0504050]

[29]   Norbert Schuch and Frank Verstraete: Computational complexity of interacting electrons and fundamental limitations of density functional theory. Nature Physics, 5(10):732–735, 2009. [doi:10.1038/nphys1370, arXiv:0712.0483]

[30]   Tzu-Chieh Wei, Michele Mosca, and Ashwin Nayak: Interacting boson problems can be QMA hard. Physical Review Letters, 104(4):040501, 2010. [doi:10.1103/PhysRevLett.104.040501, arXiv:0905.3413]