Oracle Separations in Quantum Complexity

Complexity theory almost never proves that two classes are different. What it proves instead is that a whole style of argument cannot decide the question — and the sharpest tool for that meta-statement is the oracle. Grant every machine, quantum and classical alike, identical black-box access to some function $A:\{0,1\}^*\to\{0,1\}$ answered in a single step, and ask whether the resulting relativized classes still stand in the same relation. A proof technique that survives this generalization to every oracle is said to relativize; the Baker–Gill–Solovay theorem of 1975 exhibited oracles $A,B$ with $\mathsf{P}^A=\mathsf{NP}^A$ and $\mathsf{P}^B\neq\mathsf{NP}^B$ , so no relativizing argument can ever settle $\mathsf{P}$ versus $\mathsf{NP}$ . This article carries that philosophy into the quantum world, where it becomes the engine that separates $\mathsf{BQP}$ from the classical complexity zoo. The technical heart is query complexity: how many calls to the hidden oracle a machine needs to decide a global property of the string it encodes. A query gap of the shape "one quantum query versus $N^{\Omega(1)}$ classical queries" lifts, by padding and diagonalization, into an oracle relative to which the corresponding uniform time-bounded classes come apart. The enterprise thus reduces to two crafts: quantum algorithms clever enough to read a global feature in one interference-powered shot, and classical lower bounds — via the polynomial method, approximate degree, or random restrictions — that no small sample can match. Three landmarks organize the story: Recursive Fourier Sampling, forrelation, and the Raz–Tal theorem that pushed $\mathsf{BQP}$ outside the entire polynomial hierarchy. Throughout, the refrain of $\mathsf{IP}=\mathsf{PSPACE}$ and $\mathsf{MIP}^*=\mathsf{RE}$ must sound: an oracle separation is a negative result about proof methods, never a theorem about the real, oracle-free world.

Key takeaways

An oracle (relativized) separation between classes $\mathcal{A}$ and $\mathcal{B}$ is a black-box language $A$ with $\mathcal{A}^A\neq\mathcal{B}^A$ ; it certifies that no relativizing proof can establish $\mathcal{A}=\mathcal{B}$ .
Bernstein and Vazirani's Recursive Fourier Sampling was the first oracle evidence for $\mathsf{BQP}\not\subseteq\mathsf{MA}$ : a $\Theta(\log n)$ -deep recursion amplifies a constant quantum edge into a quasipolynomial $n^{\Omega(\log n)}$ classical cost.
Forrelation measures how much a Boolean function resembles the Fourier transform of a second; one quantum query estimates it, yet any bounded-error classical algorithm needs $\tilde\Omega(\sqrt N)$ queries — and this $\sqrt N$ is provably the largest possible one-query gap.
Raz–Tal (2018) derandomized a Gaussian forrelation into a distribution over Boolean oracles that no constant-depth $\mathsf{AC}^0$ circuit can distinguish from uniform, yielding an oracle $O$ with $\mathsf{BQP}^O\not\subseteq\mathsf{PH}^O$ — quantum outside the whole polynomial hierarchy.
There is a hard ceiling: $\mathsf{BQP}^A\subseteq\mathsf{PP}^A\subseteq\mathsf{PSPACE}^A$ for every oracle $A$ , so no oracle can separate $\mathsf{BQP}$ from $\mathsf{PP}$ ; the Raz–Tal frontier sits just below it.
Key idea: to separate $\mathsf{BQP}$ from a classical class $\mathcal{C}$ relative to an oracle it suffices to plant, in the oracle string, a Boolean property that one bounded-error quantum query decides but that any $\mathcal{C}$ -machine making polynomially many queries cannot — interference supplies the upper bound, the polynomial method the matching classical lower bound, and a padding/diagonalization argument lifts the query gap to a uniform-class oracle separation.

The core insight

To separate $\mathsf{BQP}$ from a classical class $\mathcal{C}$ relative to an oracle, it suffices to exhibit a Boolean property of an oracle string that one bounded-error quantum query (or a constant number) decides, but that any $\mathcal{C}$ -machine making polynomially many queries cannot decide. Quantum interference supplies the upper bound; the polynomial method, approximate degree, or random restrictions supply the matching classical lower bound — and a padding/diagonalization argument lifts the query gap to a uniform-class oracle separation.

Where this lives today

