--- _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' ...