Oracle Separation of BQP and the Polynomial Hierarchy

Complexity theory organizes "efficient computation" around the polynomial hierarchy $\mathsf{PH}$ — the tower $\mathsf{P}\subseteq\mathsf{NP}\subseteq\Sigma_2^{\mathsf{P}}\subseteq\cdots$ built by alternating $\exists$ and $\forall$ quantifiers over short certificates. When quantum computers arrived, the question was where quantum polynomial time, $\mathsf{BQP}$ , sits in it. Factoring lives in $\mathsf{BQP}$ but also in $\mathsf{PH}$ , so it settles nothing. Could every quantum algorithm be simulated somewhere in the hierarchy — is $\mathsf{BQP}\subseteq\mathsf{PH}$ ? Intuition said no: interference feels nothing like nondeterministic guessing. Turning that into a theorem took twenty-five years. Because an unconditional separation would resolve monsters like $\mathsf{P}$ versus $\mathsf{PSPACE}$ , the achievable target is an oracle (relativized) separation: hand both classes the same black box $\mathcal{O}$ and ask whether some $\mathcal{O}$ forces $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{PH}^{\mathcal{O}}$ . Aaronson (2010) distilled the problem to one query-complexity statement and named the hard instance: forrelation. The missing half — a classical lower bound matching the trivial quantum upper bound — was supplied by Ran Raz and Avishay Tal in 2018, welding query complexity to the Fourier analysis of Boolean functions. This article develops both halves with re-derived constants and explains why the result marks the outer boundary of relativizing proofs.

Key takeaways

Relative to a suitable oracle, a problem a quantum computer solves in one query lies outside the entire polynomial hierarchy: $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{PH}^{\mathcal{O}}$ — the 2018 theorem of Raz and Tal.
The witness is forrelation: decide whether $f,g$ are independent or whether $g$ is aligned with the Hadamard transform $\widehat f$ ; the statistic is $\mathrm{forr}(f,g)=\langle\widehat f,g\rangle/N$ .
One quantum query reads it off — the amplitude returning to $\lvert 0^n\rangle$ equals $\mathrm{forr}$ , so $\Pr[0^n]=\mathrm{forr}^2$ ; independent inputs give $\mathrm{forr}\sim 1/\sqrt N$ , forrelated give $\mathrm{forr}=\Omega(1)$ .
The classical lower bound rests on Tal's Fourier-tail bound for $\mathsf{AC}^0$ : constant-depth circuits have exponentially small Fourier weight above degree $\sim(\log s)^{d-1}$ , where the signal sits.
It is an oracle separation: it does not prove $\mathsf{BQP}\not\subseteq\mathsf{PH}$ in the real world, but rules out every relativizing proof of the reverse containment — strong evidence for super-polynomial quantum advantage.
Key idea: forrelation is a global, high-Fourier-degree correlation a quantum computer evaluates in a single interference step, yet $\mathsf{AC}^0$ and $\mathsf{PH}$ circuits carry vanishing Fourier weight on precisely the high-order structure that separates the forrelated distribution from the independent one.

The core insight

Forrelation — the normalized inner product $\langle\widehat f,g\rangle/N$ of $g$ with the Hadamard transform of $f$ — is the amplitude a quantum computer reads off in one query, yet $\mathsf{AC}^0$ (hence $\mathsf{PH}$ ) circuits have negligible Fourier weight on the high-degree structure that separates the forrelated from the independent distribution.

Where this lives today

Forrelation sits where quantum complexity, circuit lower bounds, and quantum advantage meet. As a barrier result it reshaped strategy: since $\mathsf{BQP}\subseteq\mathsf{PH}$ cannot be proved by any relativizing argument, settling the question demands non-relativizing methods — as $\mathsf{IP}=\mathsf{PSPACE}$ taught for interactive proofs. It is the cleanest speedup defeating not just $\mathsf{P}$ but the whole tower of $\mathsf{PH}$ , and has been sharpened into "raw" and $k$ -fold variants proving further separations; its proof technology — Tal's $\mathsf{AC}^0$ Fourier-tail bounds — now also feeds pseudorandom generators, low-degree learning, and average-case lower bounds. The open frontier is an unrelativized separation, which forrelation frames but, being a query result, cannot itself resolve.

The physical picture

