Unconditional Separation of Quantum and Classical Bounded-Error Polynomial Time (BQP != BPP)

Unconditional Separation of Quantum and Classical Bounded-Error Polynomial Time (BQP != BPP)

Definitions and mathematical statement

Both classes decide total binary languages with error at most $1/3$ on every input and polynomial running time. The class $\mathsf{BPP}$ uses classical random bits; $\mathsf{BQP}$ uses uniform quantum computation over a fixed effective universal gate set. The target is \[ \exists L\subseteq\{0,1\}^*:\quad L\in\mathsf{BQP}\ \text{and}\ L\notin\mathsf{BPP}. \] The assertion is unconditional and unrelativized: a separation only in the presence of an oracle or under a conjectured hardness assumption does not meet it.

Formulation and concept references: [S1].

Short English statement

Can one prove, without computational assumptions, that quantum computers efficiently solve some decision problem beyond all efficient randomized classical computers?

Research attempt

Scope, source check, and process.

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. The strategy was to test whether explicitly structured interference supplies a total decision-language separation, while auditing the conversion from sampling and oracle results. All circuits are uniform and use fixed effective gates. Error bounds must hold on every input of the resulting language, including malformed encodings, which may be rejected explicitly.

The classical simulation inclusion $\mathsf{BPP}\subseteq\mathsf{BQP}$ is compatible with the target: fair bits are obtained by Hadamard gates and classical gates by reversible computation with ancillas. What is missing is one total language escaping all polynomial-time randomized deciders. The original Bernstein--Vazirani reference [S1] supplies the model and relativized context. The CCC 2025 work [S2] concerns sampling and functional tasks with its stated assumptions and parameters. Mantri's September 2026 paper [S3] explicitly concerns oracle separations in a Fourier hierarchy. Neither is treated here as the unrelativized total-language separation.

The concrete interference family below lies inside the efficiently simulable stabilizer setting studied in [E1]. Its exact probability formula and sampler are derived here to expose why a large superposition and cancellation do not alone provide classical hardness. This calculation is an illustrative special case, not a new stabilizer-simulation theorem.

Attack: quadratic phases between two Fourier layers.

Let $G$ be a simple graph on $n$ labeled vertices, with adjacency matrix $A\in\mathbb F_2^{n\times n}$, so $A$ is symmetric and has zero diagonal. Define \[ q(x)=\sum_{\{i,j\}\in E(G),\,i<j}x_i x_j\pmod2, \qquad D_q|x\rangle=(-1)^{q(x)}|x\rangle. \] The circuit \[ H^{\otimes n}D_qH^{\otimes n}|0^n\rangle \] has $O(n^2)$ gates: each edge contributes a controlled-$Z$ phase. Such gates have fixed finite decompositions in a universal effective basis, or may be included in that fixed basis. All gates and their order are generated from the input graph in polynomial time. Before the final Hadamards the state has exactly $2^n$ nonzero amplitudes and can be entangled.

On measurement, the amplitude and probability of $y$ are \begin{equation}\label{wsref-0-61-31-39-3a-66-6f-75-72-69-65-72} \alpha_y=2^{-n}\sum_{x\in\mathbb F_2^n}(-1)^{q(x)+y\cdot x}, \qquad p_y=|\alpha_y|^2. \end{equation} The sum appears exponentially large. Squaring it and changing variables gives a much smaller description of the full distribution.

Lemma 19.1: an exact affine-support formula.

Put $K=\ker A$ and $r=\operatorname{rank}A$. Then \begin{equation}\label{wsref-0-61-31-39-3a-64-69-73-74-72-69-62-75-74-69-6f-6e} p_y= \begin{cases} 2^{-r},&y\cdot z=q(z)\text{ for every }z\in K,\\ 0,&\text{otherwise}. \end{cases} \end{equation} The support is a nonempty affine subspace of dimension $r$. It is computable, and its uniform distribution is exactly samplable, in classical polynomial time.

