---
_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.
Foundations and Trends® in Theoretical Computer Science. 2015;10(3):159-282.
doi:10.1561/0400000066
apa: 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
bibtex: '@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} }'
chicago: '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.'
ieee: '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, doi: 10.1561/0400000066.'
mla: 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.
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'
...
---
_id: '8168'
abstract:
- lang: eng
text: "Tensor networks are a central tool in condensed matter physics. In this paper,
we initiate the study of tensor network non-zero testing (TNZ): Given a tensor
network T, does T represent a non-zero vector? We show that TNZ is not in the
Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among
other results) that the special cases of TNZ on non-negative and injective tensor
networks are in NP. Using this, we make a simple observation: The commuting variant
of the MA-complete stoquastic k-SAT problem on D-dimensional qudits is in NP for
logarithmic k and constant D. This reveals the first class of quantum Hamiltonians
whose commuting variant is known to be in NP for all (1) logarithmic k, (2) constant
D, and (3) for arbitrary interaction graphs.\r\n"
article_type: original
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Zeph
full_name: Landau, Zeph
last_name: Landau
- first_name: Seung
full_name: Woo Shin, Seung
last_name: Woo Shin
- first_name: Guoming
full_name: Wang, Guoming
last_name: Wang
citation:
ama: Gharibian S, Landau Z, Woo Shin S, Wang G. Tensor network non-zero testing.
Quantum Information & Computation. 2015;15(9{\ & }10):885-899.
apa: Gharibian, S., Landau, Z., Woo Shin, S., & Wang, G. (2015). Tensor network
non-zero testing. Quantum Information & Computation, 15(9{\
& }10), 885–899.
bibtex: '@article{Gharibian_Landau_Woo Shin_Wang_2015, title={Tensor network non-zero
testing}, volume={15}, number={9{\ & }10}, journal={Quantum Information &
Computation}, author={Gharibian, Sevag and Landau, Zeph and Woo Shin, Seung and
Wang, Guoming}, year={2015}, pages={885–899} }'
chicago: 'Gharibian, Sevag, Zeph Landau, Seung Woo Shin, and Guoming Wang. “Tensor
Network Non-Zero Testing.” Quantum Information & Computation 15, no.
9{\ & }10 (2015): 885–99.'
ieee: S. Gharibian, Z. Landau, S. Woo Shin, and G. Wang, “Tensor network non-zero
testing,” Quantum Information & Computation, vol. 15, no. 9{\ &
}10, pp. 885–899, 2015.
mla: Gharibian, Sevag, et al. “Tensor Network Non-Zero Testing.” Quantum Information
& Computation, vol. 15, no. 9{\ & }10, 2015, pp. 885–99.
short: S. Gharibian, Z. Landau, S. Woo Shin, G. Wang, Quantum Information &
Computation 15 (2015) 885–899.
date_created: 2019-03-01T11:53:08Z
date_updated: 2023-02-28T11:02:35Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
arxiv:
- '1406.5279'
intvolume: ' 15'
issue: 9{\&}10
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1406.5279
oa: '1'
page: 885-899
publication: Quantum Information & Computation
publication_status: published
status: public
title: Tensor network non-zero testing
type: journal_article
user_id: '71541'
volume: 15
year: '2015'
...
---
_id: '42661'
author:
- first_name: 'Florian '
full_name: 'Hessing , Florian '
last_name: 'Hessing '
citation:
ama: Hessing F. Entwicklung einer Kennwertprognose für mit Blindnietelementen
elementar gefügte CFK- Mischbauverbindungen auf Basis von experimentellen Untersuchungen.;
2015.
apa: Hessing , F. (2015). Entwicklung einer Kennwertprognose für mit Blindnietelementen
elementar gefügte CFK- Mischbauverbindungen auf Basis von experimentellen Untersuchungen.
bibtex: '@book{Hessing _2015, title={Entwicklung einer Kennwertprognose für mit
Blindnietelementen elementar gefügte CFK- Mischbauverbindungen auf Basis von experimentellen
Untersuchungen}, author={Hessing , Florian }, year={2015} }'
chicago: Hessing , Florian . Entwicklung einer Kennwertprognose für mit Blindnietelementen
elementar gefügte CFK- Mischbauverbindungen auf Basis von experimentellen Untersuchungen,
2015.
ieee: F. Hessing , Entwicklung einer Kennwertprognose für mit Blindnietelementen
elementar gefügte CFK- Mischbauverbindungen auf Basis von experimentellen Untersuchungen.
2015.
mla: Hessing , Florian. Entwicklung einer Kennwertprognose für mit Blindnietelementen
elementar gefügte CFK- Mischbauverbindungen auf Basis von experimentellen Untersuchungen.
2015.
short: F. Hessing , Entwicklung einer Kennwertprognose für mit Blindnietelementen
elementar gefügte CFK- Mischbauverbindungen auf Basis von experimentellen Untersuchungen,
2015.
date_created: 2023-03-02T13:21:40Z
date_updated: 2023-03-02T13:21:47Z
department:
- _id: '157'
language:
- iso: ger
publication_identifier:
isbn:
- 978-3-8440-3396-0
status: public
title: Entwicklung einer Kennwertprognose für mit Blindnietelementen elementar gefügte
CFK- Mischbauverbindungen auf Basis von experimentellen Untersuchungen
type: dissertation
user_id: '15324'
year: '2015'
...
---
_id: '42663'
author:
- first_name: Frederik
full_name: Klokkers, Frederik
last_name: Klokkers
citation:
ama: Klokkers F. Charakterisierung des Trag- und Bruchverhaltens von Punktschweißverbindungen
aus hochfesten Mangan-Bor-Stählen.; 2015.
apa: Klokkers, F. (2015). Charakterisierung des Trag- und Bruchverhaltens von
Punktschweißverbindungen aus hochfesten Mangan-Bor-Stählen.
bibtex: '@book{Klokkers_2015, title={Charakterisierung des Trag- und Bruchverhaltens
von Punktschweißverbindungen aus hochfesten Mangan-Bor-Stählen}, author={Klokkers,
Frederik}, year={2015} }'
chicago: Klokkers, Frederik. Charakterisierung des Trag- und Bruchverhaltens
von Punktschweißverbindungen aus hochfesten Mangan-Bor-Stählen, 2015.
ieee: F. Klokkers, Charakterisierung des Trag- und Bruchverhaltens von Punktschweißverbindungen
aus hochfesten Mangan-Bor-Stählen. 2015.
mla: Klokkers, Frederik. Charakterisierung des Trag- und Bruchverhaltens von
Punktschweißverbindungen aus hochfesten Mangan-Bor-Stählen. 2015.
short: F. Klokkers, Charakterisierung des Trag- und Bruchverhaltens von Punktschweißverbindungen
aus hochfesten Mangan-Bor-Stählen, 2015.
date_created: 2023-03-02T13:28:18Z
date_updated: 2023-03-02T13:28:23Z
department:
- _id: '157'
language:
- iso: ger
publication_identifier:
isbn:
- 978-3-8440-3552-0
status: public
title: Charakterisierung des Trag- und Bruchverhaltens von Punktschweißverbindungen
aus hochfesten Mangan-Bor-Stählen
type: dissertation
user_id: '15324'
year: '2015'
...
---
_id: '42664'
author:
- first_name: Michael
full_name: Plass, Michael
last_name: Plass
citation:
ama: Plass M. Auswirkungen von fügeprozessbedingten Delaminationen auf die mechanischen
Eigenschaften von halbhohlstanzgenieteten Mischbauverbindungen aus Faserverbundkunststoffen
und Aluminium.; 2015.
apa: Plass, M. (2015). Auswirkungen von fügeprozessbedingten Delaminationen auf
die mechanischen Eigenschaften von halbhohlstanzgenieteten Mischbauverbindungen
aus Faserverbundkunststoffen und Aluminium.
bibtex: '@book{Plass_2015, title={Auswirkungen von fügeprozessbedingten Delaminationen
auf die mechanischen Eigenschaften von halbhohlstanzgenieteten Mischbauverbindungen
aus Faserverbundkunststoffen und Aluminium}, author={Plass, Michael}, year={2015}
}'
chicago: Plass, Michael. Auswirkungen von fügeprozessbedingten Delaminationen
auf die mechanischen Eigenschaften von halbhohlstanzgenieteten Mischbauverbindungen
aus Faserverbundkunststoffen und Aluminium, 2015.
ieee: M. Plass, Auswirkungen von fügeprozessbedingten Delaminationen auf die
mechanischen Eigenschaften von halbhohlstanzgenieteten Mischbauverbindungen aus
Faserverbundkunststoffen und Aluminium. 2015.
mla: Plass, Michael. Auswirkungen von fügeprozessbedingten Delaminationen auf
die mechanischen Eigenschaften von halbhohlstanzgenieteten Mischbauverbindungen
aus Faserverbundkunststoffen und Aluminium. 2015.
short: M. Plass, Auswirkungen von fügeprozessbedingten Delaminationen auf die mechanischen
Eigenschaften von halbhohlstanzgenieteten Mischbauverbindungen aus Faserverbundkunststoffen
und Aluminium, 2015.
date_created: 2023-03-02T13:31:18Z
date_updated: 2023-03-02T13:56:55Z
department:
- _id: '157'
language:
- iso: ger
publication_identifier:
isbn:
- 978-3-8440-3455-4
status: public
title: Auswirkungen von fügeprozessbedingten Delaminationen auf die mechanischen Eigenschaften
von halbhohlstanzgenieteten Mischbauverbindungen aus Faserverbundkunststoffen und
Aluminium
type: dissertation
user_id: '15324'
year: '2015'
...
---
_id: '42665'
author:
- first_name: Sebastian Patrick
full_name: Sikora, Sebastian Patrick
last_name: Sikora
citation:
ama: Sikora SP. Materialcharakterisierung und -modellierung zur Simulation von
Klebverbindungen mit Polyurethanklebstoffen.; 2015.
apa: Sikora, S. P. (2015). Materialcharakterisierung und -modellierung zur Simulation
von Klebverbindungen mit Polyurethanklebstoffen.
bibtex: '@book{Sikora_2015, title={Materialcharakterisierung und -modellierung zur
Simulation von Klebverbindungen mit Polyurethanklebstoffen}, author={Sikora, Sebastian
Patrick}, year={2015} }'
chicago: Sikora, Sebastian Patrick. Materialcharakterisierung und -modellierung
zur Simulation von Klebverbindungen mit Polyurethanklebstoffen, 2015.
ieee: S. P. Sikora, Materialcharakterisierung und -modellierung zur Simulation
von Klebverbindungen mit Polyurethanklebstoffen. 2015.
mla: Sikora, Sebastian Patrick. Materialcharakterisierung und -modellierung zur
Simulation von Klebverbindungen mit Polyurethanklebstoffen. 2015.
short: S.P. Sikora, Materialcharakterisierung und -modellierung zur Simulation von
Klebverbindungen mit Polyurethanklebstoffen, 2015.
date_created: 2023-03-02T13:42:51Z
date_updated: 2023-03-02T13:42:55Z
department:
- _id: '157'
language:
- iso: ger
publication_identifier:
isbn:
- '9783844034318'
status: public
title: Materialcharakterisierung und -modellierung zur Simulation von Klebverbindungen
mit Polyurethanklebstoffen
type: dissertation
user_id: '15324'
year: '2015'
...
---
_id: '42684'
author:
- first_name: Dirk
full_name: Westhoff, Dirk
last_name: Westhoff
citation:
ama: Westhoff D. Entwicklung und Qualifizierung eines Funktionselementes für
das einseitige, vorlochfreie Fügen im Karosserierohbau.; 2015.
apa: Westhoff, D. (2015). Entwicklung und Qualifizierung eines Funktionselementes
für das einseitige, vorlochfreie Fügen im Karosserierohbau.
bibtex: '@book{Westhoff_2015, title={Entwicklung und Qualifizierung eines Funktionselementes
für das einseitige, vorlochfreie Fügen im Karosserierohbau}, author={Westhoff,
Dirk}, year={2015} }'
chicago: Westhoff, Dirk. Entwicklung und Qualifizierung eines Funktionselementes
für das einseitige, vorlochfreie Fügen im Karosserierohbau, 2015.
ieee: D. Westhoff, Entwicklung und Qualifizierung eines Funktionselementes für
das einseitige, vorlochfreie Fügen im Karosserierohbau. 2015.
mla: Westhoff, Dirk. Entwicklung und Qualifizierung eines Funktionselementes
für das einseitige, vorlochfreie Fügen im Karosserierohbau. 2015.
short: D. Westhoff, Entwicklung und Qualifizierung eines Funktionselementes für
das einseitige, vorlochfreie Fügen im Karosserierohbau, 2015.
date_created: 2023-03-03T09:18:10Z
date_updated: 2023-03-03T09:25:33Z
department:
- _id: '157'
language:
- iso: ger
publication_identifier:
isbn:
- 978-3-8440-3530-8
status: public
title: Entwicklung und Qualifizierung eines Funktionselementes für das einseitige,
vorlochfreie Fügen im Karosserierohbau
type: dissertation
user_id: '15324'
year: '2015'
...
---
_id: '42685'
author:
- first_name: Alexander
full_name: Brodd, Alexander
last_name: Brodd
citation:
ama: Brodd A. Untersuchungen zur Prozesskette beim Kleben von CFK-Strukturbauteilen
in Leichtbaukarosserien.; 2015.
apa: Brodd, A. (2015). Untersuchungen zur Prozesskette beim Kleben von CFK-Strukturbauteilen
in Leichtbaukarosserien.
bibtex: '@book{Brodd_2015, title={Untersuchungen zur Prozesskette beim Kleben von
CFK-Strukturbauteilen in Leichtbaukarosserien}, author={Brodd, Alexander}, year={2015}
}'
chicago: Brodd, Alexander. Untersuchungen zur Prozesskette beim Kleben von CFK-Strukturbauteilen
in Leichtbaukarosserien, 2015.
ieee: A. Brodd, Untersuchungen zur Prozesskette beim Kleben von CFK-Strukturbauteilen
in Leichtbaukarosserien. 2015.
mla: Brodd, Alexander. Untersuchungen zur Prozesskette beim Kleben von CFK-Strukturbauteilen
in Leichtbaukarosserien. 2015.
short: A. Brodd, Untersuchungen zur Prozesskette beim Kleben von CFK-Strukturbauteilen
in Leichtbaukarosserien, 2015.
date_created: 2023-03-03T09:23:19Z
date_updated: 2023-03-03T09:27:09Z
department:
- _id: '157'
language:
- iso: ger
publication_identifier:
isbn:
- 978-3-8440-3973-3
status: public
title: Untersuchungen zur Prozesskette beim Kleben von CFK-Strukturbauteilen in Leichtbaukarosserien
type: dissertation
user_id: '15324'
year: '2015'
...
---
_id: '42687'
author:
- first_name: Andreas
full_name: Somnitz, Andreas
last_name: Somnitz
citation:
ama: Somnitz A. Qualifizierung des vorlochfreien Direktverschraubens von CFK-Mischbaustrukturen
für den Einsatz im Automobilbau.; 2015.
apa: Somnitz, A. (2015). Qualifizierung des vorlochfreien Direktverschraubens
von CFK-Mischbaustrukturen für den Einsatz im Automobilbau.
bibtex: '@book{Somnitz_2015, title={Qualifizierung des vorlochfreien Direktverschraubens
von CFK-Mischbaustrukturen für den Einsatz im Automobilbau}, author={Somnitz,
Andreas}, year={2015} }'
chicago: Somnitz, Andreas. Qualifizierung des vorlochfreien Direktverschraubens
von CFK-Mischbaustrukturen für den Einsatz im Automobilbau, 2015.
ieee: A. Somnitz, Qualifizierung des vorlochfreien Direktverschraubens von CFK-Mischbaustrukturen
für den Einsatz im Automobilbau. 2015.
mla: Somnitz, Andreas. Qualifizierung des vorlochfreien Direktverschraubens von
CFK-Mischbaustrukturen für den Einsatz im Automobilbau. 2015.
short: A. Somnitz, Qualifizierung des vorlochfreien Direktverschraubens von CFK-Mischbaustrukturen
für den Einsatz im Automobilbau, 2015.
date_created: 2023-03-03T10:29:32Z
date_updated: 2023-03-03T10:29:51Z
department:
- _id: '157'
language:
- iso: ger
publication_identifier:
isbn:
- 978-3-8440-3970-2
status: public
title: Qualifizierung des vorlochfreien Direktverschraubens von CFK-Mischbaustrukturen
für den Einsatz im Automobilbau
type: dissertation
user_id: '15324'
year: '2015'
...
---
_id: '40142'
author:
- first_name: Christian
full_name: Fuchs, Christian
id: '21863'
last_name: Fuchs
orcid: 0000-0003-0589-4579
citation:
ama: Fuchs C. Dijital Emek ve Karl Marx. Nota Bene; 2015.
apa: Fuchs, C. (2015). Dijital Emek ve Karl Marx. Nota Bene.
bibtex: '@book{Fuchs_2015, place={Ankara}, title={Dijital Emek ve Karl Marx}, publisher={Nota
Bene}, author={Fuchs, Christian}, year={2015} }'
chicago: 'Fuchs, Christian. Dijital Emek ve Karl Marx. Ankara: Nota Bene,
2015.'
ieee: 'C. Fuchs, Dijital Emek ve Karl Marx. Ankara: Nota Bene, 2015.'
mla: Fuchs, Christian. Dijital Emek ve Karl Marx. Nota Bene, 2015.
short: C. Fuchs, Dijital Emek ve Karl Marx, Nota Bene, Ankara, 2015.
date_created: 2023-01-26T02:17:41Z
date_updated: 2023-03-06T04:32:11Z
department:
- _id: '136'
extern: '1'
language:
- iso: tur
place: Ankara
publication_status: published
publisher: Nota Bene
status: public
title: Dijital Emek ve Karl Marx
type: book
user_id: '49063'
year: '2015'
...