Picture the oracle as a long Boolean string in two halves, $f$ and $g$ on $\{0,1\}^n$ ( $N=2^n$ entries). A quantum computer spreads a register over all $N$ addresses, stamps the phase $f(x)$ everywhere at once, Hadamard-transforms that pattern into the spectrum $\widehat f$ , stamps $g(y)$ , and folds back with a final Hadamard. The amplitude surviving on the all-zeros string is a global correlation of the two halves — the overlap of $g$ with $\widehat f$ — in one interference step. A $\mathsf{PH}$ machine sees only individual bits and must reconstruct this global statistic from local samples.

Figure

The one-query forrelation algorithm: phase queries O_f and O_g sandwiched between Hadamard transforms Hⁿ, so the amplitude returning to 0ⁿ is exactly forr(f,g) = ⟨f̂,g⟩ ∕ N and Pr(0ⁿ) = forr². Forrelated inputs give forr ≈ 1 (here forr = 1 for the n = 2 instance f = + + + −), independent inputs give forr ∼ 1∕√N

Why is this hard for the hierarchy? Because the signal lives at high Fourier degree. In the independent case the amplitude on $\lvert 0^n\rangle$ is a sum of $N$ random signs cancelling to $1/\sqrt N$ ; in the forrelated case they conspire to $\Omega(1)$ — a difference invisible to any low-degree polynomial, and an $\mathsf{AC}^0$ acceptance probability is essentially such a polynomial on its high levels. The Raz–Tal argument replaces the $\pm1$ bits by weakly correlated Gaussians, interpolates between the distributions, and bounds how fast the acceptance probability moves by its Fourier weight at each degree — Tal's tail bound kills the high degrees where the signal lives, the small per-coordinate correlation the low ones. The next figure states the resource gap.

Figure

The query cost of forrelation on N = 2ⁿ bits, illustrated at N = 2²⁰ ≈ 10⁶: a quantum computer needs 1 query, a randomized classical algorithm needs Θ̃(√N) ≈ 10³, and no polynomial-hierarchy machine succeeds at all — its distinguishing advantage is N^(−Ω(1))

The core equations

The polynomial hierarchy is the classical yardstick: the union of levels $\Sigma_k^{\mathsf{P}}$ , each adding one alternating quantifier over a poly-length string before a poly-time predicate. Level zero is $\mathsf{P}$ , level one $\mathsf{NP}$ ; the tower captures everything reachable by constantly many guess-and-check rounds.

\mathsf{PH}=\bigcup_{k\ge 0}\Sigma_k^{\mathsf{P}},\qquad \Sigma_0^{\mathsf{P}}=\mathsf{P},\quad \Sigma_{k+1}^{\mathsf{P}}=\mathsf{NP}^{\Sigma_k^{\mathsf{P}}} \qquad (1)

where: $\Sigma_k^{\mathsf{P}}$ — level $k$ : $k$ alternating $\exists/\forall$ quantifiers then a poly-time predicate; $\mathsf{NP}^{A}$ — NP machines with an oracle $A$ . Reading: a language is in $\mathsf{PH}$ if it sits at some finite level; relative to an oracle each such language is a quasipolynomial-size, constant-depth $\mathsf{AC}^0$ circuit over the oracle bits — each quantifier a huge fan-in gate, constant alternation depth giving constant circuit depth. Forrelation is the statistic that separates the two worlds: for $f,g:\{0,1\}^n\to\{-1,+1\}$ it is the normalized correlation of $g$ with $\widehat f$ . The prefactor $N^{-3/2}$ makes $\lvert\mathrm{forr}\rvert\le 1$ — this is the amplitude the algorithm produces.

\mathrm{forr}(f,g)=\frac{1}{N^{3/2}}\sum_{x,y\in\{0,1\}^n}f(x)\,(-1)^{x\cdot y}\,g(y)=\frac{\langle \widehat f,\,g\rangle}{N},\qquad \widehat f(y)=\frac{1}{\sqrt N}\sum_x(-1)^{x\cdot y}f(x) \qquad (2)

where: $(-1)^{x\cdot y}$ — Hadamard matrix entry, $x\cdot y$ the mod-2 inner product; $\widehat f$ — orthonormal transform with $\lVert\widehat f\rVert_2=\lVert f\rVert_2=\sqrt N$ (Parseval); $N=2^n$ . Reading: since $\lVert\widehat f\rVert_2\lVert g\rVert_2=N$ , $\langle\widehat f,g\rangle/N$ is the cosine between $g$ and $\widehat f$ — a correlation in $[-1,1]$ , hence for-relation. The quantum algorithm is three Hadamards around two phase queries, making forrelation a measurement probability.

