Quantum Hamiltonian Complexity
From MaRDI portal
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.
Recommendations
- Quantum Complexity Theory
- Complexity of operators generated by quantum mechanical Hamiltonians
- Complexity of commuting Hamiltonians on a square lattice of qubits
- Complexity classification of two-qubit commuting Hamiltonians
- On quantum complexity
- Quantum Kolmogorov complexity
- Complexity of stoquastic frustration-free Hamiltonians
- Quantum information complexity
- Quantum implicit computational complexity
- Computational complexity of the quantum separability problem
Cited in
(37)- Circuit complexity in interacting QFTs and RG flows
- Action growth for AdS black holes
- Complexity of formation in holography
- The complexity of translationally invariant spin chains with low local dimension
- Comments on holographic complexity
- Surface counterterms and regularized holographic complexity
- Liouville action as path-integral complexity: from continuous tensor networks to AdS/CFT
- Universal eigenstate entanglement of chaotic local Hamiltonians
- Generic simplicity of quantum Hamiltonian reductions
- Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete
- On efficiently solvable cases of quantum \(k\)-SAT
- Complexity of quantum impurity problems
- Circuit complexity for free fermions
- Complexity of operators generated by quantum mechanical Hamiltonians
- Time evolution of complexity: a critique of three methods
- Quantum Gibbs samplers: the commuting case
- Complexity classification of local Hamiltonian problems
- Entanglement and correlation functions of the quantum Motzkin spin-chain
- Quantum max-flow/min-cut
- scientific article; zbMATH DE number 6351479 (Why is no real title available?)
- Faster ground state preparation and high-precision ground energy estimation with fewer qubits
- scientific article; zbMATH DE number 6866233 (Why is no real title available?)
- On efficiently solvable cases of quantum k-SAT
- When a local Hamiltonian must be frustration-free
- Complexity classification of two-qubit commuting Hamiltonians
- A Quantum Hamiltonian Identification Algorithm: Computational Complexity and Error Analysis
- Approximation algorithms for quantum many-body problems
- scientific article; zbMATH DE number 7650098 (Why is no real title available?)
- Hamiltonian complexity in the thermodynamic limit
- Entropy constraints for ground energy optimization
- Hamiltonian complexity in the thermodynamic limit
- An improved quantum max cut approximation via maximum matching
- Commuting local Hamiltonian problem on 2D beyond qubits
- Quantum fluctuation on the worldsheet of probe string in BTZ black hole
- Quantum entropy thermalization
- Interior point methods for structured quantum relative entropy optimization problems
- On the characterization of partially entanglement breaking and annihilating channels
This page was built for publication: Quantum Hamiltonian Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3451340)
