Unconditional Separation of BQP from the Polynomial Hierarchy

Unconditional Separation of BQP from the Polynomial Hierarchy

Definitions and mathematical statement

The polynomial hierarchy is $\mathsf{PH}=\bigcup_{k\ge0}\Sigma_k^{\mathsf P}$, where a language in $\Sigma_k^{\mathsf P}$ has a polynomial-time predicate preceded by $k$ alternating blocks of polynomially bounded existential and universal quantifiers, starting existentially. The target is \[ \exists L\in\mathsf{BQP}\quad L\notin\Sigma_k^{\mathsf P}\text{ for every fixed }k. \] This is a statement about ordinary uniform computation. Exhibiting an oracle relative to which the containment fails is a different statement.

Formulation and concept references: [S1].

Short English statement

Can efficient quantum computation be shown to solve a problem beyond every fixed level of the polynomial hierarchy?

Research attempt

Scope, process, and checked context.

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. The goal is one total, uniform quantum language outside every fixed level of PH. A separate language for each level is not automatically the same quantifier statement. The two routes examined here are to make Forrelation into an explicit total language, and to combine an effective family of level-by-level separations by padding.

Aaronson's original source [S1, S2] motivates the Fourier approach. Raz--Tal [E1] subsequently established an oracle separation of BQP from PH; the oracle remains part of that theorem. Aaronson--Ambainis [E2] supplies the primary Forrelation context. The recent IQP manuscript [S3] explicitly retains oracle access in its separation, while [S4] studies the distinction between language and promise access. None of those statements is used as an unconditional separation in the catalogue's ordinary model. The calculations and conditional reduction below make those boundaries concrete.

An exact Forrelation amplitude.

Let $N=2^n$ and let $f,g:\{0,1\}^n\to\{-1,1\}$. Write $W_{x,y}=(-1)^{x\cdot y}$, with the inner product over $\mathbb F_2$, and put $H=N^{-1/2}W$. Orthogonality gives $H^2=I$. Define \begin{equation}\label{wsref-0-72-33-35-3a-70-68-69} \Phi(f,g)=N^{-3/2}\sum_{x,y}f(x)(-1)^{x\cdot y}g(y). \end{equation} Since $\|f\|_2=\|g\|_2=\sqrt N$ and $H$ is orthogonal, $|\Phi|=N^{-1}|f^{\mathsf T}Hg|\le1$.

Let $D_f|x\rangle=f(x)|x\rangle$, and similarly define $D_g$. The circuit $U=HD_gHD_fH$ satisfies \begin{equation}\label{wsref-0-72-33-35-3a-63-69-72-63-75-69-74} \langle0^n|U|0^n\rangle=\Phi(f,g). \end{equation} Indeed $H|0^n\rangle=N^{-1/2}\sum_x|x\rangle$; the first phase layer inserts $f(x)$, the middle transform inserts $(-1)^{x\cdot y}/\sqrt N$, and the remaining phase and output transform insert $g(y)/\sqrt N$. Summing these contributions proves the formula. This uses two phase queries, without claiming the more delicate one-query implementation for a signed version of the promise.

Measuring all zero has probability $p=\Phi^2$. Therefore the promise $|\Phi|\ge3/5$ versus $|\Phi|\le1/100$ is distinguished with constant bounded error. For an explicit bound, perform 100 independent runs and accept if their all-zero frequency is at least $1/5$. The mean is at least $9/25$ or at most $1/10000$, respectively. Its distance from the threshold is at least $4/25$, and the variance of the empirical mean is at most $1/400$. Chebyshev bounds either error by $25/256<1/3$. This is a complete quantum algorithm for the stated promise, not yet a total decision language or a classical lower bound.

Lemma 35.1: explicit truth tables are classically tractable.

When the two tables of length $N$ are the input, the preceding promise has a deterministic polynomial-time solution, including exact comparisons.

