QMA and the Power of “Positivity”
summary
The paper shows a surprising dichotomy: restricting witnesses to non-negative amplitudes can either leave QMA+ equal to QMA or make QMA+ (and QMA2+) as powerful as NEXP depending on the constant completeness–soundness gap. The construction uses PCP amplification and Dinur preprocessing, encodes constraints as question/answer registers, estimates L1 mass with a pi-plus projector, forces a rigid uniform one-answer-per-question form, enforces consistency via expanders decomposed into permutations and checks invariance with the Hadamard test, all scalable to succinct NEXP instances.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 0:52Context
- 2:30Facts
- 7:14Gap amplification
- 8:32Upper bound optimization
- 10:02Power of QMA
- 16:34MP Hard
- 17:44Positivity
- 27:37How to use this power
- 30:27Consistency test
- 34:49Recap
- 34:59Goal
- 36:37Example
- 42:42Consistency
- 48:02Conclusions
related talks
48mThe Quantum Games PCP: Results and Confessions
58mTwo classical oracle separations between QMA and QCMA
22mQuantum space, ground space traversal, and how to embed multi-prover...
37mQuantum Pseudorandomness and Classical Complexity
44mQuantum Meets Minimum Circuit Size Problem
01h 09mRecent Progress in Quantum Advantage
45mInteractive Proofs for Synthesizing Quantum States and Unitaries
01h 06mPractical Quantum Machine Learning: Overcoming the Bottlenecks of Scalability and(…)