PIRSA:18070057

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

Talk number
PIRSA:18070057
Collection
Talk Type
Subject
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.