Avishay Tal (UC Berkeley) - On Certified Randomness from Quantum Advantage Experiments
Certified randomness is the ability to generate random bits that one can certify their randomness to a skeptic, without placing any trust in the experimental device. Recently Aaronson (Aaronson 2018, 2020) proposed a novel certified randomness protocol based on existing random circuit sampling experiments – placing this application within reach of near-term quantum devices. However, the security of Aaronson’s protocol relies on non-standard conjectures that were not previously studied in the literature. In joint work with Roozbeh Bassirian, Adam Bouland, Bill Fefferman, and Sam Gunn, we prove two versions of Aaronson’s conjectures unconditionally in the black-box (aka, random-oracle) setting.
In this talk, I will describe the setting and applications and give a brief proof outline of one of our results. The presentation will be self-contained and not assume much prior knowledge about quantum computing.
Host: Aaron Potechin
Speakers
Avishay Tal
Avishay Tal is an Assistant Professor at the University of California, Berkeley. His research interests include computational complexity theory, analysis of Boolean functions, quantum computing, pseudo randomness, and learning theory. He obtained his Ph.D. in 2015 from the Weizmann Institute of Science and later held postdoctoral appointments at the Institute for Advanced Study and at Stanford University.