The forrelation circle closed by Raz and Tal is now the theoretical backbone of quantum supremacy arguments. The same Gaussian-forrelation indistinguishability that blinds $\mathsf{AC}^0$ underlies the claim that random-circuit and boson-sampling output distributions cannot be reproduced by any $\mathsf{PH}$ -bounded classical simulator — the formal spine beneath the 2019 Sycamore and later photonic supremacy experiments, where a device samples in seconds from a distribution believed to lie outside the polynomial hierarchy. Barrier results guide the search directly: that $\mathsf{BQP}\subseteq\mathsf{PP}$ relativizes while $\mathsf{BQP}$ -vs- $\mathsf{PH}$ does not tells theorists which conjectures demand non-relativizing tools and which are dead ends. Forrelation-type statistics are also candidate verifiable benchmarks — a single-query routine yields a number that provably resists few-sample classical estimation, exactly what a classical verifier needs to gain confidence a remote device did something genuinely quantum. The open frontier is whether any relativized separation can be made unrelativized: no oracle-free proof that $\mathsf{BQP}\not\subseteq\mathsf{PH}$ is known, and $\mathsf{IP}=\mathsf{PSPACE}$ warns that one, if it exists, will look nothing like the arguments here.

The physical picture

Picture the oracle as an astronomically large lookup table an algorithm may consult but never see whole. Relativization poses one question: hand the same table to a quantum and a classical machine, and ask whether the quantum one can extract a global feature the classical one provably cannot. The feature is engineered so that quantum interference reads it in a single sweep, while classical sampling must scrape the table cell by cell. Forrelation is the cleanest incarnation. Two functions $f,g:\{0,1\}^n\to\{\pm1\}$ are packed into the oracle, and the target is $\Phi=\langle\hat f,g\rangle$ — how strongly $g$ resembles the Fourier (Walsh–Hadamard) transform of $f$ . Because a Hadamard layer is the Fourier transform, one sandwich $H^{\otimes n}U_g H^{\otimes n}U_f H^{\otimes n}$ on $|0^n\rangle$ deposits exactly $\Phi$ into a single amplitude. The first figure makes that circuit, and the one-query-versus- $\sqrt N$ gap it produces, one picture.

Figure

The forrelation circuit: the Hadamard sandwich Hⁿ Uf Hⁿ Ug Hⁿ deposits forr(f,g) into the amplitude of returning to the all-zeros state, so the acceptance probability equals the squared forrelation, read in a single quantum query, while any bounded-error classical algorithm needs Ω̃(√N) queries with N = 2ⁿ

The second half of the story is which classes an oracle can and cannot pry apart. Some containments are so robust they hold under every oracle, and those relativizing ceilings bound the whole game from above: $\mathsf{BQP}^A\subseteq\mathsf{PP}^A\subseteq\mathsf{PSPACE}^A$ for all $A$ , so no oracle will ever place $\mathsf{BQP}$ outside $\mathsf{PP}$ . The prize target was the polynomial hierarchy $\mathsf{PH}$ , which by the Furst–Saxe–Sipser correspondence relativizes to quasipolynomial-size constant-depth $\mathsf{AC}^0$ circuits. Forrelation's Gaussian cousin is exactly the distribution $\mathsf{AC}^0$ cannot tell from noise but a quantum machine can — how Raz and Tal poked a sliver of $\mathsf{BQP}$ outside $\mathsf{PH}$ while it stayed safely inside $\mathsf{PP}$ . The second figure is that landscape.

Figure

The relativized landscape: for every oracle A the ceiling BQP ⊆ PP ⊆ PSPACE holds, so no oracle escapes PP, but Raz and Tal found an oracle O with a sliver of BQP outside PH, bounded by the AC⁰ indistinguishability polylog(N)ᵈ over √N

The core equations

An oracle separation is, at bottom, a statement about proofs. If two relativized classes differ under some oracle, any argument that would have shown them equal for all oracles is dead on arrival — that is the entire logical payload.

\mathcal{A}^A \neq \mathcal{B}^A \ \Longrightarrow\ \text{no relativizing proof of } \mathcal{A}=\mathcal{B} \qquad (1)

where: $A$ — an oracle, a language answered in one step; $\mathcal{A}^A,\mathcal{B}^A$ — the classes with every machine granted identical black-box access to $A$ ; "relativizing" — a proof valid for all oracles at once. It is a barrier: the separation costs you a whole family of proof techniques. The workhorse property is forrelation, a real functional of the two oracle-encoded functions that measures Fourier alignment, normalized so its magnitude never exceeds one.

\mathrm{forr}(f,g) \;=\; \frac{1}{2^{3n/2}} \sum_{x,y\in\{0,1\}^n} f(x)\,(-1)^{x\cdot y}\,g(y) \qquad (2)

where: $f,g:\{0,1\}^n\to\{\pm1\}$ — the two Boolean functions packed into the oracle; $(-1)^{x\cdot y}$ — the $(x,y)$ entry of the $2^n$ -point Walsh–Hadamard transform, $x\cdot y$ the mod-2 inner product; $2^{3n/2}$ — the normalization fixing $|\mathrm{forr}|\le1$ . Equivalently $\mathrm{forr}=\langle\hat f,g\rangle$ up to scale, a single global correlation. Forrelation is a quantum quantity because the Hadamard sandwich computes it as an amplitude; measuring the all-zeros outcome returns its square.

