English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The local Hamiltonian problem is famously complete for the class QMA, thequantum analogue of NP. The complexity of its semi-classical version, in whichthe terms of the Hamiltonian are required to commute (the CLH problem), hasattracted considerable attention recently due to its intriguing nature, as wellas in relation to growing interest in the qPCP conjecture. We show here that ifthe underlying bipartite interaction graph of the CLH instance is a goodlocally-expanding graph, namely, the expansion of any constant-size set ise-close to optimal, then approximating its ground energy to within additivefactor O(e) lies in NP. The proof holds for k- local Hamiltonians for anyconstant k and any constant dimensionality of particles d. We also show thatthe approximation problem of CLH on such good local expanders is NP-hard. Thisimplies that too good local expansion of the interaction graph constitutes anobstacle against quantum hardness of the approximation problem, though itretains its classical hardness. The result highlights new difficulties intrying to mimic classical proofs (in particular Dinur's PCP proof) in anattempt to prove the quantum PCP conjecture. A related result was discoveredrecently 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.

The commuting local Hamiltonian on locally-expanding graphs is in NP