---
_id: '8166'
abstract:
- lang: eng
  text: '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.'
article_type: review
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Yichen
  full_name: Huang, Yichen
  last_name: Huang
- first_name: Zeph
  full_name: Landau, Zeph
  last_name: Landau
- first_name: Seung
  full_name: Woo Shin, Seung
  last_name: Woo Shin
citation:
  ama: Gharibian S, Huang Y, Landau Z, Woo Shin S. Quantum Hamiltonian Complexity.
    <i>Foundations and Trends® in Theoretical Computer Science</i>. 2015;10(3):159-282.
    doi:<a href="https://doi.org/10.1561/0400000066">10.1561/0400000066</a>
  apa: Gharibian, S., Huang, Y., Landau, Z., &#38; Woo Shin, S. (2015). Quantum Hamiltonian
    Complexity. <i>Foundations and Trends® in Theoretical Computer Science</i>, <i>10</i>(3),
    159–282. <a href="https://doi.org/10.1561/0400000066">https://doi.org/10.1561/0400000066</a>
  bibtex: '@article{Gharibian_Huang_Landau_Woo Shin_2015, title={Quantum Hamiltonian
    Complexity}, volume={10}, DOI={<a href="https://doi.org/10.1561/0400000066">10.1561/0400000066</a>},
    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} }'
  chicago: 'Gharibian, Sevag, Yichen Huang, Zeph Landau, and Seung Woo Shin. “Quantum
    Hamiltonian Complexity.” <i>Foundations and Trends® in Theoretical Computer Science</i>
    10, no. 3 (2015): 159–282. <a href="https://doi.org/10.1561/0400000066">https://doi.org/10.1561/0400000066</a>.'
  ieee: 'S. Gharibian, Y. Huang, Z. Landau, and S. Woo Shin, “Quantum Hamiltonian
    Complexity,” <i>Foundations and Trends® in Theoretical Computer Science</i>, vol.
    10, no. 3, pp. 159–282, 2015, doi: <a href="https://doi.org/10.1561/0400000066">10.1561/0400000066</a>.'
  mla: Gharibian, Sevag, et al. “Quantum Hamiltonian Complexity.” <i>Foundations and
    Trends® in Theoretical Computer Science</i>, vol. 10, no. 3, 2015, pp. 159–282,
    doi:<a href="https://doi.org/10.1561/0400000066">10.1561/0400000066</a>.
  short: S. Gharibian, Y. Huang, Z. Landau, S. Woo Shin, Foundations and Trends® in
    Theoretical Computer Science 10 (2015) 159–282.
date_created: 2019-03-01T11:45:40Z
date_updated: 2023-02-28T11:02:21Z
department:
- _id: '623'
- _id: '7'
doi: 10.1561/0400000066
extern: '1'
external_id:
  arxiv:
  - '1401.3916'
intvolume: '        10'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1401.3916
oa: '1'
page: 159-282
publication: Foundations and Trends® in Theoretical Computer Science
publication_identifier:
  issn:
  - 1551-305X
publication_status: published
status: public
title: Quantum Hamiltonian Complexity
type: journal_article
user_id: '71541'
volume: 10
year: '2015'
...