Proof. The polarization identity is \[ q(x+z)+q(x)+q(z)=x^{\mathsf T}Az. \] Expand the square in (a19:fourier) and substitute $x'=x+z$: \[ p_y=2^{-2n}\sum_z(-1)^{q(z)+y\cdot z} \sum_x(-1)^{x^{\mathsf T}Az}. \] If $Az\ne0$, choose a coordinate where it is $1$. Pair each $x$ with $x$ plus the corresponding unit vector; the inner summands cancel. If $Az=0$, all $2^n$ inner summands equal $1$. Therefore \[ p_y=2^{-n}\sum_{z\in K}(-1)^{q(z)+y\cdot z}. \] For $u,z\in K$, polarization gives $q(u+z)=q(u)+q(z)$; also $q(0)=0$. Thus $q$ restricted to $K$ is a linear functional. The last sum is $|K|$ if that functional equals $z\mapsto y\cdot z$, and otherwise is zero by pairing with an element on which they disagree. As $|K|=2^{n-r}$, this proves (a19:distribution).

Every linear functional on $K$ extends to one on $\mathbb F_2^n$: extend a basis of $K$ to a full basis and assign arbitrary values to the added basis vectors. Every such full functional has the form $z\mapsto y\cdot z$. Hence the support is nonempty, with one independent equation for each basis vector of $K$, and has dimension $r$.

Compute a kernel basis by Gaussian elimination, evaluate $q$ on each basis vector, and solve those linear equations for $y$. Obtain a particular solution $y_0$ and a basis $v_1,\ldots,v_r$ for their homogeneous solutions. Output $y_0+\sum_i B_i v_i$ for independent fair bits $B_i$. The map from the $r$ bits to the affine subspace is bijective, so this is the exact required distribution. Every arithmetic operation is over $\mathbb F_2$, and all storage and work are polynomial in the graph encoding. $\square$

An easily missed detail is the affine shift $q|_K$. For a triangle, $K=\{000,111\}$ and $q(111)=1$, so the output is uniform on the four odd-parity strings, not the even-parity subspace. For the empty graph, $K=\mathbb F_2^n$ and the output is always $0^n$. For a single edge on two vertices, $A$ is invertible and all four outputs have probability $1/4$. These cases test both interference cancellation and the normalization.

Consequence for attempted decision separations.

Suppose an input $x$ determines such a graph in polynomial time and a polynomial-time predicate $R(x,y)$ is applied to its measured output. The classical sampler above, followed by $R$, reproduces the quantum acceptance probability exactly. If those probabilities satisfy the total BQP gap on all inputs, the same procedure is a BPP decider for the language. Consequently this entire proposed source of separating decision problems fails, despite exponential state support and nontrivial interference. Adding arbitrary nonquadratic phases changes the calculation: the derivative of the phase need no longer be linear in $x$, and the inner sum need not reduce to the kernel test. No polynomial simulator for that generalization is proved here, but failure of this formula is not a classical lower bound.

A cubic stress test: losing the formula still need not give hardness.

Take $q(x)=x_1x_2x_3$. Its sign function is $1$ at seven inputs and $-1$ at $111$. The Walsh sum is therefore $6$ at $y=000$. At every nonzero $y$, the Walsh sum of the constant function is zero, so changing the one sign gives $-2(-1)^{y_1+y_2+y_3}$. The output probabilities are \[ p_{000}=9/16,\qquad p_y=1/16\quad(y\ne000). \] This full-support, nonuniform distribution cannot have the form in Lemma 19.1. Nevertheless it has an exact constant-time classical sampler: draw four fair bits, map nine of the sixteen outcomes to $000$, and map the other seven bijectively to the seven nonzero strings.

For $k$ disjoint triples, let the phase polynomial be the sum of these $k$ cubic monomials. Both Hadamard layers and the phase operator factor across triples. Consequently the measured distribution is the product of the $k$ displayed distributions and is sampled with $4k$ fair bits and linear work. This family has $2^{3k}$ output strings of positive probability and falls outside the quadratic calculation, yet it remains efficiently classically samplable. Nonquadratic degree is therefore not a hardness criterion by itself. A plausible next candidate must also address coupling between blocks and prove an algorithm-independent lower bound, rather than merely invalidate one Gaussian-elimination formula.

There is also a quantitative version of the sampling-to-decision implication. If a classical polynomial-time sampler approximates each circuit's output distribution within total variation distance $1/12$, the probability of any specified accept event changes by at most $1/12$. A BQP gap of $2/3$ versus $1/3$ becomes at least $7/12$ versus at most $5/12$. On $145$ independent runs, majority voting fails with probability at most $36/145<1/3$ by Chebyshev's inequality: the sample mean has variance at most $1/(4\cdot145)$ and its expectation is separated from $1/2$ by at least $1/12$. Thus such uniform approximate sampling would already suffice for BPP. The converse inference from a sampling hardness claim to a particular total decision-language lower bound requires an additional argument.

