[Theory] UC Theory Seminar: a reminder

[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 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.