+++ONLINE COLLOQUIUM+++ BQP After 28 Years (MCQST-Colloquium) (Prof. Scott Aaronson)

  • (online)
  • Datum: 26.04.2022
  • Uhrzeit: 16:00
  • Vortragende(r): Prof. Scott Aaronson
  • The University of Texas, Austin, USA
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.

Zur Redakteursansicht