The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP

DOI10.1007/S11128-014-0877-9zbMATH Open1327.68105arXiv1311.7378OpenAlexW2039104910MaRDI QIDQ2018136FDOQ2018136

Authors: Dorit Aharonov, Lior Eldar 

Publication date: 13 April 2015

Published in: Quantum Information Processing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1311.7378

Recommendations

• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• Product-state approximations to quantum ground states
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• The Complexity of the Local Hamiltonian Problem
• Approximation algorithms for QMA-complete problems

zbMATH Keywords

approximationPCPlocal Hamiltoniancommuting local Hamiltonianquantum PCP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35)

Cites Work

• Title not available (Why is that?)
• Fault-tolerant quantum computation by anyons
• Expander codes
• Proof verification and the hardness of approximation problems
• Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
• Probabilistic checking of proofs
• Title not available (Why is that?)
• Some optimal inapproximability results
• The PCP theorem by gap amplification
• On the power of unique 2-prover 1-round games
• Graph expansion and the unique games conjecture
• The detectability lemma and quantum gap amplification
• Randomness conductors and constant-degree lossless expanders
• The complexity of quantum spin systems on a two-dimensional square lattice
• The Complexity of the Local Hamiltonian Problem
• The power of quantum systems on a line
• Subexponential Algorithms for Unique Games and Related Problems
• Commutative version of the local Hamiltonian problem and common eigenspace problem
• Unique games on expanding constraint graphs are easy (extended abstract)
• Hardness of Approximation for Quantum Problems
• Efficient algorithm for a quantum analogue of 2-SAT
• Dense Locally Testable Codes Cannot Have Constant Rate and Distance
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation Algorithms for QMA-Complete Problems
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems

Cited In (7)

• Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems
• Commutative version of the local Hamiltonian problem and common eigenspace problem
• Title not available (Why is that?)
• Total functions in QMA
• Title not available (Why is that?)
• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• NLTS Hamiltonians from good quantum codes

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)