Certified Randomness from Quantum Supremacy


Aaronson, S. (2018). Certified Randomness from Quantum Supremacy. Perimeter Institute. https://pirsa.org/18070057


Aaronson, Scott. Certified Randomness from Quantum Supremacy. Perimeter Institute, Jul. 25, 2018, https://pirsa.org/18070057


          @misc{ pirsa_PIRSA:18070057,
            doi = {10.48660/18070057},
            url = {https://pirsa.org/18070057},
            author = {Aaronson, Scott},
            keywords = {Quantum Information},
            language = {en},
            title = {Certified Randomness from Quantum Supremacy},
            publisher = {Perimeter Institute},
            year = {2018},
            month = {jul},
            note = {PIRSA:18070057 see, \url{https://pirsa.org}}

Scott Aaronson The University of Texas at 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.