Classical Verification of a Remote Quantum Processor via Degenerate Concordant Computations: An Application to Randomness Generation

A client who rents a cloud quantum processor cannot easily tell whether the bitstrings it receives came from a quantum device. Certification by random circuit sampling runs on present hardware, but scoring each returned sample costs the client time $O(2^n)$. We give a protocol in which the client sc