A note about a partial no-go theorem for quantum PCP

MaRDI QIDQ3101921zbMATH OpenFDO

Authors Itai Arad

Publication date 1 December 2011

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

zbMATH Keywords

local HamiltoniansQSATquantum PCP

Mathematics Subject Classification ID

Proof theory in general (including proof-theoretic semantics) (03F03) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Recommendations

• Pointer Quantum PCPs and Multi-Prover Games
• The detectability lemma and quantum gap amplification
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• Quantum information and the PCP theorem
• Product-state approximations to quantum ground states

Cited in

(3)

• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• Hamiltonian sparsification and gap-simulation
• Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture

This page was built for publication: A note about a partial no-go theorem for quantum PCP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3101921)