\lvert 0^n\rangle\ \xrightarrow{\,H^{\otimes n}\,O_f\,H^{\otimes n}\,O_g\,H^{\otimes n}\,}\ \lvert\psi\rangle,\qquad \langle 0^n|\psi\rangle=\mathrm{forr}(f,g),\qquad \Pr[0^n]=\mathrm{forr}(f,g)^2 \qquad (3)

where: $H^{\otimes n}$ — $n$ -fold Hadamard, implementing $\widehat{\,\cdot\,}$ ; $O_f:\lvert x\rangle\mapsto f(x)\lvert x\rangle$ — phase oracle. Reading: a single query suffices, and the decision version ( $\lvert\mathrm{forr}\rvert\ge\varepsilon$ or $\approx 0$ ?) has constant bias because $\Pr[0^n]$ jumps from $\sim 1/N$ to $\Omega(1)$ . The classical bound is a distinguishing-advantage inequality: view the acceptance indicator $C$ as a multilinear function of the oracle bits, expand in the Fourier basis, and the advantage is controlled level by level.

\big\lvert\,\mathbb{E}_{\mathcal{D}_1}[C]-\mathbb{E}_{\mathcal{D}_0}[C]\,\big\rvert\ \le\ \sum_{k\ge 1}\varepsilon^{\,k}\,\sqrt{W^{\ge k}[C]}\cdot(\text{combinatorial factor}) \qquad (4)

where: $C$ — circuit acceptance indicator as a multilinear polynomial in the oracle bits; $W^{\ge k}[C]=\sum_{\lvert S\rvert\ge k}\widehat C(S)^2$ — Fourier weight above degree $k$ ; $\varepsilon$ — per-coordinate correlation between $\mathcal{D}_0,\mathcal{D}_1$ . Reading: low degrees are suppressed by $\varepsilon^k$ , so all hinges on high-degree weight — which the next bound crushes. Tal's Fourier-tail bound is the load-bearing input: a constant-depth circuit cannot hide Fourier mass at high degree.

W^{\ge k}[C]\ \le\ 2\cdot 2^{-\,k/\,O\!\left((\log s)^{d-1}\right)}\qquad\text{for } C\in\mathsf{AC}^0\text{ of size }s,\ \text{depth }d \qquad (5)

where: $s$ — circuit size; $d$ — depth; $W^{\ge k}$ — Fourier mass above degree $k$ , exponentially small once $k\gg(\log s)^{d-1}$ . Reading: for quasipoly size and constant depth the crossover degree is $\mathrm{polylog}(N)\ll N$ , so where forrelation stores its signal the circuit is blind. The query upper bound, circuit lower bound, and diagonalization over $\mathsf{PH}$ machines give the theorem.

\exists\,\mathcal{O}:\qquad \mathsf{BQP}^{\mathcal{O}}\ \not\subseteq\ \mathsf{PH}^{\mathcal{O}} \qquad (6)

where: $\mathcal{O}$ — a random (or explicit) oracle encoding one forrelation instance per input length. Reading: no relativizing technique can prove $\mathsf{BQP}\subseteq\mathsf{PH}$ , since it would have to hold in this oracle world, where it is false.

Derivation AHow one quantum query reads off the forrelation

The goal is to prove $\langle 0^n|\psi\rangle=\mathrm{forr}(f,g)$ exactly by tracking the state through the five-stage circuit $H^{\otimes n}\,O_f\,H^{\otimes n}\,O_g\,H^{\otimes n}$ , hiding nothing in a normalization. This is the entire quantum side of the separation: it must produce a number bounded by one whose square is a probability, which we confirm numerically on a small instance.

Step 1. Start in $\lvert 0^n\rangle$ and apply the first Hadamard: $\lvert 0^n\rangle\to \tfrac{1}{\sqrt N}\sum_x\lvert x\rangle$ , the uniform superposition over all $N$ addresses. Why: the only step that touches every oracle location at once — the global view a classical sampler lacks.

Step 2. Apply $O_f$ , giving $\tfrac{1}{\sqrt N}\sum_x f(x)\lvert x\rangle$ , then the second Hadamard. Using $H^{\otimes n}\lvert x\rangle=\tfrac{1}{\sqrt N}\sum_y(-1)^{x\cdot y}\lvert y\rangle$ , the amplitude on $\lvert y\rangle$ becomes $\tfrac{1}{N}\sum_x(-1)^{x\cdot y}f(x)=\tfrac{1}{\sqrt N}\widehat f(y)$ . Why: the Hadamard turns the phase pattern $f$ into the amplitude pattern $\widehat f$ — the register now holds the spectrum of $f$ .

