Uploaded July 2026 | Updated September 2026, 1 week ago
Quynh T. Nguyen (Harvard University)
https://simons.berkeley.edu/talks/quynh-t-nguyen-harvard-university-2026-07-23
Quantum Summer Cluster Final Workshop
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 dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of every known strategy for proving the classical PCP theorem. Here, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies combinatorial gap. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central structural ingredients in classical PCPs into the quantum setting.
Quynh T. Nguyen (Harvard University)
https://simons.berkeley.edu/talks/quynh-t-nguyen-harvard-university-2026-07-23
Quantum Summer Cluster Final Workshop
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 dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of every known strategy for proving the classical PCP theorem. Here, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies combinatorial gap. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central structural ingredients in classical PCPs into the quantum setting.
