We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The commuting local Hamiltonian problem on locally expanding graphs is approximable in $$\mathsf{{NP}}$$.
- Authors
Aharonov, Dorit; Eldar, Lior
- Abstract
The local Hamiltonian problem is famously complete for the class $$\mathsf{{QMA}}$$ , the quantum analogue of $$\mathsf{{NP}}$$ . The complexity of its semiclassical version, in which the terms of the Hamiltonian are required to commute (the $$\mathsf{{CLH}}$$ problem), has attracted considerable attention recently due to its intriguing nature, as well as in relation to growing interest in the $$\mathsf{{qPCP}}$$ conjecture. We show here that if the underlying bipartite interaction graph of the $$\mathsf{{CLH}}$$ instance is a good locally expanding graph, namely the expansion of any constant-size set is $$\varepsilon $$ -close to optimal, then approximating its ground energy to within additive factor $$O(\varepsilon )$$ lies in $$\mathsf{{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 $$\mathsf{{CLH}}$$ on such good local expanders is $$\mathsf{{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 $$\mathsf{{PCP}}$$ proof) in an attempt to prove the quantum $$\mathsf{{PCP}}$$ conjecture. A related result was discovered recently independently by Brandão and Harrow, for $$2$$ -local general Hamiltonians, bounding the quantum hardness of the approximation problem on good expanders, though no $$\mathsf{{NP}}$$ hardness is known in that case.
- Subjects
HAMILTONIAN systems; PROBLEM solving; APPROXIMATION theory; QUANTUM theory; BIPARTITE graphs
- Publication
Quantum Information Processing, 2015, Vol 14, Issue 1, p83
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-014-0877-9