Classically-Verifiable Quantum Advantage from a Computational Bell Test

Understand

We propose and analyze a novel interactive protocol for demonstrating quantum computational advantage, which is efficiently classically verifiable.

• Our protocol relies upon the cryptographic hardness of trapdoor claw-free functions (TCFs).
• Through a surprising connection to Bell's inequality, our protocol avoids the need for an adaptive hardcore bit, with essentially no increase in the quantum circuit complexity and no extra cryptographic assumptions.
• Crucially, this expands the set of compatible TCFs, and we propose two new constructions: one based upon the decisional Diffie-Hellman problem and the other based upon Rabin's function, $x^2 \bmod N$.