Gap Amplification for Local Hamiltonians with Combinatorial Soundness
The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.04952
curl -X POST /api/v1/records/arxiv/2610.04952/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.04952/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'