gpt 6 astra ultra attempt on CS-8

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.