Proof. Compute $Wg$ by the butterfly recurrence \[ W_{2M}\binom{u}{v}=\binom{W_M(u+v)}{W_M(u-v)},\qquad W_1=(1). \] There are $O(N\log N)$ integer additions and subtractions. Every intermediate entry has magnitude at most $N$, so it uses $O(\log N)$ bits. Then compute the integer $Z=f^{\mathsf T}Wg$ with $O(N)$ more operations. Since $\Phi^2=Z^2/N^3$, the comparison to $1/5$ is the exact integer comparison $5Z^2\ge N^3$. Its answer correctly separates the two promised ranges. On intermediate inputs, use the same rule to define a total language in P. The full algorithm has polynomial bit cost in the actual table length $2N$.$\square$

This does not refute a query lower bound. A lower bound of order a positive power of $N$ is compatible with a polynomial-time algorithm on an input of length $N$. Calling $n=\log_2N$ the input size after explicitly listing $N$ entries would be a change of encoding, not an exponential-time lower bound for the listed-table language.

A more plausible route specifies $f$ and $g$ by circuits of size polynomial in $n$. Reversible evaluation computes each phase, applies a sign, and uncomputes its workspace, so (r35:circuit) then has polynomial size in a standard encoding which explicitly lists its $n$ input wires. But a classical competitor now sees the descriptions. A lower bound for queries to arbitrary hidden tables need not survive that information. The next examples exhibit both ends of the promise with transparent circuit descriptions.

Two efficiently recognizable extremes.

For characters $f(x)=(-1)^{a\cdot x}$ and $g(y)=(-1)^{b\cdot y}$, character orthogonality gives \[ (Wg)(x)=N1_{x=b},\qquad \Phi(f,g)=(-1)^{a\cdot b}/\sqrt N. \] Thus these succinct inputs lie in the small-magnitude range once $N\ge10000$. Their exponential table length does not create hardness.

For even $n=2r$, let \[ q(x)=\sum_{j=1}^{r}x_{2j-1}x_{2j}\pmod2, \qquad f(x)=g(x)=(-1)^{q(x)}. \] The two-bit vector is $h=(1,1,1,-1)$, in lexicographic order, and direct multiplication gives $W_4h=2h$. Both the Walsh matrix and $f$ are tensor products of these two-bit objects. Hence $Wf=\sqrt N f$ and $\Phi(f,f)=1$. These inputs attain maximal correlation with only $r$ quadratic phase terms. Replacing $g$ by $-g$ gives $\Phi=-1$ and the same all-zero probability, which tests why this particular circuit uses an absolute-value promise. Again, the family is recognized and evaluated classically from its short description.

These examples neither invalidate the oracle theorem nor establish a classical simulator for every succinct instance. They show why high correlation, low-degree phase structure, and a compact description are not by themselves a lower-bound argument. A successful construction must identify a family on which every PH algorithm fails despite seeing that description.

What makes a promised construction a total BQP language.

Suppose a polynomial-time compiler maps every binary string $x$ to circuits $f_x,g_x$, of polynomially bounded size and number of input wires. If one proves that every output pair satisfies one of the two Forrelation ranges, then \[ L=\{x:|\Phi(f_x,g_x)|\ge3/5\} \] is a total BQP language by the circuit and amplification above. Alternatively, a polynomial-time recognizable set of valid encodings can be used, provided all its elements satisfy the promise and malformed encodings are rejected. This is a sufficient completion criterion; no such hard compiler is constructed here.

Simply placing all intermediate cases on one side of a threshold does not supply this proof. On those cases the quantum test's probability can approach its decision threshold, so a uniform bounded-error guarantee may fail. Conversely, a total classical language defined by an exact threshold on explicit tables, as in Lemma 35.1, need not preserve any claimed oracle hardness. Totality, efficient evaluation, and lower bounds must refer to the same representation and the same language.

Lemma 35.2: effective separations can be combined by padding.

