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 unique
features of our interactive protocol: (i) it allows one to discard so-called
“garbage bits”, thereby removing the need for reversibility in the quantum
circuits, and (ii) there exists a natural post-selection scheme, which
significantly reduces the fidelity needed to demonstrate quantum advantage.
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.

By admin