Quantum PCPs Meet Derandomization

on YouTube ↗01h 01m

" summary

Conjecture: a gap-amplifying map from general local Hamiltonians to stochastic uniform Hamiltonians exists if and only if randomized verification class MA derandomizes. Proof constructs reductions from MA to stochastic local Hamiltonians and a verifier that runs an implicit graph random-walk over bit-strings; main technical tools are a one-term and non-overlapping expansion lemma and a light-cone argument that extracts a constant-size path to a bad string. Consequence: deciding constant promise gap for these stochastic Hamiltonians is in NP.

AI-written summary · about

" chapters (11)

1. 0:00Introduction to the workshop
2. 1:03Complexity and randomization
3. 4:35Defining NP, MA, and TMA
4. 8:03Hamiltonian complexity overview
5. 11:50Stochastic Hamiltonians
6. 18:04Main results and conjectures
7. 22:15Gap amplification and MA
8. 28:33Implicit graph random walks
9. 36:40Proof structure and lemmas
10. 48:19Open problems and outlook
11. 53:10Q&A session