Quantum PCPs: On Adaptivity, Multiple Provers and Reductions to Local Hamiltonians

Explore a 24-minute conference talk from TQC 2024 that delves into a comprehensive formulation of quantum Probabilistically Checkable Proofs (PCPs), examining adaptivity and multiple unentangled provers. Learn about the detailed construction of quantum reduction to local Hamiltonians with constant promise gaps, and discover how non-adaptive quantum PCPs can simulate adaptive quantum PCPs with constant proof queries. Understand the relationship between quantum complexity theory problems, including the connection between QMA(k) and QMA(2), and gain insights into why quantum PCP conjecture proofs require non-relativizing techniques. Presented by Jordi Weggemans, Jonas Helsen, and Harry Buhrman at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, this talk advances theoretical quantum information science through rigorous mathematical analysis and innovative problem-solving approaches.