Step 3. Apply $O_g$ (coefficient $\tfrac{1}{\sqrt N}\widehat f(y)g(y)$ on $\lvert y\rangle$ ), then the final Hadamard and read the amplitude on $\lvert 0^n\rangle$ , which collects $\tfrac{1}{\sqrt N}$ from every basis state: $\langle 0^n|\psi\rangle=\tfrac{1}{N}\sum_y\widehat f(y)g(y)=\langle\widehat f,g\rangle/N=\mathrm{forr}(f,g)$ . Why: the last Hadamard performs the inner product $\langle\widehat f,g\rangle$ automatically — interference on $0^n$ is exactly the correlation we wanted.

Step 4. Bound and check. Since $\lvert\langle\widehat f,g\rangle\rvert\le\lVert\widehat f\rVert_2\lVert g\rVert_2=N$ , we get $\lvert\mathrm{forr}\rvert\le 1$ and $\Pr[0^n]=\mathrm{forr}^2\in[0,1]$ . On $f=(+,+,+,-)$ ( $n=2$ ), $\widehat f=(+,+,+,-)$ ; aligning $g=\mathrm{sign}(\widehat f)$ gives $\mathrm{forr}=1$ , $\Pr[0^n]=1$ — one query certifies forrelation with certainty. Why: a real constant, not $\Omega(1)$ in asymptotics; state-vector simulation reproduces amplitude $=1$ exactly. *Verified: $\langle 0^n|\psi\rangle=\langle\widehat f,g\rangle/N$ reproduced by state-vector simulation ( $n=2$ , $\mathrm{forr}=1$ ); Parseval $\lVert\widehat f\rVert_2=\lVert f\rVert_2=\sqrt N$ confirmed.*

Go deeper · Derivation B · 1 minThe forrelation gap — constant versus one over root N

Derivation BThe forrelation gap — constant versus one over root N

The goal is to compute the typical size of $\mathrm{forr}(f,g)$ in the two regimes and exhibit the constant-factor gap the quantum algorithm exploits: under $\mathcal{D}_0$ the forrelation concentrates at $1/\sqrt N$ , while under $\mathcal{D}_1$ it is bounded away from zero. We do the second moment exactly for $\mathcal{D}_0$ and the alignment estimate for $\mathcal{D}_1$ — the $\Omega(1)$ -versus- $1/\sqrt N$ gap that becomes the separation.

Step 1. Independent second moment. With $f,g$ independent i.i.d. $\pm1$ , expand $\mathrm{forr}^2=N^{-3}\sum_{x,y,x',y'}f(x)f(x')(-1)^{x\cdot y+x'\cdot y'}g(y)g(y')$ and take expectations. Why: the second moment is the natural scale of a mean-zero quantity, and independence makes it closed-form.