Stress test: compiling an oracle can reveal its secret.

Simon's original separation [E2] is explicitly an oracle result. To test a naive conversion to explicit circuit inputs, fix a nonzero $s\in\mathbb F_2^n$ and an index $j$ with $s_j=1$. Define \[ f_s(x)=x+x_j s. \] This linear map satisfies $f_s(x)=f_s(x')$ precisely when $x'=x$ or $x'=x+s$. Indeed its kernel contains $0,s$, and solving $v+v_js=0$ shows these are its only elements. Thus it has the usual two-to-one hidden-XOR collision structure.

Yet a circuit description of this particular family can explicitly record $j$ and the bits of $s$, using $O(n)$ gates to implement the displayed formula. A classical algorithm reading that description recovers $s$ immediately. Even oracle access to this restricted linear family permits learning its whole matrix with $n$ standard-basis queries, so it is not the hard arbitrary-label oracle distribution used in Simon's lower bound. This example does not refute that lower bound. It shows exactly why merely choosing an efficient family satisfying the same collision promise does not transport the lower bound to algorithms reading circuit descriptions.

A valid unrelativized separation would need an explicitly uniform family with a hardness proof against every randomized algorithm allowed to inspect its representation. Hiding the description behind a query interface changes the input model. Listing the full oracle table changes the input length; a runtime polynomial in the table length can be exponential in the number of oracle-address bits without contradicting BPP.

Stress test: a promise cannot be filled in by a threshold rule.

Suppose a quantum procedure distinguishes promised yes- and no-inputs with probabilities at least $2/3$ and at most $1/3$. Declaring every other input a yes-instance exactly when its acceptance probability is greater than $1/2$ defines a total set, but need not give that set a bounded-error quantum decider. On newly assigned inputs the probability may be $1/2$ or differ from it by an exponentially small amount.

For a concrete gap test, generate $m+1$ fair bits and accept when the first bit is $1$ or when all bits are $0$. The probability is $1/2+2^{-(m+1)}$. Sampling this output polynomially often does not turn its comparison with a fair coin into a bounded-error test: couple a Bernoulli sample of bias $1/2+\delta$ to a fair bit with disagreement probability $\delta$. For $R$ independent samples, the transcripts have total variation distance at most $R\delta$ by the union bound. Constant distinguishing advantage therefore requires exponentially many samples when $\delta=2^{-(m+1)}$. This is an obstruction to the proposed generic repetition wrapper, not a lower bound for all algorithms analyzing those simple circuits.

Verification, remaining gap, and outcome.

The accompanying exact checks enumerate every simple graph on up to five vertices, compute all integer Walsh sums in (a19:fourier), and compare their squared probabilities with (a19:distribution). They check the triangle shift, normalization, and all hidden-XOR fibers through dimension six. No empirical timing comparison is used to infer an asymptotic separation.

UNRESOLVED. The main checked result is a complete classical sampler for a structured interference family, together with three explicit scope obstructions: approximate sampling can already simulate decision, oracle compilation may expose structure, and a threshold rule need not preserve a total bounded-error gap. A successful positive continuation needs one total uniform BQP language and an unconditional lower bound against all randomized polynomial-time deciders for that same language. A negative continuation would need a general classical simulation far beyond the quadratic-phase family. Neither has been obtained; the restricted calculations carry no claim of historical novelty.

Sources

• S1 E. Bernstein, U. Vazirani, SIAM J. Comput. 26$5$:1411-1473, 1997. https://doi.org/10.1137/S0097539796300921. Formulation source.
• S2 Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks — Marshall, Aaronson and Dunjko, CCC 2025. https://drops.dagstuhl.de/storage/00lipics/lipics-vol339-ccc2025/LIPIcs.CCC.2025.5/LIPIcs.CCC.2025.5.pdf. Further reference; not a proof endorsement.
• S3 Oracle Separations in the Fourier Hierarchy — Atul Mantri, September 10, 2026. https://arxiv.org/abs/2609.11830. Further reference; not a proof endorsement.
• E1 Scott Aaronson and Daniel Gottesman, Improved Simulation of Stabilizer Circuits, Physical Review A 70 $2004$, 052328. https://arxiv.org/abs/quant-ph/0406196. Primary classical-simulation context; consulted 27 September 2026. The quadratic-phase special case needed here is proved directly.
• E2 Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing 26$5$ $1997$, pp. 1474--1483. https://doi.org/10.1137/S0097539796298637. Primary source; publisher abstract consulted 27 September 2026. Its oracle-input restriction is retained.

Unconditional Separation of Quantum and Classical Bounded-Error Polynomial Time (BQP != BPP)

Definitions and mathematical statement

Both classes decide total binary languages with error at most $1/3$ on every input and polynomial running time. The class $\mathsf{BPP}$ uses classical random bits; $\mathsf{BQP}$ uses uniform quantum computation over a fixed effective universal gate set. The target is \[ \exists L\subseteq\{0,1\}^*:\quad L\in\mathsf{BQP}\ \text{and}\ L\notin\mathsf{BPP}. \] The assertion is unconditional and unrelativized: a separation only in the presence of an oracle or under a conjectured hardness assumption does not meet it.

Formulation and concept references: [S1].

Short English statement

Can one prove, without computational assumptions, that quantum computers efficiently solve some decision problem beyond all efficient randomized classical computers?

Research attempt

Current frontier.

Research check: 27 September 2026. Shor supplies polynomial-time quantum factoring, not a classical lower bound. [E1]. The 2025 sampling/function paper in the original bibliography obtains conditional consequences involving collapse of the polynomial hierarchy. The September 2026 Fourier-hierarchy manuscript concerns oracle separations. Neither statement supplies the unconditional total language required here. [S2], [S3]. We distinguish these carefully before trying to convert a quantum algorithm into a separating language.

Attack route.

There are three distinct missing steps: prove classical hardness of a known quantum task; make an oracle lower bound survive an explicit description of the oracle; or turn a promise separation into a total-language separation. The last two steps are often concealed by a change of encoding. We pursue the first through an exact decision/search reduction, then test the other two against that reduction. All claims of hardness below remain hypotheses.

Attempt: a total factoring threshold language.

Fix a conventional, polynomial-time parsable binary encoding of pairs and put \[ L_{\rm fac}=\{\langle N,t\rangle:N\geq2,\ 2\leq t<N, \ \exists d\ (2\leq d\leq t,\ d\mid N)\}. \tag{19.1} \] Malformed encodings, primes, and out-of-range thresholds are no-instances. The language is total. A bounded-error quantum factorization algorithm, followed by multiplication checks on its output, decides it in quantum polynomial time. Complete factorization reveals the least prime factor; on a prime it reveals no proper factor. The usual amplification and polynomial-time truncation of the factoring algorithm give the required worst-case bounded-error time bound. This uses the established quantum algorithm, not an assumption about its classical complexity. [E1].

Here is the converse reduction with adaptive error accounted for. Suppose $L_{\rm fac}\in\mathsf{BPP}$, and let $N$ be composite of binary length $n$. The predicate in $19.1$, as a function of $t\in[2,N-1]$, changes from zero to one precisely at the least prime divisor $p$ of $N$. Binary search uses at most $n$ decision calls and returns $p$ if all answers are correct. Amplify every call to error at most $1/(12(n+1))$, using fresh random bits. Even though later queries depend on earlier answers, conditional on any past transcript the next query is a fixed input, so its error bound still holds. The union bound makes the entire search succeed with probability at least $11/12$. Division verifies the output; a failed verification can be reported as failure. The running time is polynomial in $n$, including amplification and arithmetic. Consequently \[ \begin{split} &\text{no randomized polynomial-time algorithm finds a proper factor}\\[-2pt] &\text{of every composite with success at least }2/3 \quad\Longrightarrow\quad L_{\rm fac}\in\mathsf{BQP}\setminus\mathsf{BPP}. \end{split} \tag{19.2} \] This is a complete conditional implication, not an unconditional separation. In particular, a negative answer to UnsolvedMath problem 8400004's deterministic factoring question would not supply the stronger randomized lower bound assumed here.

Attempt: a quantitative oracle-to-input audit.

Consider an oracle $f:\{0,1\}^m\to\{0,1\}^m$ in Simon's promise problem: $f(x)=f(y)$ exactly when $y=x$ or $y=x\oplus s$, for a nonzero hidden $s$. The quantum algorithm obtains random linear equations orthogonal to $s$; classical queries require a collision to expose it in the black-box model. The established query-complexity framework, including the distinction between oracle and ordinary machines, is essential here. [E3].

