Date & Time:
May 24, 2022 3:30 pm – 4:30 pm
Kent 107, 1020-24 East 58th St., Chicago, IL, 60637
05/24/2022 03:30 PM 05/24/2022 04:30 PM America/Chicago Avishay Tal (UC Berkeley) – On Certified Randomness from Quantum Advantage Experiments Kent 107, 1020-24 East 58th St., Chicago, IL, 60637

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


Avishay Tal

Assistant Professor, University of California, Berkeley

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.

Related News & Events

UChicago CS News

Non-Unital Noise Adds a New Wrinkle to the Quantum Supremacy Debate

Apr 05, 2024
In the News

The Science of Computer Security: An Interview with Grant Ho, Assistant Professor in Computer Science

Apr 02, 2024
UChicago CS News

Four Students Receive Honorable Mention in CRA Undergraduate Research Awards

Mar 25, 2024
UChicago CS News

Navigating the Intersection of Technology and Public Policy: The Journey of Ranya Sharma at UChicago

Mar 21, 2024
UChicago CS News

Assistant Professor Aloni Cohen Receives Prestigious Award for Groundbreaking Research in Machine Learning Complexity

Mar 20, 2024
UChicago CS News

Haifeng Xu named a AI2050 Early Career Fellow

Mar 11, 2024
UChicago CS News

FabRobotics: The Fusion of 3D Printing and Mobile Robots

Feb 27, 2024
UChicago CS News

Professor Andrew A. Chien on the Environmental Impacts of Technology

Feb 26, 2024
UChicago CS News

Assistant Professor Yanjing Li Awarded NSF CAREER Grant for Innovative Computer Architecture and Deep Learning Research

Feb 26, 2024
UChicago CS News

Prof. Rebecca Willett awarded the SIAG DATA Career prize

Feb 21, 2024
UChicago CS News

Argonne scientists use AI to identify new materials for carbon capture

Feb 19, 2024
UChicago CS News

Alumni Spotlight: Dixin Tang, Assistant Professor of Computer Science at UT Austin

Feb 05, 2024
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube