Foundations and Trends® in Theoretical Computer Science > Vol 10 > Issue 3

Quantum Hamiltonian Complexity

Sevag Gharibian, Simons Institute for the Theory of Computing, University of California, Berkeley, USA, sgharibian@vcu.edu Yichen Huang, University of California, Berkeley, USA, yichenhuang@berkeley.edu Zeph Landau, Simons Institute for the Theory of Computing, University of California, Berkeley, USA, zeph.landau@gmail.com Seung Woo Shin, University of California, Berkeley, USA, seungwoo@eecs.berkeley.edu
 
Suggested Citation
Sevag Gharibian, Yichen Huang, Zeph Landau and Seung Woo Shin (2015), "Quantum Hamiltonian Complexity", Foundations and Trends® in Theoretical Computer Science: Vol. 10: No. 3, pp 159-282. http://dx.doi.org/10.1561/0400000066

Published: 13 Oct 2015
© 2015 S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin
 
Subjects
Computational complexity,  Design and analysis of algorithms,  Quantum Computation
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Preliminaries
3. Roadmap and Organization
4. A Brief History
5. Motivations From Physics
6. Physics Concepts in Greater Depth
7. Reviews of Selected Results
Acknowledgments
References

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.

DOI:10.1561/0400000066
ISBN: 978-1-68083-006-4
138 pp. $90.00
Buy book
 
ISBN: 978-1-68083-007-1
138 pp. $125.00
Buy E-book
Table of contents:
1. Introduction
2. Preliminaries
3. Roadmap and Organization
4. A Brief History
5. Motivations From Physics
6. Physics Concepts in Greater Depth
7. Reviews of Selected Results
Acknowledgments
References

Quantum Hamiltonian Complexity

Constraint satisfaction problems are a central pillar of modern computational complexity theory. This monograph provides an introduction to the rapidly growing field of Quantum Hamiltonian Complexity (QHC), 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.

Quantum Hamiltonian Complexity provides the reader with 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, it includes the following: (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, it provides a novel information theoretic presentation of Bravyi’s polynomial time algorithm for Quantum 2-SAT.

Quantum Hamiltonian Complexity reviews some of the most fundamental results in QHC and is an ideal reference for computer scientists with little or no background in quantum information.

Simons Institute Monographs are texts originating from scientific programs at the Simons Institute for the Theory of Computing at the University of California, Berkeley. For information on the Institute's mission and programs, visit http://simons.berkeley.edu.

 
TCS-066