If the entire table of $f$ is the input, its length is $B=m2^m$. A classical algorithm can read and sort the pairs $(f(x),x)$ in time polynomial in $B$, recover a collision, and obtain $s$. Thus an $\exp(\Omega(m))$ query lower bound is not a superpolynomial lower bound in this encoding. A proof that charged time in $m$ while giving the table as an input would have changed the target's size parameter.

If instead a size-$\operatorname{poly}(m)$ circuit $C$ describes $f$, quantum queries can be implemented by reversible evaluation of $C$, with its workspace uncomputed. But a classical algorithm now sees $C$, not just an oracle. As a concrete stress test, take a rank-$m-1$ binary matrix $A$ and $f(x)=Ax$. Its kernel is $\{0,s\}$, so it satisfies Simon's promise. Given the coefficient list defining $C$, Gaussian elimination finds $s$ in polynomial time. The oracle difficulty therefore does not hold uniformly for small descriptions, even though their truth tables have the same two-to-one pattern. A hard explicit family, together with a lower bound against algorithms inspecting its descriptions, is still required.

Attempt: what a legitimate totalization needs.

Suppose a promise problem has a polynomial-time decidable promise set $D$ and a bounded-error quantum algorithm on $D$. Define a total language by rejecting inputs outside $D$. The preliminary membership test for $D$ then gives a BQP algorithm for the totalization, and any BPP decider for it solves the original promise problem. This elementary lemma is sound. It is useless without a cheap test for the entire promise.

For an arbitrary circuit, "acceptance probability lies outside $(1/3,2/3)$" is a semantic promise, not a syntactic property that may be assumed efficiently decidable. Repeating the circuit does not decide membership in that promise with a fixed gap near either endpoint. Likewise, testing Simon periodicity by evaluating every pair uses an exponential number of evaluations in a succinct encoding. Rejecting invalid descriptions is therefore an uncharged operation in the naive construction. The total threshold language $19.1$ avoids that particular problem, but does not avoid the classical-hardness problem.

Stress test.

The reduction handles all composite inputs and all adaptive transcripts; it is not an average-case factoring assertion. Its hypothesis is stronger than merely excluding deterministic factoring. Oracle results and sampling results have not been substituted for a lower bound for $19.1$. The linear Simon example refutes only a universal description-to-oracle transfer principle, not the existence of other hard descriptions. Also, $\mathsf P=\mathsf{PSPACE}$ would imply $\mathsf{BQP}=\mathsf{BPP}=\mathsf P$, by the standard polynomial-space simulation of quantum computation; the target would then be false. [E2]. That dependency is another reason an unconditional hardness assertion here cannot be supplied by a query bound alone.

Outcome.

Outcome: Conditional reduction. The notebook gives a total-language witness conditional on worst-case randomized factoring hardness, with a fully charged adaptive reduction. It also isolates concrete failures of table encoding, succinct-oracle transfer, and unchecked promise totalization. No randomized factoring lower bound has been established. The conditional implication and the special examples are not claimed to be historically new.

Sources

• S1 E. Bernstein, U. Vazirani, SIAM J. Comput. 26$5$:1411-1473, 1997. https://doi.org/10.1137/S0097539796300921. Catalogue formulation source.
• S2 Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks — Marshall, Aaronson and Dunjko, CCC 2025. https://drops.dagstuhl.de/storage/00lipics/lipics-vol339-ccc2025/LIPIcs.CCC.2025.5/LIPIcs.CCC.2025.5.pdf. Catalogue research/status reference; not a proof endorsement.
• S3 Oracle Separations in the Fourier Hierarchy — Atul Mantri, September 10, 2026. https://arxiv.org/abs/2609.11830. Catalogue research/status reference; not a proof endorsement.
• E1 Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing 26$5$ $1997$, 1484--1509; arXiv:quant-ph/9508027. https://arxiv.org/abs/quant-ph/9508027. Added research source. Quantum factoring algorithm; no classical hardness theorem is inferred. Consulted 27 September 2026.
• E2 John Watrous, Quantum Computational Complexity, arXiv:0804.3401v1 $2008$, Sections III.2 and IV. https://arxiv.org/pdf/0804.3401v1. Added research source. Fixed-gate conventions and polynomial-space classical simulation. Consulted 27 September 2026.
• E3 Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing 26$5$ $1997$, 1474--1483, DOI 10.1137/S0097539796298637. https://www.cs.miami.edu/home/burt/learning/csc595.251/s0097539796298637.pdf. Added research source. Primary paper for the hidden-XOR-period oracle problem, not an ordinary language-class separation. Consulted 27 September 2026.