The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP
From MaRDI portal
Publication:2018136
Abstract: The local Hamiltonian problem is famously complete for the class QMA, the quantum analogue of NP. The complexity of its semi-classical version, in which the terms of the Hamiltonian are required to commute (the CLH problem), has attracted considerable attention recently due to its intriguing nature, as well as in relation to growing interest in the qPCP conjecture. We show here that if the underlying bipartite interaction graph of the CLH instance is a good locally-expanding graph, namely, the expansion of any constant-size set is e-close to optimal, then approximating its ground energy to within additive factor O(e) lies in NP. The proof holds for k- local Hamiltonians for any constant k and any constant dimensionality of particles d. We also show that the approximation problem of CLH on such good local expanders is NP-hard. This implies that too good local expansion of the interaction graph constitutes an obstacle against quantum hardness of the approximation problem, though it retains its classical hardness. The result highlights new difficulties in trying to mimic classical proofs (in particular Dinur's PCP proof) in an attempt to prove the quantum PCP conjecture. A related result was discovered recently independently by Brandao and Harrow, for 2-local general Hamiltonians, bounding the quantum hardness of the approximation problem on good expanders, though no NP-hardness is known in that case.
Recommendations
Cites work
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- A note about a partial no-go theorem for quantum PCP
- Approximation algorithms for QMA-complete problems
- Commutative version of the local Hamiltonian problem and common eigenspace problem
- Complexity of commuting Hamiltonians on a square lattice of qubits
- Dense locally testable codes cannot have constant rate and distance
- Efficient algorithm for a quantum analogue of 2-SAT
- Expander codes
- Fault-tolerant quantum computation by anyons
- Graph expansion and the unique games conjecture
- Hardness of approximation for quantum problems
- On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
- On the power of unique 2-prover 1-round games
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Randomness conductors and constant-degree lossless expanders
- Some optimal inapproximability results
- Subexponential algorithms for unique games and related problems
- The Complexity of the Local Hamiltonian Problem
- The PCP theorem by gap amplification
- The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
- The complexity of quantum spin systems on a two-dimensional square lattice
- The detectability lemma and quantum gap amplification
- The power of quantum systems on a line
- Unique games on expanding constraint graphs are easy (extended abstract)
Cited in
(10)- A note about a partial no-go theorem for quantum PCP
- Hamiltonian sparsification and gap-simulation
- NLTS Hamiltonians from good quantum codes
- On the complexity of two dimensional commuting local Hamiltonians
- Total functions in QMA
- THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
- Product-state approximations to quantum ground states
- Product-state approximations to quantum states
- Commutative version of the local Hamiltonian problem and common eigenspace problem
- Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems
This page was built for publication: The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018136)