Here is a precise sufficient way to exchange the quantifiers. Suppose a single computable constructor, on $1^k$, halts and outputs a description of a uniform quantum algorithm $M_k$ and positive integers $c_k,d_k$. Assume that $M_k$ decides a total language $L_k$ with error at most $1/3$ and running time at most $c_k(n+1)^{d_k}$ on length $n$, using one fixed finite gate basis. If \begin{equation}\label{wsref-0-72-33-35-3a-6c-65-76-65-6c-73} L_k\notin\Sigma_k^{\mathsf P}\quad(k\ge1), \end{equation} then there is a single total language $L^*\in\mathsf{BQP}\setminus\mathsf{PH}$. The constructor need only be computable, not polynomial-time in $k$.

Proof. Encode triples $(1^k,x,1^t)$ with an unambiguous binary format, for example $1^k0\,1^{|x|}0\,x\,1^t$. Let $N$ be the whole encoding length. Run the constructor for at most $N$ steps, rejecting if it has not halted. If it halts, check that its declared time bound $c_k(|x|+1)^{d_k}$ is at most $N$; otherwise reject. This comparison is polynomial-time even for a large binary exponent: use repeated squaring with all intermediate values capped at $N+1$. On passing both checks, simulate $M_k(x)$ for its declared number of steps and use its answer. Malformed encodings are rejected.

The finite-basis universal simulation has polynomial overhead in the program length and its clock bound, both at most polynomial in $N$. The constructor itself is stopped after $N$ steps. Thus there is one polynomial running-time bound for the whole algorithm. On a rejected format or clock condition its answer is deterministic. Otherwise the hypotheses on the actual constructor ensure that it simulates a total bounded-error decider within its valid bound. Consequently it decides a total language $L^*$ in BQP.

For each fixed $k$, the constructor's runtime and the constants $c_k,d_k$ are fixed finite quantities. Padding $x$ with enough ones makes both clock checks pass using an output of length $O_k((|x|+1)^{\max(1,d_k)})$. This gives a polynomial-time many-one reduction $L_k\le_m^{\mathsf P}L^*$. If $L^*\in\Sigma_m^{\mathsf P}$ for some fixed $m$, choose $k\ge\max(1,m)$. Substituting the reduction into its polynomial-time predicate preserves its $m$ quantifier blocks and polynomial witness bounds. Thus $L_k\in\Sigma_m^{\mathsf P}\subseteq\Sigma_k^{\mathsf P}$, contrary to (r35:levels).$\square$

No constructor or family satisfying these hypotheses is given. The lemma shows that varying polynomial exponents alone are not an insurmountable obstruction: explicit clocks and padding handle them. What cannot simply be assumed from a bare $\forall k\,\exists L_k$ assertion is an effective selection of deciders with valid time bounds and total error guarantees. A finite list of verified separations also cannot substitute for (r35:levels) at every level. These are logical constraints on a possible proof strategy, not a noncomputability theorem about witnesses.

Verification, first gaps, and outcome.

The local exact checks compare the butterfly transform with its defining integer matrix on all small sign tables, verify $W^2=NI$, and compare the amplitude numerator with direct circuit path sums. They check every pair of two-bit sign tables, character examples, and the tensor-product maximal-correlation family. Integer squaring avoids numerical threshold errors. These finite checks support the identities, not a PH lower bound.

UNRESOLVED. The Forrelation route supplies a correct quantum promise algorithm and an exact classical algorithm under the table encoding, then stops at constructing a total succinct family with an unrelativized PH lower bound. The aggregation route gives a proved conditional padding lemma, but stops at an effective family of genuine level separations. Concrete next work would provide the compiler and its all-input gap proof, prove lower bounds against descriptions rather than hidden queries, or construct the uniformly specified family in Lemma 35.2. No unconditional language outside PH is exhibited; the partial arguments carry no claim of novelty or formal proof certification.

Sources

