Classically-Verifiable Quantum Advantage from a Computational Bell Test
Classically-Verifiable Quantum Advantage from a Computational Bell Test
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 …