Heisenberg's uncertainty principle states that it is not possible to compute both the position and momentum of an electron with absolute certainty. However, this computational limitation, which is central to quantum mechanics, has no counterpart in theoretical computer science. Here, I will show that we can distinguish between the complexity classes P and NP when we consider intrinsic uncertainty in our computations, and take uncertainty about whether a bit belongs to the program code or machine input into account. Given intrinsic uncertainty, every output is uncertain, and computations become meaningful only in combination with a confidence level. In particular, it is impossible to compute solutions with absolute certainty as this requires infinite run-time. Considering intrinsic uncertainty, I will present a function that is in NP but not in P, and thus prove that P is a proper subset of NP. I will also show that all traditional hard decision problems have polynomial-time algorithms that provide solutions with confidence under uncertainty.
I will 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 will 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 will then discuss very 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} ̸ ⊂ BQP^{PH} - solving a 2005 open problem of Lance Fortnow - and conversely, relative to which BQP^{NP} ̸ ⊂ PH^{BQP}; an oracle relative to which 𝖯 = NP and yet BQP ≠ QCMA; an oracle relative to which NP ⊆ BQP yet PH is infinite; an oracle relative to which 𝖯 = NP≠ BQP = PP; and an oracle relative to which PP = PostBQP ̸ ⊂ QMA^{QMA^{…}}. By popular demand, I will also speculate about the status of BQP in the unrelativized world.
Quantum complexity has emerged as a natural probe of chaos, thermalization, and the black hole interior on timescales long after local observables have equilibrated. However, its time evolution has been studied almost exclusively in subsystems confined to a single connected region. We show, using complementary tools from holography and random quantum circuits, that noncontiguous subsystems composed of multiple disjoint regions give rise to qualitatively new physics compared to the contiguous case. First, at finite temperature, a subsystem occupying less than half of the total system can carry high complexity at late times, even as the complexity of its larger complement remains low. This inversion of the usual hierarchy is intrinsically thermal: it vanishes in the infinite-temperature limit, which is the regime modeled by random quantum circuits. Second, if a subsystem's complexity equilibrates at an early time, then fragmenting it into
m disjoint components can further reduce this timescale by a factor of
m, a phenomenon we exhibit in both holography and random quantum circuits. These results not only sharpen the correspondence between geometric and computational notions of complexity, but also motivate the search for novel complexity phenomena in quantum dynamics.