Quantum Hamiltonian Complexity

S. Gharibian, Y. Huang, Z. Landau, S. Woo Shin, Foundations and Trends® in Theoretical Computer Science 10 (2015) 159–282.

Journal Article | Published | English
Author
; ; ;
Department
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.
Publishing Year
Journal Title
Foundations and Trends® in Theoretical Computer Science
Volume
10
Issue
3
Page
159-282
ISSN
LibreCat-ID

Cite this

Gharibian S, Huang Y, Landau Z, Woo Shin S. Quantum Hamiltonian Complexity. Foundations and Trends® in Theoretical Computer Science. 2015;10(3):159-282. doi:10.1561/0400000066
Gharibian, S., Huang, Y., Landau, Z., & Woo Shin, S. (2015). Quantum Hamiltonian Complexity. Foundations and Trends® in Theoretical Computer Science, 10(3), 159–282. https://doi.org/10.1561/0400000066
@article{Gharibian_Huang_Landau_Woo Shin_2015, title={Quantum Hamiltonian Complexity}, volume={10}, DOI={10.1561/0400000066}, number={3}, journal={Foundations and Trends® in Theoretical Computer Science}, author={Gharibian, Sevag and Huang, Yichen and Landau, Zeph and Woo Shin, Seung}, year={2015}, pages={159–282} }
Gharibian, Sevag, Yichen Huang, Zeph Landau, and Seung Woo Shin. “Quantum Hamiltonian Complexity.” Foundations and Trends® in Theoretical Computer Science 10, no. 3 (2015): 159–282. https://doi.org/10.1561/0400000066.
S. Gharibian, Y. Huang, Z. Landau, and S. Woo Shin, “Quantum Hamiltonian Complexity,” Foundations and Trends® in Theoretical Computer Science, vol. 10, no. 3, pp. 159–282, 2015.
Gharibian, Sevag, et al. “Quantum Hamiltonian Complexity.” Foundations and Trends® in Theoretical Computer Science, vol. 10, no. 3, 2015, pp. 159–282, doi:10.1561/0400000066.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 1401.3916

Search this title in

Google Scholar