• S1 Scott Aaronson, BQP and the Polynomial Hierarchy, arXiv:0910.4698, Abstract $2009$. https://arxiv.org/abs/0910.4698. Formulation source.
• S2 BQP and the Polynomial Hierarchy. https://www.scottaaronson.com/papers/stoc114-aaronson.pdf. Further reference; not a proof endorsement.
• S3 IQP circuits for 2-Forrelation. https://arxiv.org/abs/2604.15248. Further reference; not a proof endorsement.
• S4 Promises should be taken seriously: On relativization with promise problems. https://arxiv.org/abs/2609.07945. Further reference; not a proof endorsement.
• E1 Ran Raz and Avishay Tal, Oracle Separation of BQP and PH, ECCC TR18-107 $2018$, subsequently STOC 2019. https://eccc.weizmann.ac.il/report/2018/107/. https://eccc.weizmann.ac.il/report/2018/107/download/. Primary separation theorem with its oracle restriction retained.
• E2 Scott Aaronson and Andris Ambainis, Forrelation: A Problem that Optimally Separates Quantum from Classical Computing, STOC 2015, 307--316, Section 2.1 and the algorithm discussion. https://www.scottaaronson.com/papers/forstoc.pdf. Primary Forrelation context. The two-query absolute-value variant and explicit-table calculation used here are derived in the attempt. Additional references consulted 27 September 2026.

Unconditional Separation of BQP from the Polynomial Hierarchy

Definitions and mathematical statement

The polynomial hierarchy is $\mathsf{PH}=\bigcup_{k\ge0}\Sigma_k^{\mathsf P}$, where a language in $\Sigma_k^{\mathsf P}$ has a polynomial-time predicate preceded by $k$ alternating blocks of polynomially bounded existential and universal quantifiers, starting existentially. The target is \[ \exists L\in\mathsf{BQP}\quad L\notin\Sigma_k^{\mathsf P}\text{ for every fixed }k. \] This is a statement about ordinary uniform computation. Exhibiting an oracle relative to which the containment fails is a different statement.

Formulation and concept references: [S1].

Short English statement

Can efficient quantum computation be shown to solve a problem beyond every fixed level of the polynomial hierarchy?

Research attempt

Current frontier.

The established Raz--Tal result is an oracle separation $\mathsf{BQP}^O\not\subseteq\mathsf{PH}^O$, obtained from a distributional query problem; deleting the superscripts is not a valid inference. [E1]. Buzet--Chailloux's August 2026 version implements 2-Forrelation with restricted IQP resources and strengthens an oracle separation, not the present unrelativized statement. [S3], [E2]. Miloschewsky--Podder--Rudolph's September 2026 manuscript constructs an oracle where quantum and deterministic language classes agree while their promise versions do not. Its abstract makes particularly clear why an oracle promise must not silently become a total language. [S4], [E3]. The recent statements were checked; their full proofs were not independently audited. Aaronson's original formulation remains the target here. [S1].

Attack route.

A plausible route is to replace the random oracle functions in Forrelation by uniformly evaluable, succinct functions, then prove that every fixed level of the polynomial hierarchy fails on the resulting total decision problem. This requires both a total gap convention and a lower bound that survives access to the functions' descriptions. Query hardness by itself supplies neither. I test two natural explicit replacements, Fourier-sparse functions and quadratic phases, before attempting a more ambitious derandomization. The calculations below are deductions in this notebook, not new claims about the published oracle construction.

Attempt.

Set $N=2^m$, take $f,g:{\mathbb{F}}_2^m\to\{-1,1\}$, and use the normalization \begin{equation}\label{wsref-0-72-33-35-3a-70-68-69} \Phi(f,g)=N^{-3/2}\sum_{x,y\in{\mathbb{F}}_2^m} f(x)(-1)^{x\cdot y}g(y). \end{equation} This is the inner product of two normalized states after a normalized Hadamard transform, so $|\Phi|\le1$. With reversible evaluation circuits for $f,g$, a Hadamard test estimates this real amplitude to fixed additive accuracy with polynomially many gates in the description lengths. This explains the attraction of a constant-gap promise; it does not define bounded-error answers for inputs arbitrarily close to a threshold. The Forrelation setup and its query interpretation are discussed in [S1] and [E1].

