BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Complexity-Theoretic Foundations of Quantum Supremacy Experiments Aaronson, Scott


Depending on time, I'll discuss some subset of the following results. (1) There exists an oracle relative to which classical and quantum computers can solve the same approximate sampling problems in polynomial time, and yet the polynomial hierarchy is infinite. This means that any "BosonSampling-type theorem" will need to be non-relativizing. (2) Can P be separated from BQP by an efficiently-computable oracle (one in P/poly)? Yes if quantum-resistant one-way functions exist; no if P=PSPACE. The latter builds on recent results in quantum query complexity by myself and Shalev Ben-David. (3) How hard is it to approximately sample the output distribution of a random quantum circuit? One can do it (and even calculate the probabilities) in polynomial space and m^O(n) time, where m is the number of gates and n is the number of qubits. But if that's essentially optimal for estimating probabilities, then approximate sampling also requires exponential time. Joint work with Lijie Chen (Tsinghua University)

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International