Scott Aaronson, Alex Arkhipov

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a

model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count ...
more >>>

Scott Aaronson, Andrew Drucker

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

Yang Li

We initiate the study of the relationship between two complexity classes, BQP

(Bounded-Error Quantum Polynomial-Time) and PPAD (Polynomial Parity Argument,

Directed). We first give a conjecture that PPAD is contained in BQP, and show

a necessary and sufficient condition for the conjecture to hold. Then we prove

that the conjecture ...
more >>>

Adam Bouland, Scott Aaronson

In 1994, Reck et al. showed how to realize any linear-optical unitary transformation using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of m by m unitary transformations (or orthogonal transformations, in the real case) ... more >>>

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the ... more >>>

Ran Raz, Avishay Tal

We present a distribution $D$ over inputs in $\{-1,1\}^{2N}$, such that:

(1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time $O(\log N)$, that distinguishes between $D$ and the uniform distribution with advantage $\Omega(1/\log N)$.

(2) No Boolean circuit of $\mathrm{quasipoly}(N)$ ...
more >>>

Xinyu Wu

After presentations of the oracle separation of BQP and PH result by Raz and Tal [ECCC TR18-107], several people

(e.g. Ryan Oâ€™Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified by

stochastic calculus. In this short note, we describe such a simplification.

Scott Aaronson, DeVon Ingram, William Kretschmer

We show that, in the black-box setting, the behavior of quantum polynomial-time (${BQP}$) can be remarkably decoupled from that of classical complexity classes like ${NP}$. Specifically:

-There exists an oracle relative to which ${NP}^{{BQP}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits ... more >>>