Association for Computing Machinery Lecture in Memory of Nathan Krasnopoler: Quantum Supremacy and Its Applications

Description

In the near future, there will likely be special-purpose quantum computers with 50-70 high-quality qubits and controllable nearest-neighbor couplings. In this lecture, Scott Aaronson, of University of Texas at Austin, focuses on general theoretical foundations for how to use such devices to demonstrate quantum supremacy; that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis, which says that all physical systems can be efficiently simulated by classical computers, as confidently as possible. This part of the talk is based on joint work with Lijie Chen.

Then, in a second part of the talk, Aaronson will discuss brand new work on how these experiments could be used to generate cryptographically certified random bits.