Lemma 35.1 (a sparsity obstruction). Define $\widehat f(y)=N^{-1}\sum_x f(x)(-1)^{x\cdot y}$. If at most $k$ Fourier coefficients are nonzero, then \begin{equation}\label{wsref-0-72-33-35-3a-73-70-61-72-73-65} |\Phi(f,g)|\le\sqrt{k/N}. \end{equation} Proof. Orthogonality gives $\sum_y\widehat f(y)^2=1$, and $\Phi=N^{-1/2}\sum_y\widehat f(y)g(y)$. Cauchy--Schwarz on its support proves the assertion. Thus $\Phi\ge c>0$ requires $k\ge c^2N$. A family with polynomially many Fourier coefficients in $m$ cannot produce constant positive Forrelation in this normalization. This says nothing against succinct functions with exponentially large Fourier support.

Lemma 35.2 (quadratic phases admit exact classical evaluation). Suppose $f(x)=(-1)^{q(x)}$ and $g(y)=(-1)^{r(y)}$, with explicitly given multilinear quadratic polynomials over ${\mathbb{F}}_2$. Then $\Phi(f,g)$ can be computed exactly in time polynomial in $m$, including its sign.

Proof. The numerator of (r35:phi) is $S(Q)=\sum_{z\in{\mathbb{F}}_2^{2m}}(-1)^{Q(z)}$, where $Q(x,y)=q(x)+x\cdot y+r(y)$ is quadratic. Here is an elimination algorithm that does not enumerate the $2^{2m}$ points. If a cross term $uv$ occurs, write, with $z$ denoting the other variables, \[ Q(u,v,z)=uv+uA(z)+vB(z)+C(z), \qquad \deg A,\deg B\le1,\quad\deg C\le2. \] For fixed $z$, direct summation gives \begin{equation}\label{wsref-0-72-33-35-3a-65-6c-69-6d-69-6e-61-74-65} \sum_{u,v\in{\mathbb{F}}_2}(-1)^{uv+uA+vB+C}=2(-1)^{C+AB}. \end{equation} Replace $Q$ by $C+AB$, reducing $z_i^2=z_i$, and record a factor two. The degree remains at most two. If no cross term remains, an affine polynomial has sum zero when any linear coefficient is nonzero, and otherwise sum $(-1)^{Q(0)}2^{\#z}$. At most $m$ eliminations occur; coefficient bookkeeping uses polynomially many bit operations. The answer is an integer divided by $2^{3m/2}$, representable exactly in ${\mathbb{Q}}(\sqrt2)$.

There is a useful independent magnitude check. Let $B(u,v)=Q(u+v)+Q(u)+Q(v)+Q(0)$ have rank $\rho$ on ${\mathbb{F}}_2^d$, $d=2m$. Changing variables from a pair of summation points to their difference gives \[ S(Q)^2=2^d\sum_{h\in\ker B}(-1)^{Q(h)+Q(0)}. \] The exponent restricts to a linear functional on $\ker B$. If it is nonzero the sum vanishes; otherwise $|S(Q)|=2^{d-\rho/2}$. The elimination algorithm supplies the sign that this square identity does not determine. $\square$

The obstruction is not simply the absence of strongly correlated examples. For even $m$, put $q(x)=x_1x_2+\cdots+x_{m-1}x_m$. Summing separately over pairs shows $\widehat f(y)=N^{-1/2}f(y)$. Hence \[ \Phi(f,f)=1,\qquad \Phi\left(f,\,y\mapsto f(y)(-1)^{y_1}\right)=0. \] These have maximally dense Fourier support and a large decision gap, but Lemma 35.2 evaluates both efficiently. Thus merely combining an explicit bent phase with an exact promise does not establish the desired hardness.

Where succinctness and totality intervene. Supplying full tables has input length $2N$. The fast Walsh transform computes (r35:phi) in $O(N\log N)$ arithmetic operations on integers with polynomially bounded bit lengths, so the query lower bound does not become a superpolynomial bound in that encoding. Supplying small circuits instead avoids the table-size cost, but allows classical algorithms to exploit the circuit syntax, as in Lemma 35.2.

For arbitrary circuit descriptions, the test $\Phi\ge a$ versus $\Phi\le b$ with fixed $a>b$ is a promise problem. Defining the remaining inputs to be no-instances does not make the quantum tester a total bounded-error algorithm: amplitudes can lie arbitrarily close to the new yes/no boundary. A successful construction must specify a total language and show its algorithm has error at most $1/3$ on every input, or provide a polynomial-time recognizable encoding whose valid descriptions have a proved gap and whose invalid descriptions receive deterministic answers. The oracle/promise distinction emphasized in [E3] is therefore a live issue here, not a cosmetic qualification.

The strongest plausible continuation is an explicit nonlinear family for which the gap is certified from syntax but no polynomial-hierarchy algorithm decides the associated label. To establish the target it would have to produce one language outside every fixed level, not a sequence $L_k$ with no uniform method for assembling them. No such family or lower-bound argument has been found in this attempt.

Stress test.

The elimination identity is checked in the accompanying script for all quadratic polynomials in four binary variables, against exhaustive summation. The dense examples are checked at even $m=2,4,6$. These are exact integer checks, not tests of a complexity-class separation. The exponent-sum algorithm is restricted to degree two; claiming its extension to arbitrary polynomial-size Boolean circuits would discard the essential invariant that $C+AB$ is still quadratic.

An oracle may contain information with no efficient uniform description. Replacing it by a random seed without bounding both seed length and evaluation cost is not de-oracularization. Fixing a successful seed nonconstructively may introduce advice. Neither of those steps is used here. The desired conclusion would in particular exclude $\mathsf{BQP}\subseteq\mathsf{NP}$, since $\mathsf{NP}\subseteq\mathsf{PH}$. No such unrelativized exclusion follows from either of the lemmas.

\Needspace{8\baselineskip}

Outcome.

Outcome: Exploratory approach with unresolved gap.

The attempt proves two explicit obstructions to simple replacements of the Forrelation oracle: Fourier sparsity rules out a constant signal, whereas quadratic phases allow a constant signal but admit exact polynomial-time classical evaluation. The remaining tasks are a uniform total-gap construction and a lower bound against all fixed hierarchy levels that uses more than oracle indistinguishability. Neither is supplied. The auxiliary calculations are not asserted to be historically new, and no complete separation candidate is claimed.

Sources

• S1 Scott Aaronson, BQP and the Polynomial Hierarchy, arXiv:0910.4698, Abstract $2009$. https://arxiv.org/abs/0910.4698. Catalogue formulation source.
• S2 BQP and the Polynomial Hierarchy. https://www.scottaaronson.com/papers/stoc114-aaronson.pdf. Catalogue research/status reference; not a proof endorsement.
• S3 IQP circuits for 2-Forrelation. https://arxiv.org/abs/2604.15248. Catalogue research/status reference; not a proof endorsement.
• S4 Promises should be taken seriously: On relativization with promise problems. https://arxiv.org/abs/2609.07945. Catalogue research/status reference; not a proof endorsement.
• E1 Ran Raz and Avishay Tal, Oracle Separation of BQP and PH, ECCC TR18-107 $2018$; Journal of the ACM 69$4$ $2022$, article 30. https://eccc.weizmann.ac.il/report/2018/107/. https://doi.org/10.1145/3530258. Oracle scope and distributional statement checked 27 September 2026.
• E2 Quentin Buzet and André Chailloux, IQP circuits for 2-Forrelation, arXiv:2604.15248v2, 24 August 2026, abstract and resource statement. https://arxiv.org/abs/2604.15248v2. Version-specific supplement to [S3]; not an unrelativized separation. Checked 27 September 2026.
• E3 David Miloschewsky, Supartha Podder and Dorian Rudolph, Promises should be taken seriously: On relativization with promise problems, arXiv:2609.07945v1, 7 September 2026, abstract and language/promise separation statement. https://arxiv.org/abs/2609.07945v1. Recent manuscript, statement-level consultation 27 September 2026; not a complete proof audit.