The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
From MaRDI portal
Publication:2018136
DOI10.1007/s11128-014-0877-9zbMath1327.68105arXiv1311.7378OpenAlexW2039104910MaRDI QIDQ2018136
Publication date: 13 April 2015
Published in: Quantum Information Processing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.7378
Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Total functions in QMA ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The power of quantum systems on a line
- Fault-tolerant quantum computation by anyons
- Hardness of Approximation for Quantum Problems
- Graph expansion and the unique games conjecture
- Dense Locally Testable Codes Cannot Have Constant Rate and Distance
- Expander codes
- Approximation Algorithms for QMA-Complete Problems
- Proof verification and the hardness of approximation problems
- Subexponential Algorithms for Unique Games and Related Problems
- Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
- On the power of unique 2-prover 1-round games
- Randomness conductors and constant-degree lossless expanders
- Probabilistic checking of proofs
- The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
- The detectability lemma and quantum gap amplification
- Some optimal inapproximability results
- The Complexity of the Local Hamiltonian Problem
- On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
- The PCP theorem by gap amplification
This page was built for publication: The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
