Depth-efficient proofs of quantumness

Quantum 6, 807 (2022).

https://doi.org/10.22331/q-2022-09-19-807

A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the $textit{quantum advantage}$ of an untrusted prover. That is, a quantum prover can correctly answer the verifier’s challenges and be accepted, while any polynomial-time classical prover will be rejected with high probability, based on plausible computational assumptions. To answer the verifier’s challenges, existing proofs of quantumness typically require the quantum prover to perform a combination of polynomial-size quantum circuits and measurements.
In this paper, we give two proof of quantumness constructions in which the prover need only perform $textit{constant-depth quantum circuits}$ (and measurements) together with log-depth classical computation. Our first construction is a generic compiler that allows us to translate all existing proofs of quantumness into constant quantum depth versions. Our second construction is based around the $textit{learning with rounding}$ problem, and yields circuits with shorter depth and requiring fewer qubits than the generic construction. In addition, the second construction also has some robustness against noise.