\langle 0^n| H^{\otimes n} U_g H^{\otimes n} U_f H^{\otimes n}|0^n\rangle = \mathrm{forr}(f,g), \qquad \Pr[\,0^n\,]=\big|\mathrm{forr}(f,g)\big|^2 \qquad (3)

where: $U_f|x\rangle=f(x)|x\rangle$ and $U_g|y\rangle=g(y)|y\rangle$ are the $\pm1$ phase oracles; $H^{\otimes n}$ — the $n$ -fold Hadamard, i.e. the Fourier transform over $\mathbb{Z}_2^n$ . Two oracle calls sit inside one sandwich, counting as a single query in the standard convention. Derivation A tracks the amplitude layer by layer. Against that one-query upper bound stands the classical lower bound, proved by the polynomial method: no bounded-error randomized algorithm can estimate forrelation without a near-square-root number of probes.

R_\varepsilon(\mathrm{forr}) \;=\; \tilde\Omega\!\left(\sqrt{N}\right), \qquad N = 2^n \qquad (4)

where: $R_\varepsilon$ — bounded-error randomized query complexity; $N=2^n$ — the domain size of each function; $\tilde\Omega$ — an asymptotic lower bound suppressing polylog factors. The gap $1$ versus $\tilde\Omega(\sqrt N)$ is the widest a single quantum query can ever open. That optimality is a theorem, not a coincidence: Aaronson and Ambainis showed a general simulation — any property decided by $k$ quantum queries falls to a randomized algorithm using a polynomial number of queries with exponent below one.

Q(F)\le k \ \Longrightarrow\ R_\varepsilon(F)=O\!\big(N^{\,1-1/(2k)}\big) \qquad (5)

where: $Q(F)$ — bounded-error quantum query complexity of the partial property $F$ ; $R_\varepsilon(F)$ — its randomized counterpart. For $k=1$ this reads $R_\varepsilon=O(\sqrt N)$ , which forrelation's $\tilde\Omega(\sqrt N)$ meets up to logs — so forrelation is the extremal one-query problem. To reach uniform classes, the query gap is fed through the Furst–Saxe–Sipser dictionary, which turns the polynomial hierarchy into circuit language, and then through the Raz–Tal indistinguishability bound that kills those circuits.

\mathsf{PH}=\bigcup_{k\ge0}\Sigma_k^{\mathsf{P}}\ \xleftrightarrow{\ \text{relativized}\ }\ \mathsf{AC}^0,\qquad \big|\,\mathbb{E}_{\mathrm{forr}}[C]-\mathbb{E}_{\mathrm{unif}}[C]\,\big|\le\frac{\mathrm{polylog}(N)^{\,d}}{\sqrt N} \qquad (6)

where: $\Sigma_k^{\mathsf{P}}$ — the $k$ -th level of the hierarchy; $\mathsf{AC}^0$ — quasipolynomial-size, constant-depth $d$ unbounded-fan-in circuits; $C$ — any such circuit, standing in for a $\mathsf{PH}$ predicate; $\mathbb{E}_{\mathrm{forr}},\mathbb{E}_{\mathrm{unif}}$ — expectations over the planted and uniform oracle distributions. The bias decays as $1/\sqrt N$ against the fixed poly-log the circuit can muster, so $\mathsf{PH}$ is blind to a planting a quantum algorithm sees. Finally the ceiling that bounds every such result: three containments so robust they hold under all oracles at once.

\mathsf{BQP}^A\subseteq\mathsf{PP}^A\subseteq\mathsf{PSPACE}^A\quad\text{for every oracle }A \qquad (7)

where: $\mathsf{PP}$ — probabilistic polynomial time with unbounded error (majority of computation paths); $\mathsf{PSPACE}$ — polynomial space. Since these inclusions relativize, no oracle can push $\mathsf{BQP}$ past $\mathsf{PP}$ ; the Raz–Tal separation of $\mathsf{BQP}$ from $\mathsf{PH}$ therefore lives in the narrow band between $\mathsf{PH}$ and $\mathsf{PP}$ .

Derivation AForrelation as a single quantum amplitude

The goal is to prove equation (3) from the ground up: that the five-layer circuit $H^{\otimes n}U_g H^{\otimes n}U_f H^{\otimes n}$ , run on $|0^n\rangle$ and overlapped with $\langle0^n|$ , returns exactly the forrelation sum, so the outcome $0^n$ has probability $|\mathrm{forr}(f,g)|^2$ . We track the state through each layer and watch the two phase oracles and the middle Hadamard fold a full Fourier correlation into one amplitude.

Step 1. Start in $|0^n\rangle$ and apply the first Hadamard layer, $H^{\otimes n}|0^n\rangle=2^{-n/2}\sum_x|x\rangle$ , a uniform superposition over all $N=2^n$ inputs. Why: only a uniform superposition gives interference access to every table entry in parallel.

