The MCQST Colloquium Series features interdisciplinary talks given by visiting international speakers. The monthly colloquial covers topics spanning all MCQST research units and will be broadcasted live, being made available to audiences worldwide. The main goal of the series is to create the framework for idea exchange, to strengthen links with QST leading groups worldwide, as well as to act as an integral part of the local educational environment.

MCQST Colloquium: Scott Aaronson

On April 26th, 2022, we are excited to invite you to the colloquium offered by Scott Aaronson, Professor at University of Texas at Austin:

BQP After 28 Years

I'll discuss the now-ancient question of where BQP, Bounded-Error Quantum Polynomial-Time, fits in among classical complexity classes. After reviewing some basics from the 90s, I’ll discuss the Forrelation problem that I introduced in 2009 to yield an oracle separation between BQP and PH, and the dramatic completion of that program by Ran Raz and Avishay Tal in 2018. I’ll then discuss recent work, with William Kretschmer and DeVon Ingram, which leverages the Raz-Tal theorem, along with a new "quantum-aware" random restriction method, to obtain results that illustrate just how differently BQP can behave from BPP. These include oracles relative to which NP^BQP is not in BQP^PH -- solving a 2005 open problem of Lance Fortnow -- and conversely, relative to which BQP^NP is not in PH^BQP; an oracle relative to which P=NP and yet BQP!=QCMA; an oracle relative to which BQP contains NP yet PH is infinite; an oracle relative to which P=NP!=BQP=PP; and an oracle relative to which PP=PostBQP is not in QMA^QMA^… By popular demand, I’ll also speculate about the status of BQP in the unrelativized world.

If you would like to get more information about future talks, you can sign up for our mailing lists using the following links: