Certified Randomness from Quantum Supremacy
August 19, 2018, 4:10 PM - 5:00 PM
Location:
Corwin Pavilion West
University of California, Santa Barbara
Scott Aaronson, University of Texas, Austin
I’ll describe a novel application for near-term quantum computers with 50-70 qubits: namely, generating cryptographic random bits, whose randomness can be certified even if the quantum computer is untrusted (e.g., has been backdoored by an adversary). Unlike schemes based on Bell inequality violation, ours requires only a single device able to solve classically hard sampling problems. Our protocol harvests the outputs of the sampling process and feeds them into a randomness extractor, while occasionally verifying the outputs using exponential classical time. I’ll also compare to the beautiful independent work of Brakerski et al., who proposed a scheme for the same problem that has much more efficient verification, but that probably can’t be implemented on near-term devices. Paper still in preparation. As time permits, I’ll also say something about a new connection between gentle measurement of quantum states and differential privacy (joint work with Guy Rothblum, paper still in preparation).