Step 2. Apply the phase oracle $U_f$ , sending $|x\rangle$ to $f(x)|x\rangle$ , giving $2^{-n/2}\sum_x f(x)|x\rangle$ . Why: encoding $f$ as a $\pm1$ phase, not an ancilla bit, lets the next transform read $f$ globally.

Step 3. Apply the middle Hadamard. Using $H^{\otimes n}|x\rangle=2^{-n/2}\sum_y(-1)^{x\cdot y}|y\rangle$ the state becomes $2^{-n}\sum_{x,y}f(x)(-1)^{x\cdot y}|y\rangle$ , whose amplitude on $|y\rangle$ is the Fourier coefficient $\hat f(y)$ . Why: a Hadamard layer is literally the Walsh–Fourier transform, so $\hat f$ appears as amplitudes for free.

Step 4. Apply the second phase oracle $U_g$ , giving $2^{-n}\sum_{x,y}f(x)(-1)^{x\cdot y}g(y)|y\rangle$ ; each Fourier amplitude is now weighted by $g(y)$ . Why: this builds the term-by-term product whose sum is the correlation $\langle\hat f,g\rangle$ .

Step 5. Apply the final Hadamard and project on $\langle0^n|$ . Since $\langle0^n|H^{\otimes n}=2^{-n/2}\sum_y\langle y|$ , the overlap gains one more $2^{-n/2}$ and sums over $y$ , yielding $2^{-3n/2}\sum_{x,y}f(x)(-1)^{x\cdot y}g(y)=\mathrm{forr}(f,g)$ ; the outcome $0^n$ has probability $|\mathrm{forr}(f,g)|^2$ . Why: the last layer collapses the correlation onto one amplitude, so a single-shot measurement — not tomography — detects it. *Verified: reproduces the Aaronson–Ambainis (2018) forrelation estimator; the amplitude algebra is checked numerically for n = 2 in the worked example, where a bent f gives forr = 1.*

Go deeper · Derivation B · 1 minLifting a query gap to a uniform oracle separation

Derivation BLifting a query gap to a uniform oracle separation

The goal is to convert the black-box statement "one quantum query, but $N^{\Omega(1)}$ classical queries" into a uniform one: a single fixed oracle $O$ relative to which $\mathsf{BQP}^O$ contains a language no $\mathcal{C}^O$ -machine decides, for any classical class $\mathcal{C}$ closed under poly-time reductions. The device is padding forrelation instances into successive blocks of one oracle and diagonalizing against an enumeration of $\mathcal{C}$ -machines — the Baker–Gill–Solovay scheme upgraded with a quantum-versus-classical query gap in place of an exhaustive-search gap.

Step 1. For each input length $m$ reserve a fresh block of $O$ holding a forrelation instance on $N=2^n$ bits with $n=\mathrm{poly}(m)$ , and define $L_O=\{1^m:\text{the length-}m\text{ block is a YES (forrelated) instance}\}$ . Why: one hard instance per length turns a query gap into a language, the object uniform classes are defined on.

Step 2. Establish $L_O\in\mathsf{BQP}^O$ : run the single-query forrelation circuit, repeat it $\mathrm{poly}(m)$ times, and amplitude-estimate whether $|\mathrm{forr}|$ is large or small with bounded error, spending only polynomially many oracle calls. Why: this pins $L_O$ inside $\mathsf{BQP}$ relative to $O$ — one side of the separation.

Step 3. Enumerate all $\mathcal{C}$ -machines $M_1,M_2,\dots$ with time bound $m^c$ . Each, at length $m$ , issues at most $m^c=N^{o(1)}$ queries — far below the $\tilde\Omega(\sqrt N)=N^{\Omega(1)}$ the lower bound demands. Why: this counting is where the query lower bound starves every classical machine of information.

Step 4. Diagonalize block by block: at stage $i$ pick a fresh length $m_i$ larger than anything touched, and fix the length- $m_i$ block so $M_i$ 's output is wrong, leaving earlier blocks intact. Since $M_i$ probes only $N^{o(1)}$ of the $N$ bits, exponentially many positions stay free to flip the answer. Why: block independence lets each machine be defeated once without backtracking.

Step 5. Conclude $L_O\notin\mathcal{C}^O$ : every $\mathcal{C}$ -machine errs on some length, while Step 2 keeps $L_O\in\mathsf{BQP}^O$ , giving $\mathsf{BQP}^O\not\subseteq\mathcal{C}^O$ . Why: the query gap has become a permanent uniform oracle separation. *Verified: reproduces the Aaronson–Ambainis lifting and is structurally identical to the Bernstein–Vazirani RFS argument and the BGS template of Derivation C.*

Go deeper · Derivation C · 1 minBaker Gill and Solovay show relativization cuts both ways

Derivation CBaker Gill and Solovay show relativization cuts both ways

The goal is to build the two oracles at the root of the whole subject: an oracle $A$ with $\mathsf{P}^A=\mathsf{NP}^A$ and an oracle $B$ with $\mathsf{P}^B\neq\mathsf{NP}^B$ , so the same question relativizes in both directions and cannot be settled by any relativizing proof. This two-sided behaviour is why $\mathsf{BQP}$ -versus- $\mathsf{PH}$ has both "pro" and "contra" oracles, and it is the template every quantum oracle separation imitates.

Step 1. Collapse with a powerful oracle: let $A$ be any $\mathsf{PSPACE}$ -complete language such as $\mathsf{TQBF}$ . Then $\mathsf{P}^A\supseteq\mathsf{PSPACE}\supseteq\mathsf{NP}^A$ , so all three coincide, $\mathsf{P}^A=\mathsf{NP}^A=\mathsf{PSPACE}^A$ . Why: a $\mathsf{PSPACE}$ oracle floods a poly-time machine with so much power that $\mathsf{NP}$ 's nondeterministic advantage evaporates.

Step 2. Separate with a sparse oracle: define $L_B=\{1^n:\exists\,x\in\{0,1\}^n,\ x\in B\}$ , testing whether $B$ contains any length- $n$ string. Clearly $L_B\in\mathsf{NP}^B$ — guess the witness $x$ and query it. Why: existence-of-a-needle is the canonical nondeterministic task, easy to verify but forced to be hard to decide.

Step 3. Diagonalize against deterministic machines: enumerate poly-time oracle machines $M_i$ ; at stage $i$ pick a length $n$ exceeding all prior queries. On $1^n$ , $M_i$ probes at most $\mathrm{poly}(n)\ll2^n$ strings. If $M_i$ accepts, keep every length- $n$ string out of $B$ ; if it rejects, plant one it never queried. Why: with $2^n$ candidates and only poly probes, an unqueried witness always exists to contradict the verdict.

Step 4. Conclude $L_B\in\mathsf{NP}^B\setminus\mathsf{P}^B$ , so $\mathsf{P}^B\neq\mathsf{NP}^B$ ; with Step 1 this proves $\mathsf{P}$ -versus- $\mathsf{NP}$ is immune to relativizing methods. Why: two oracles pointing opposite ways is the signature of a question no oracle-invariant proof can touch. *Verified: Baker–Gill–Solovay (1975), the prototype reused, with a quantum query gap, by every result in this article.*

Limiting cases

The reach of oracle separations is fenced in on all sides by relativizing inclusions; the table below marks the boundaries.

Case	Result	Meaning
Maximal query gap	$Q(\mathrm{forr})=1,\ R_\varepsilon(\mathrm{forr})=\tilde\Omega(\sqrt N)$	Forrelation is the extremal one-query problem: any property needs $\Omega(\sqrt{N}/Q)$ classical queries when $Q$ quantum queries suffice, so $\sqrt N$ is the ceiling at $Q=1$ .
Hard ceiling from PP	$\mathsf{BQP}^A\subseteq\mathsf{PP}^A\subseteq\mathsf{PSPACE}^A\ \forall A$	No oracle can separate $\mathsf{BQP}$ from $\mathsf{PP}$ or $\mathsf{PSPACE}$ ; those containments relativize, so quantum stays inside $\mathsf{PP}$ in every oracle world.
Raz–Tal frontier	$\exists\,O:\ \mathsf{BQP}^O\not\subseteq\mathsf{PH}^O$	The strongest known relativized quantum-vs-classical separation: outside the entire polynomial hierarchy, yet still inside $\mathsf{PP}^O$ .
RFS depth limit	$d=\Theta(\log n)\Rightarrow$ cost $n^{\Omega(\log n)}$	Recursion depth tuned to $\log n$ turns a constant per-level edge into a quasipolynomial gap — just enough to escape $\mathsf{MA}$ , not more.
Non-relativizing warning	$\mathsf{IP}=\mathsf{PSPACE},\ \mathsf{MIP}^*=\mathsf{RE}$	These are true unrelativized yet fail under suitable oracles, proving no oracle result can settle the matching real-world question.

Common trapAn oracle separation of BQP from PH does not prove BQP is not in PH

An oracle result $\mathsf{BQP}^A\not\subseteq\mathsf{PH}^A$ says nothing directly about the real, oracle-free classes. The decisive counterexamples are $\mathsf{IP}=\mathsf{PSPACE}$ and $\mathsf{MIP}^*=\mathsf{RE}$ : both are true unrelativized yet fail under suitable oracles, possible only because their proofs use arithmetization and other non-black-box algebra. So read an oracle separation strictly as a barrier — it rules out relativizing proof strategies for that inclusion and nothing more. Two further traps ride along. First, never conflate a query-complexity gap with a time-complexity gap until the lifting of Derivation B is carried out; only the lifting makes it a statement about $\mathsf{BQP}$ . Second, remember the ceiling: because $\mathsf{BQP}\subseteq\mathsf{PP}$ relativizes, hunting for an oracle separating $\mathsf{BQP}$ from $\mathsf{PP}$ is not hard, it is impossible.

Worked examples

1 · Forrelation of an explicit pair, computed by hand (fully worked)

Take $n=2$ , so $N=4$ and $2^{3n/2}=8$ . Encode $f=(f(00),f(01),f(10),f(11))=(+1,+1,+1,-1)$ . First correlate it with a copy of itself, $g=f$ ; then with the shifted function $g'=(+1,-1,+1,+1)$ . Find $\mathrm{forr}$ and the circuit's acceptance probability in each case.

Step 1. Compute the Walsh–Fourier transform $\hat f(y)=\tfrac14\sum_x f(x)(-1)^{x\cdot y}$ over the four inputs. Working the mod-2 dot products out gives $\hat f(00)=\hat f(01)=\hat f(10)=+\tfrac12$ and $\hat f(11)=-\tfrac12$ . Every coefficient has magnitude $\tfrac12=2^{-n/2}$ , so $f$ is a bent function — its spectrum is perfectly flat, the ideal forrelation seed.

Step 2. Use the compact identity $\mathrm{forr}(f,g)=2^{-n/2}\sum_y\hat f(y)\,g(y)$ (equivalent to equation (2) after summing over $x$ ). For $g=f$ the signs of $g$ match the signs of $\hat f$ term by term, so $\sum_y\hat f(y)f(y)=\tfrac12+\tfrac12+\tfrac12+(-\tfrac12)(-1)=2$ , and $\mathrm{forr}(f,f)=2^{-1}\cdot2=\mathbf{1}$ . The circuit returns to $|0^n\rangle$ with probability $|\mathrm{forr}|^2=\mathbf{1}$ — it accepts every time.

