On the Cryptographic Foundations of Interactive Quantum Advantage

Kabir Tomer, Mark Zhandry

In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A ``trivial'' PoQ is to simp…