Step 2. Independence gives $\mathbb{E}[f(x)f(x')]=\delta_{x,x'}$ , $\mathbb{E}[g(y)g(y')]=\delta_{y,y'}$ , so only the diagonal survives (phase $(-1)^{2x\cdot y}=1$ ): $\mathbb{E}_{\mathcal{D}_0}[\mathrm{forr}^2]=N^{-3}\cdot N^2=1/N$ . Why: random signs kill every off-diagonal term, leaving $N^2$ terms out of $N^3$ — the $1/N$ is exact.

Step 3. So the RMS forrelation under $\mathcal{D}_0$ is $1/\sqrt N$ (about $10^{-3}$ for $N=2^{20}$ ): independent oracles are un-forrelated. Why: the forrelated case must clear this noise floor, and the floor shrinks as $N$ grows, so the gap widens.

Step 4. Forrelated alignment. Take $g(y)=\mathrm{sign}(\widehat f(y))$ , so $\mathrm{forr}=\tfrac1N\sum_y\lvert\widehat f(y)\rvert$ . Each $\widehat f(y)$ is a normalized sum of $N$ signs, approximately standard Gaussian, so $\mathrm{forr}\to\mathbb{E}\lvert Z\rvert=\sqrt{2/\pi}\approx 0.798$ . Why: alignment replaces cancellation with a sum of absolute values — the same $N$ terms add coherently, lifting to a constant.

Step 5. The genuine Raz–Tal $\mathcal{D}_1$ avoids exact alignment (not samplable as a valid $\pm1$ oracle) and uses weakly correlated truncated Gaussians with a small $\varepsilon$ , tuned so $\mathbb{E}_{\mathcal{D}_1}[\mathrm{forr}]=\Omega(1)$ while only high-degree Fourier structure separates $\mathcal{D}_0,\mathcal{D}_1$ . Why: the constant gap must come from a legitimate, samplable distribution — a real oracle must realize it. *Verified: $\mathbb{E}_{\mathcal{D}_0}[\mathrm{forr}^2]=1/N$ by Monte Carlo ( $n=6,10,14$ : $0.01542$ vs $0.01562$ ; $0.00098$ vs $0.00098$ ; $0.00006$ vs $0.00006$ ); aligned $\to\sqrt{2/\pi}=0.7979$ ( $n=6,10,14$ : $0.7934,0.7977,0.7979$ ).*

Go deeper · Derivation C · 1 minWhy constant-depth circuits cannot tell the two distributions apart

Derivation CWhy constant-depth circuits cannot tell the two distributions apart

The goal is to bound the advantage of any $\mathsf{AC}^0$ circuit — hence any relativized $\mathsf{PH}$ machine — in distinguishing $\mathcal{D}_0$ from $\mathcal{D}_1$ , showing it is $N^{-\Omega(1)}$ for quasipolynomial size. The strategy is a Gaussian interpolation: connect the distributions by a one-parameter family, differentiate the acceptance probability along it, and control the derivative degree by degree with Tal's bound — the hard half of the theorem, and why it needed a Fourier-analytic breakthrough.

Step 1. Interpolate. Let $C$ be the multilinear extension of the acceptance function and embed both distributions in a family $\mathcal{G}_\rho$ of $\rho$ -correlated Gaussians, $\rho=0$ giving $\mathcal{D}_0$ and $\rho=\rho_\star$ a truncation of $\mathcal{D}_1$ . Then $\Delta(\rho)=\mathbb{E}_{\mathcal{G}_\rho}[C]$ obeys $\Delta(\rho_\star)-\Delta(0)=\int_0^{\rho_\star}\Delta'(\rho)\,d\rho$ . Why: "distinguish" becomes "integrate a derivative," localizing the advantage to how fast $C$ 's mean moves per unit correlation.

Step 2. Differentiate in the Fourier basis. With $C=\sum_S\widehat C(S)\chi_S$ , only correlated coordinates contribute and $\tfrac{d}{d\rho}\mathbb{E}_{\mathcal{G}_\rho}[\chi_S]\sim\lvert S\rvert\,\rho^{\lvert S\rvert-1}\Theta^{\lvert S\rvert}$ , $\Theta=O(1/\sqrt N)$ . Why: correlation propagates through a degree- $k$ monomial as a $k$ -fold product, so each extra degree costs another factor of the tiny signal.

Step 3. Cauchy–Schwarz per level gives $\lvert\Delta(\rho_\star)-\Delta(0)\rvert\lesssim\sum_k\Theta^{k}\sqrt{W^{=k}[C]}$ — the bound of equation (4). Why: this replaces a sum over exponentially many subsets by a sum over the $N$ degrees, weighted by the circuit's Fourier mass.

Step 4. Apply Tal: $W^{\ge k}[C]\le 2\cdot 2^{-k/O((\log s)^{d-1})}$ is tiny once $k\gg(\log s)^{d-1}$ . Low degrees are killed by $\Theta^k=N^{-k/2}$ , high degrees by the tail bound. Why: the two suppressions overlap — no degree has both the distribution difference and the circuit weight large.

Step 5. Summing, $\lvert\mathbb{E}_{\mathcal{D}_1}[C]-\mathbb{E}_{\mathcal{D}_0}[C]\rvert=N^{-\Omega(1)}$ for every quasipoly constant-depth circuit; since a relativized $\mathsf{PH}$ machine is exactly such a family, none distinguishes $\mathcal{D}_0$ from $\mathcal{D}_1$ . Why: the classical lower bound Aaronson conjectured in 2010 and Raz–Tal supplied. *Verified: structure follows Raz–Tal (2018/STOC 2019); the load-bearing input is Tal's $\mathsf{AC}^0$ Fourier-tail bound (CCC 2017). Confirm $\tfrac{d}{d\rho}\mathbb{E}[\chi_S]\propto\lvert S\rvert\rho^{\lvert S\rvert-1}$ and the decay constant $O((\log s)^{d-1})$ .*

Limiting cases

Case	Result	Meaning
Independent oracle ( $\mathcal{D}_0$ )	$\mathbb{E}[\mathrm{forr}]\approx 0,\ \ \mathrm{forr}=O(1/\sqrt N)$	random $f,g$ are essentially un-forrelated; the amplitude on $0^n$ is a cancelling sum of random signs
Forrelated oracle ( $\mathcal{D}_1$ )	$\mathbb{E}[\mathrm{forr}]=\Omega(1)$ , up to $\sqrt{2/\pi}\approx 0.80$	$g$ aligned with $\widehat f$ : the terms add coherently and one quantum query detects it
Quantum query complexity	$Q(\text{Forrelation})=1$	a single query gives constant bias; the optimal quantum advantage (Aaronson–Ambainis)
Classical randomized	$\widetilde\Omega(\sqrt N)$ queries	the best possible classical query bound — matched, so forrelation is the extremal separator
Polynomial hierarchy / $\mathsf{AC}^0$	advantage $\le N^{-\Omega(1)}$	no quasipoly constant-depth circuit distinguishes $\mathcal{D}_0,\mathcal{D}_1$ ; the tower is blind
Deep circuits ( $d\to\infty$ )	Tal's bound degrades	specific to constant depth; unbounded depth (e.g. $\mathsf{P}/\mathsf{poly}$ ) is not separated this way

Common trap“An oracle separation means BQP is not in PH.”

It does not. The theorem is $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{PH}^{\mathcal{O}}$ for some oracle $\mathcal{O}$ — a statement about the relativized world, not the real one. In the real world both classes sit inside $\mathsf{PSPACE}$ , so no inclusion is broken by fiat, and whether $\mathsf{BQP}\subseteq\mathsf{PH}$ holds unconditionally is wide open. What the separation delivers is a barrier: any proof of $\mathsf{BQP}\subseteq\mathsf{PH}$ that relativizes — treats the machines' resources as a black box, as most simulation arguments do — is impossible, since it would have to survive the Raz–Tal oracle world where the containment fails. The lesson mirrors $\mathsf{IP}=\mathsf{PSPACE}$ : a true statement can require non-relativizing methods. (A second trap: the separation is one-directional — $\mathsf{PH}^{\mathcal{O}}$ can also contain problems hard for $\mathsf{BQP}^{\mathcal{O}}$ ; interference and alternation are incomparable black-box resources.)

Worked examples

1 · A forrelation instance by hand (confidence builder)

Take $n=2$ , $N=4$ , $f=(+1,+1,+1,-1)$ on the ordered points $00,01,10,11$ . Find $\widehat f$ , the forrelation with aligned $g=\mathrm{sign}(\widehat f)$ , and $\Pr[0^n]$ ; then contrast an independent $g$ .

Step 1. Transform. With $\widehat f(y)=\tfrac12\sum_x(-1)^{x\cdot y}f(x)$ and $x\cdot y=x_1y_1+x_2y_2 \bmod 2$ : $\widehat f(00)=\tfrac12(1{+}1{+}1{-}1)=1$ , $\widehat f(01)=1$ , $\widehat f(10)=1$ , $\widehat f(11)=\tfrac12(1{-}1{-}1{-}1)=-1$ . So $\widehat f=(+,+,+,-)$ — this $f$ is its own transform, with $\lVert\widehat f\rVert_2^2=4$ (Parseval).

Step 2. Aligned. Take $g=\mathrm{sign}(\widehat f)=(+,+,+,-)$ : $\langle\widehat f,g\rangle=1{+}1{+}1{+}1=4$ , so $\mathrm{forr}=4/4=\mathbf{1}$ . By equation (3) the amplitude on $\lvert 0^2\rangle$ is $1$ , hence $\Pr[0^2]=\mathbf{1}$ : one query certifies the forrelated case with certainty.

Step 3. Independent contrast. For $g=(+,-,-,+)$ , $\langle\widehat f,g\rangle=-2$ , so $\mathrm{forr}=-0.5$ ; for $g=(+,-,+,+)$ , $\langle\widehat f,g\rangle=0$ , so $\mathrm{forr}=0$ . Independent forrelations scatter around $0$ with spread $1/\sqrt N=0.5$ (large only because $N=4$ ). Aligned forr = 1, independent forr scatters as $\pm0.5$ — the gap one query reads.

2 · The asymptotic gap and the query counts

Let $N=2^{20}\approx 1.05\times 10^6$ . Using the verified moments, quantify the gap and the queries each model needs.

Step 1. Noise floor under $\mathcal{D}_0$ : $\mathbb{E}_{\mathcal{D}_0}[\mathrm{forr}^2]=1/N$ , so RMS forrelation is $2^{-10}\approx \mathbf{9.8\times 10^{-4}}$ and $\Pr[0^n]\approx 1/N\approx\mathbf{10^{-6}}$ . Under $\mathcal{D}_1$ , $\mathrm{forr}=\Omega(1)$ (idealized $\sqrt{2/\pi}\approx 0.80$ ), giving $\Pr[0^n]\approx 0.64$ — a bias of $\mathbf{\Omega(1)}$ .

Step 2. Query counts: quantum $Q=\mathbf{1}$ ; classical randomized $\widetilde\Omega(\sqrt N)\approx\mathbf{10^{3}}$ (a thousand-fold gap, growing as $\sqrt N$ ); polynomial hierarchy — advantage $N^{-\Omega(1)}$ , so no $\mathsf{PH}$ machine succeeds at all. Quantum 1, randomized $\sim 10^3$ , $\mathsf{PH}$ super-polynomial — the query gap is the separation.

Physics of the portrait

Forrelation is a single number that is at once a quantum amplitude, a Fourier correlation, and a complexity-theoretic separator — with a story running from 1993 to a 2018 proof.

Origins · 1 minforrelation and how this was discovered

forrelation

conjectured by Aaronson 2010 · settled by Raz and Tal 2018 · quantum query complexity meets the polynomial hierarchy

The question was born with the field. In 1993 Ethan Bernstein and Umesh Vazirani defined $\mathsf{BQP}$ and asked how it relates to the classical hierarchy; the evidence stayed soft, since Shor's factoring lives in $\mathsf{BQP}$ yet also in $\mathsf{PH}$ and witnesses nothing. Scott Aaronson reframed the problem in 2010, reducing " $\mathsf{BQP}$ versus $\mathsf{PH}$ relative to an oracle" to a query-complexity statement and naming the hard instance forrelation. He and Andris Ambainis proved (2015) that it optimally separates quantum from classical queries: one versus $\widetilde\Omega(\sqrt N)$ . But upgrading "classical" to the whole hierarchy required showing even $\mathsf{AC}^0$ circuits cannot tell the two distributions apart — a tool from harmonic analysis. Avishay Tal supplied it in 2017 with a sharp Fourier-tail bound, and in 2018 he and Ran Raz combined it with Gaussian interpolation to prove the advantage is $N^{-\Omega(1)}$ : an oracle relative to which $\mathsf{BQP}\not\subseteq\mathsf{PH}$ — the theorem the 1993 question had awaited for 25 years.

History

1993

— Bernstein and Vazirani define BQP and ask how it sits against the classical hierarchy

2010

— Aaronson reduces BQP versus PH to a query problem and names the forrelation instance

2015

— Aaronson and Ambainis prove forrelation optimally separates quantum from classical queries

2017

— Tal proves the sharp Fourier-tail bound for constant-depth AC0 circuits

2018

— Raz and Tal supply the matching AC0 lower bound, proving BQP is not in PH relative to an oracle

Going further

Texts and papers. Raz, Tal, Oracle Separation of BQP and PH, STOC 2019 / Theory of Computing 18 (2022) — main theorem · Aaronson, BQP and the Polynomial Hierarchy, STOC 2010 — reduction and conjecture · Aaronson, Ambainis, Forrelation, SIAM J. Comput. 47 (2018) — optimal query gap · Tal, Tight Bounds on the Fourier Spectrum of AC0, CCC 2017 — Fourier-tail bound · Bernstein, Vazirani, Quantum Complexity Theory, SIAM J. Comput. 26 (1997) · O'Donnell, Analysis of Boolean Functions (2014) — Fourier toolkit.

Provenance. Forrelation is standardized here to $\mathrm{forr}=N^{-3/2}\sum f(x)(-1)^{x\cdot y}g(y)=\langle\widehat f,g\rangle/N$ (so $\lvert\mathrm{forr}\rvert\le 1$ ), the amplitude-consistent normalization; a source variant with a $1/N$ prefactor differs by $\sqrt N$ and is not the amplitude. Re-verified in this build: $\langle 0^n|\psi\rangle=\mathrm{forr}$ by state-vector simulation ( $n=2$ , $\mathrm{forr}=1$ ); $\mathbb{E}_{\mathcal{D}_0}[\mathrm{forr}^2]=1/N$ by Monte Carlo ( $n=6,10,14$ ); aligned $\to\sqrt{2/\pi}=0.7979$ . Main theorem: Raz–Tal (2018); $\mathsf{AC}^0$ Fourier-tail bound: Tal (2017); optimal gap $Q=1$ vs $\widetilde\Omega(\sqrt N)$ : Aaronson–Ambainis (2018). Class facts ( $\mathsf{PH},\mathsf{BQP}\subseteq\mathsf{PSPACE}$ ; relativized $\mathsf{PH}$ as quasipoly $\mathsf{AC}^0$ ) are standard.

Prerequisites. The Complexity Class BQP · BQP versus P, NP, PSPACE · Quantum Query Complexity · The Polynomial Method for Quantum Lower Bounds. Leads to. BQP is Contained in PP and PSPACE · Quantum Interactive Proofs (QIP).

Ask the tutor: Ask me to walk through the $n=2$ forrelation instance by hand, or to unpack how Tal's Fourier-tail bound turns constant depth into blindness to high-degree structure.

Does this theorem prove quantum computers can do something outside the polynomial hierarchy?

Only inside a black box. Raz and Tal prove $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{PH}^{\mathcal{O}}$ for some oracle $\mathcal{O}$ — relative to it, a one-query quantum problem escapes the entire hierarchy. In the real world the question is still open, and both classes sit inside $\mathsf{PSPACE}$ , so nothing is broken outright. The value is as a barrier: no relativizing technique can ever show $\mathsf{BQP}\subseteq\mathsf{PH}$ . It does not settle the real-world relationship — it tells you which proof methods cannot.

What exactly is forrelation, in one sentence?

Forrelation measures how much one function $g$ correlates with the Fourier (Hadamard) transform of another $f$ : $\mathrm{forr}(f,g)=\langle\widehat f,g\rangle/N$ , a number in $[-1,1]$ near zero for independent $f,g$ and bounded away from zero when $g$ is aligned with $\widehat f$ — correlation after a Fourier transform. It matters because this quantity is exactly the amplitude a three-Hadamard, two-query circuit deposits on the all-zeros string, so a quantum computer evaluates it in one shot while hierarchy machines cannot.

Why does a single quantum query suffice when classical algorithms need √N?

Because the circuit computes a global transform of the whole oracle in one interference step: the two Hadamards turn the phase pattern $f$ into its full spectrum $\widehat f$ across all $N$ amplitudes at once, and the final inner product against $g$ lands on the all-zeros amplitude as $\langle\widehat f,g\rangle/N$ . A classical algorithm reads individual bits; to estimate a global correlation of $N$ terms that is either $1/\sqrt N$ or $\Omega(1)$ it must sample enough to beat the noise floor — provably $\widetilde\Omega(\sqrt N)$ queries. The advantage is evaluating a Fourier correlation versus sampling it.

What is Tal's Fourier-tail bound and why is it the crux of the proof?

A function's "Fourier weight at degree $k$ " measures how much of it lives in $k$ -wise interactions. Tal's 2017 bound says a size- $s$ , depth- $d$ constant-depth circuit has weight above degree $k$ at most $2\cdot 2^{-k/O((\log s)^{d-1})}$ — exponentially small once $k$ exceeds a polylogarithm. It is the crux because the two distributions differ only through high-degree structure (weighted by the tiny signal $\Theta\sim 1/\sqrt N$ ); the circuit has almost no weight there, so it cannot feel the difference — the ingredient Aaronson lacked in 2010.

How does a query lower bound turn into a statement about an oracle?

By diagonalization. Encode one forrelation instance of size $N_m=2^m$ at each length $m$ ; the oracle $\mathcal{O}$ is the concatenation and $L_{\mathcal{O}}$ asks whether that instance is forrelated. The quantum bound puts $L_{\mathcal{O}}\in\mathsf{BQP}^{\mathcal{O}}$ for every choice. Each fixed $\mathsf{PH}$ machine is a quasipoly constant-depth circuit family, wrong at length $m$ with probability $\ge\tfrac12-N_m^{-\Omega(1)}$ ; summing over the countably many machines (Borel–Cantelli), a random $\mathcal{O}$ defeats all of them with probability one — and Raz–Tal also give an explicit construction.

Is forrelation related to quantum-supremacy experiments like random circuit sampling?

They share a moral but not a mechanism. Forrelation is a decision/query problem with a proven, extremal separation against a rich classical class ( $\mathsf{PH}$ ), so it is the cleanest certificate that quantum advantage defeats every strategy in the hierarchy, not just polynomial time. Random circuit and boson sampling are sampling problems whose hardness rests on different, often average-case conjectures. The link is that forrelation-style arguments underpin the belief that hierarchy-based heuristics cannot spoof those experiments — the structural backbone of why "somewhere in $\mathsf{PH}$ " is not enough to simulate a quantum device.