Step 3. Now the unforrelated $g'=(+1,-1,+1,+1)$ : $\sum_y\hat f(y)g'(y)=\tfrac12(1)+\tfrac12(-1)+\tfrac12(1)+(-\tfrac12)(1)=0$ , so $\mathrm{forr}(f,g')=\mathbf{0}$ and the acceptance probability is $\mathbf{0}$ . The same one-query circuit that fired with certainty on the aligned pair is silent here. A single quantum query cleanly separates forr = 1 from forr = 0, and the gap over classical sampling widens to $\tilde\Omega(\sqrt N)$ as $n$ grows.

2 · From a query gap to a uniform separation, with numbers

Instantiate the lifting argument at $n=40$ . How many oracle probes does each side spend, and why does the diagonalization succeed?

Step 1. The block holds $N=2^{40}\approx1.10\times10^{12}$ bits. The quantum side runs the forrelation circuit and amplitude-estimates $|\mathrm{forr}|$ with $O(\mathrm{poly}(m))$ repetitions — a few thousand single-query oracle calls. The quantum machine reads a global statistic of a trillion-bit table with roughly $10^3$ – $10^4$ probes.

Step 2. The classical lower bound demands $R_\varepsilon=\tilde\Omega(\sqrt N)$ , and $\sqrt N=2^{20}\approx1.05\times10^6$ , so any bounded-error classical algorithm needs on the order of a million probes. A poly-time $\mathcal{C}$ -machine makes only $N^{o(1)}$ queries — far below $10^6$ .

Step 3. Diagonalize: $M_i$ touches at most $N^{o(1)}\ll2^{40}$ bits, leaving essentially all $\sim10^{12}$ positions unqueried, and by the lower bound those still control the answer, so we set them to flip $M_i$ 's verdict. Because $10^{12}$ free bits dwarf the $\sim10^4$ inspected, a falsifying setting always exists — the separation is forced, not lucky.

3 · Recursive Fourier Sampling: why logarithmic depth

A single Bernstein–Vazirani layer recovers a hidden string $s$ in one quantum query (measure after $H^{\otimes n}U_s H^{\otimes n}$ ) versus $\Theta(n)$ classical queries — a linear edge, too weak to escape $\mathsf{MA}$ . RFS nests the problem in a depth- $d$ tree where a classical solver pays a multiplicative factor per level, so choosing $d=\log_2 n$ makes the classical cost $n^{\Theta(\log n)}$ while the quantum cost stays $\mathrm{poly}(n)$ . At $n=1024$ , $d=10$ and the classical cost scales like $n^{d}=1024^{10}=2^{100}\approx1.3\times10^{30}$ : <strong>ten levels convert a linear edge into a $10^{30}$ -fold gap — the first oracle evidence that $\mathsf{BQP}\not\subseteq\mathsf{MA}$ .</strong>

Physics of the portrait

Oracle separations are the work of many hands — Baker, Gill and Solovay who invented the two-oracle method; Bernstein and Vazirani who first turned it quantum; Raz and Tal who finished the $\mathsf{PH}$ story — but one figure sits at the conceptual centre of the modern chapter. Scott Aaronson defined forrelation, conjectured it was the optimal one-query separator, and posed the $\mathsf{BQP}$ -versus- $\mathsf{PH}$ oracle question that Raz and Tal resolved.

Origins · 1 minScott Aaronson and how this was discovered

Scott Aaronson

b. 1981 · quantum complexity theory and the BQP-vs-PH oracle question

Scott Aaronson, more than anyone, shaped how quantum and classical complexity are compared through oracles. In his 2009 work "BQP and the Polynomial Hierarchy" he introduced forrelation as a candidate problem inside $\mathsf{BQP}$ but, he conjectured, outside the relativized polynomial hierarchy, and framed the precise question — is there an oracle $O$ with $\mathsf{BQP}^O\not\subseteq\mathsf{PH}^O$ ? — open in spirit since Bernstein and Vazirani's Recursive Fourier Sampling. With Andris Ambainis he then proved (2015, journal 2018) that forrelation is optimal: one quantum query versus $\tilde\Omega(\sqrt N)$ classical is the widest gap any single-query property can achieve, capped by $Q(F)\le k\Rightarrow R_\varepsilon(F)=O(N^{1-1/(2k)})$ . His deeper contribution was the meta-reading: an oracle separation charts the limits of our proof techniques, never a claim about the unrelativized world — a discipline traced to Baker–Gill–Solovay and sharpened against the non-relativizing landmarks $\mathsf{IP}=\mathsf{PSPACE}$ and $\mathsf{MIP}^*=\mathsf{RE}$ . When Ran Raz and Avishay Tal closed the loop in 2018 with a Gaussian-forrelation oracle achieving $\mathsf{BQP}^O\not\subseteq\mathsf{PH}^O$ , they were answering Aaronson's question with the very problem he had designed.

History

1975

— Baker, Gill and Solovay build oracles giving both P = NP and P ≠ NP

1993

— Bernstein and Vazirani introduce Recursive Fourier Sampling, first oracle evidence BQP ⊄ MA

2009

— Aaronson defines forrelation and asks whether an oracle separates BQP from PH

2015

— Aaronson and Ambainis prove forrelation is the optimal one-query separation

2018

— Raz and Tal construct an oracle with BQP ⊄ PH

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniv. ed., Ch. 6 · Preskill, Lecture Notes on Quantum Computation, Ch. 6 · Watrous, The Theory of Quantum Information, chapters on query and interactive models · Wilde, Quantum Information Theory, 2nd ed. · Kitaev, Shen & Vyalyi, Classical and Quantum Computation · Arora & Barak, Computational Complexity, Ch. 3 (relativization) and Ch. 14.

Papers. Baker, Gill & Solovay, "Relativizations of the P =? NP Question", SIAM J. Comput. 4(4), 431 (1975) · Bernstein & Vazirani, "Quantum Complexity Theory", SIAM J. Comput. 26(5), 1411 (1997) · Furst, Saxe & Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy" (1984) · Aaronson, "BQP and the Polynomial Hierarchy", STOC 2010 · Aaronson & Ambainis, "Forrelation: A Problem that Optimally Separates Quantum from Classical Computing", SIAM J. Comput. 47(3), 982 (2018) · Raz & Tal, "Oracle Separation of BQP and PH", STOC 2019.

Provenance. A verifier should recompute: (1) the amplitude identity $\langle0^n|H^{\otimes n}U_g H^{\otimes n}U_f H^{\otimes n}|0^n\rangle=\mathrm{forr}(f,g)$ by tracking the five-layer state (Derivation A; Aaronson–Ambainis 2018); (2) the worked $n=2$ bent-function value $\mathrm{forr}(f,f)=1$ and $\mathrm{forr}(f,g')=0$ ; (3) the classical lower bound $R_\varepsilon(\mathrm{forr})=\tilde\Omega(\sqrt N)$ and its optimality via $Q(F)\le k\Rightarrow R_\varepsilon(F)=O(N^{1-1/(2k)})$ (Aaronson–Ambainis 2018); (4) the Raz–Tal indistinguishability bound and the $\mathsf{PH}\leftrightarrow\mathsf{AC}^0$ correspondence (Furst–Saxe–Sipser 1984; Raz–Tal 2019); (5) the Baker–Gill–Solovay two-oracle construction (1975); (6) the relativizing ceiling $\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}$ (Adleman–DeMarrais–Huang; Bernstein–Vazirani). No numerical constants beyond standard asymptotic exponents are asserted.

Prerequisites. The Complexity Class BQP · BQP versus P, NP, and PSPACE · Quantum Query Complexity · The Polynomial Method for Quantum Lower Bounds. Leads to. BQP is Contained in PP and PSPACE · QIP = PSPACE · MIP* = RE.

Ask the tutor: Ask me to walk you through the five-layer forrelation amplitude, the lifting diagonalization, or why $\mathsf{IP}=\mathsf{PSPACE}$ is the cautionary tale that keeps every oracle separation honest.

Does an oracle separating BQP from PH mean quantum computers are provably outside the polynomial hierarchy?

No, and this is the single most important caveat. An oracle result $\mathsf{BQP}^O\not\subseteq\mathsf{PH}^O$ only proves that no relativizing argument can show $\mathsf{BQP}\subseteq\mathsf{PH}$ . In the real, oracle-free world the containment could still hold, because the truth can contradict every oracle — the theorems $\mathsf{IP}=\mathsf{PSPACE}$ and $\mathsf{MIP}^*=\mathsf{RE}$ are exactly such cases, true unrelativized yet false under suitable oracles. Treat the Raz–Tal separation as a barrier chart: it says which proof techniques are hopeless for the real question, not what the answer is.

What exactly is forrelation, in one sentence?

Forrelation is the amount by which one Boolean function $g$ resembles the Walsh–Hadamard (Fourier) transform of a second function $f$ , packaged as the single real number $\mathrm{forr}(f,g)=2^{-3n/2}\sum_{x,y}f(x)(-1)^{x\cdot y}g(y)\in[-1,1]$ . It is a genuinely global statistic — every one of the $2^{2n}$ pairs $(x,y)$ contributes — which is why classical algorithms, forced to sample entries, struggle with it while a quantum circuit computes it as an amplitude in one shot. Near one the functions are "forrelated"; near zero they are effectively independent, and telling the cases apart is the decision problem that separates $\mathsf{BQP}$ from classical classes.

Why is the quantum-vs-classical query gap capped at square-root of N?

Because of a general simulation theorem: any partial property decidable with $k$ quantum queries can be decided by a randomized algorithm using $O(N^{1-1/(2k)})$ queries (Aaronson–Ambainis). At $k=1$ this is $O(\sqrt N)$ , so a one-query advantage can never demand more than about $\sqrt N$ classical queries. Forrelation meets this ceiling — its classical complexity is $\tilde\Omega(\sqrt N)$ — which makes it the optimal one-query separator. To open a wider gap you must let the quantum side use more queries; the bound loosens as $k$ grows, approaching a full exponential separation only as $k\to\infty$ .

What is the difference between a query separation and a uniform oracle separation?

A query separation is a statement about a fixed-size black box: so many quantum versus so many classical queries to decide one property. A uniform oracle separation is about time-bounded classes like $\mathsf{BQP}$ and $\mathsf{PH}$ relative to one infinite oracle. The bridge is the lifting argument (Derivation B): pad a hard query instance into each length-block of a single oracle and diagonalize against an enumeration of classical machines, using the query lower bound to defeat each on its own block. Skipping this step is a classic error — a query gap says nothing about $\mathsf{BQP}$ as a uniform class until the padding and diagonalization are made explicit.

Why can no oracle separate BQP from PP?

Because $\mathsf{BQP}\subseteq\mathsf{PP}$ relativizes — it holds relative to every oracle at once. The proof (Adleman–DeMarrais–Huang) simulates a quantum computation by summing the amplitudes of computational paths, which a $\mathsf{PP}$ machine can do whether or not both machines share an oracle. Since $\mathsf{BQP}^A\subseteq\mathsf{PP}^A$ for all $A$ , no oracle world puts $\mathsf{BQP}$ outside $\mathsf{PP}$ , so searching for a separating oracle is provably futile. This is why the Raz–Tal frontier stops at $\mathsf{PH}$ : it is the strongest classical class oracles can still pry loose from $\mathsf{BQP}$ , sitting just under the $\mathsf{PP}$ ceiling.

How does the polynomial hierarchy become circuits in these proofs?

Through the relativized Furst–Saxe–Sipser correspondence: a language in the $k$ -th level $\Sigma_k^{\mathsf{P}}$ , relativized, corresponds to a quasipolynomial-size, constant-depth $\mathsf{AC}^0$ circuit with $k$ alternating layers of unbounded-fan-in AND/OR gates. This lets a circuit lower bound stand in for a complexity-class separation. Raz and Tal's core result is exactly an $\mathsf{AC}^0$ statement — no such circuit distinguishes the forrelated oracle distribution from uniform, its bias bounded by $\mathrm{polylog}(N)^d/\sqrt N$ — and the correspondence upgrades that into the uniform separation $\mathsf{BQP}^O\not\subseteq\mathsf{PH}^O$ .