Quantum Hamiltonian Complexity
- 13 October 2015
- journal article
- Published by Emerald Publishing in Foundations and Trends® in Theoretical Computer Science
- Vol. 10 (3) , 159-282
Abstract
Constraint satisfaction problems are a central pillar of modern computational complexity theory. This survey provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity, which includes the study of quantum constraint satisfaction problems. Over the past decade and a half, this field has witnessed fundamental breakthroughs, ranging from the establishment of a “Quantum Cook-Levin Theorem” to deep insights into the structure of 1D low-temperature quantum systems via so-called area laws. Our aim here is to provide a computer science-oriented introduction to the subject in order to help bridge the language barrier between computer scientists and physicists in the field. As such, we include the following in this survey: (1) The motivations and history of the field, (2) a glossary of condensed matter physics terms explained in computer-science friendly language, (3) overviews of central ideas from condensed matter physics, such as indistinguishable particles, mean field theory, tensor networks, and area laws, and (4) brief expositions of selected computer science-based results in the area. For example, as part of the latter, we provide a novel information theoretic presentation of Bravyi’s polynomial time algorithm for Quantum 2-SAT.Keywords
All Related Versions
This publication has 123 references indexed in Scilit:
- Finitely correlated states on quantum spin chainsCommunications in Mathematical Physics, 1992
- Valence bond ground states in isotropic quantum antiferromagnetsCommunications in Mathematical Physics, 1988
- A proof of part of Haldane's conjecture on spin chainsLetters in Mathematical Physics, 1986
- Quantum mechanical hamiltonian models of turing machinesJournal of Statistical Physics, 1982
- The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machinesJournal of Statistical Physics, 1980
- Reducibility among Combinatorial Problems1972
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are BinaryMathematical Logic Quarterly, 1967
- The Approximation of One Matrix by Another of Lower RankPsychometrika, 1936
- Die gegenw rtige Situation in der QuantenmechanikThe Science of Nature, 1935
- Zur Theorie der MetalleThe European Physical Journal A, 1931