PIRSA:18070057

Certified Randomness from Quantum Supremacy

APA

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

MLA

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

BibTex

          @misc{ 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 University of Texas - Austin

Abstract

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.