[Theory] UC Theory Seminar

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, May 24, 3:30pm
Location Kent 107

Avishay Tal (Berkeley)

TITLE: On certified randomness from quantum advantage experiments

ABSTRACT: 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. 

%%%%%%%%%%%%%%%%%%%%%%%%%
Re the recent University masking guidance: since the room is huge, we will not be
making designated “masks-only” zone. We, however, encourage the audience to space out and try to congregate according to their masking philosophy.