  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$. We also describe two
independent innovations which improve the efficiency of our protocol's
implementation: (i) a scheme to discard so-called "garbage bits", thereby
removing the need for reversibility in the quantum circuits, and (ii) a natural
way of performing post-selection which significantly reduces the fidelity
needed to demonstrate quantum advantage. These two constructions may also be of
independent interest, as they may be applicable to other TCF-based quantum
cryptography such as certifiable random number generation. Finally, we design
several efficient circuits for $x^2 \bmod N$ and describe a blueprint for their
implementation on a Rydberg-atom-based quantum computer.
