PIRSA:18070057

Video URL

https://pirsa.org/18070057

Certified Randomness from Quantum Supremacy

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

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

          @misc{ scivideos_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 for Theoretical Physics},
            year = {2018},
            month = {jul},
            note = {PIRSA:18070057 see, \url{https://scivideos.org/pirsa/18070057}}
          }

Scott Aaronson The University of Texas at Austin

Talk numberPIRSA:18070057
DOI10.48660/18070057
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
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.