Quantum Hamiltonian Complexity
Authors:
Preprint
Abstract
We survey the growing field of Quantum Hamiltonian Complexity, which includes the study of Quantum Constraint Satisfaction. In particular, our aim 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 paper: (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 88 references indexed in Scilit:
- Exponential Decay of Correlations Implies Area LawCommunications in Mathematical Physics, 2014
- Fault-tolerant quantum computation by anyonsAnnals of Physics, 2003
- 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
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- 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
- Zur Theorie der MetalleThe European Physical Journal A, 1931