BQP Versus NP: Complete Language-Class Relation

BQP Versus NP: Complete Language-Class Relation

Definitions and mathematical statement

A total language belongs to $\mathsf{BQP}$ if uniformly generated polynomial-size quantum circuits accept yes-inputs with probability at least $2/3$ and no-inputs with probability at most $1/3$. Use precisely the fixed gates, ancillas, and measurement convention in the recorded scope. The class $\mathsf{NP}$ instead uses polynomial-length classical witnesses and deterministic verification. Determine the pair of truth values \[ \left(\mathsf{NP}\subseteq\mathsf{BQP},\quad \mathsf{BQP}\subseteq\mathsf{NP}\right). \] A complete answer distinguishes equality, one of the two strict containments, or incomparability. Oracle access, advice, and arbitrary uncomputable gate constants are excluded.

Formulation and concept references: [S1].

Short English statement

Which is stronger: efficient quantum decision-making or efficient classical verification, or are their powers incomparable?

Research attempt

Exact scope and process.

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026 by recovering the catalogue's recorded scope, checking primary sources, and attacking both containments separately. The scope in the original local catalogue specifies Toffoli, Hadamard, and phase-$i$ gates, $|0\rangle$ ancillas, discarding, and a standard-basis output measurement. A deterministic polynomial-time machine prints $Q_n$ on $1^n$. These are the gates in Watrous [S1], Section III.2. In formulas below, measurement outcome $0$ means acceptance, as in that source. Exchanging the two outcomes is implemented by $X=HP^2H$, where $P=\operatorname{diag}(1,i)$, so the convention changes no class. No gate contains an unspecified real constant.

The original survey discusses promise problems as well as languages. Here only total languages are used: every binary input must have an acceptance probability in the appropriate yes or no interval. The two desired truth values are logically independent targets. The pairs $(1,1),(1,0),(0,1),(0,0)$ mean equality, $\mathsf{NP}\subsetneq\mathsf{BQP}$, $\mathsf{BQP}\subsetneq\mathsf{NP}$, and incomparability, respectively. Showing only one noncontainment does not complete the requested classification.

Context and attack map.

Watrous [S1], Sections IV.3--IV.6, supplies the classical simulation and oracle context. Bennett--Bernstein--Brassard--Vazirani [E1] establish the black-box search obstruction. Its oracle restriction is essential. This attempt examines two possible shortcuts: use a quantum computation path as an NP witness, and obtain a quantum SAT algorithm by treating verification as an unstructured search oracle. The first is refuted by interference; the second has an explicit query lower bound. Neither argument settles the unrelativized class question.

There are elementary constraints on a future answer. BQP is closed under complement by exchanging its output labels. Hence $\mathsf{BQP}\subseteq\mathsf{NP}$ would imply $\mathsf{BQP}\subseteq\mathsf{NP}\cap\mathsf{coNP}$: for $L$ in BQP, its complement is also in BQP and would be in NP. Likewise $\mathsf{NP}\subseteq\mathsf{BQP}$ would put coNP in BQP. If both containments held, NP would equal coNP. These are conditional consequences, not contradictions that can be invoked without proof.

Lemma 16.1: exact path aggregation in the recorded gate set.

Fix an input and a circuit with $q$ qubits, $T$ gates, and $h$ Hadamard gates. Ancillas are counted among the $q$ qubits. Discarded wires may instead be retained and never touched again; tracing them out at the end gives the same output statistics. Thus a pure-state computation on polynomially many wires suffices for this calculation.

Associate a binary choice with the output of each Hadamard. A path $\omega\in\{0,1\}^h$ then determines a final basis string $z(\omega)$ and a phase $i^{e(\omega)}$, with $e(\omega)\in\mathbb Z/4\mathbb Z$. Toffoli gates just update bits. A phase gate on bit $a$ adds $a$ to $e$. A Hadamard taking input $a$ and chosen output $b$ contributes $(-1)^{ab}/\sqrt2$, so it adds $2ab$ to $e$. All path data are computable in polynomial time from $\omega$ and the circuit.

For each final basis string define the Gaussian integer \[ g_z=\sum_{\omega:z(\omega)=z}i^{e(\omega)}=a_z+i b_z, \qquad a_z,b_z\in\mathbb Z. \] Then \begin{equation}\label{wsref-0-61-31-36-3a-70-61-74-68} \langle z|Q|x,0\cdots0\rangle=2^{-h/2}g_z, \qquad p_{\rm acc}=2^{-h}\sum_{z:z_{\rm out}=0}(a_z^2+b_z^2). \end{equation}

Proof. Expand the matrix product gate by gate in the computational basis. Every non-Hadamard gate has exactly one nonzero successor from a basis state, with the update just described. Each Hadamard has the two stated matrix entries. Multiplication along a path gives its phase and denominator; summing paths with the same final basis string gives the first identity. Orthogonality of the full basis, including retained discarded wires, gives the second. In particular, paths ending in different environment strings must not be combined before squaring.$\square$

The numerator in (a16:path) is an exactly specified nonnegative integer. The difficulty is computing or certifying the cancellations inside each $g_z$, not writing down the phase of one term. A guessed path has only $h$ bits, but its existence need not imply even positive acceptance probability.

An explicit false certificate.

Apply $H$ twice to $|1\rangle$ and accept on output $0$. There are two paths to output $0$: through intermediate $0$ with contribution $1/2$, and through intermediate $1$ with contribution $-1/2$. Both are valid gate-by-gate paths, yet their sum is zero and the circuit rejects with certainty. This is a constant-size, fully checked counterexample to "an accepting path certifies quantum acceptance." Requiring a positive path does not repair it: one of the two paths is positive. Counting paths without their phases also fails.

Nor does a list of large individual amplitudes suffice without showing it accounts for the total signed sum. Any proposed NP certificate for general BQP acceptance must establish a sound bound on the whole expression in (a16:path), including potentially omitted cancelling terms. That is a substantive unproved certification theorem, not ordinary NP nondeterminism.

A complete restricted simulation.

If $h=O(\log n)$ for a polynomial-size circuit on inputs of length $n$, there are only polynomially many paths. Enumerate them, group their final strings, and accumulate the integer pairs $(a_z,b_z)$ exactly. Each pair uses $O(h+1)$ bits. The circuit input, final strings, integer arithmetic, and path enumeration all have polynomial cost. Compute (a16:path) and compare it with $1/2$; on a total BQP decider's inputs, its specified gap makes this an exact decision algorithm in P.

More generally, a dictionary simulation is polynomial if at every stage only polynomially many computational basis strings have nonzero amplitude. At a Hadamard, branch each dictionary entry twice, add equal keys, and remove zeros. Keep a common denominator $2^{h_t/2}$ after $h_t$ Hadamards. Integer numerators have polynomial bit length, and Toffoli or phase gates update keys or phases without increasing the support. This proves a conditional simulation under an explicit bound on all intermediate supports. It does not assert that such a bound holds generally. Even $H^{\otimes n}|0^n\rangle$ has $2^n$ nonzero entries, while its computational-basis measurement is easy to sample. Large support is therefore neither an NP certificate nor a hardness proof.

Lemma 16.2: the unstructured-verifier obstruction.

Let an oracle specify either no marked element of $[N]$ or a single marked element $y$. A quantum query may flip an answer bit conditional on whether the query index is marked. Any algorithm distinguishing these cases with error at most $1/3$ on every promised oracle needs at least $\sqrt N/6$ queries.

Proof. Let $|\psi_t^0\rangle$ be the state just before query $t$ when the oracle is identically zero. Write $p_t(y)$ for the squared norm of its component querying index $y$, including all other registers. The marked and unmarked query unitaries differ only on this component, so their difference on this state has norm at most $2\sqrt{p_t(y)}$. Telescope the final marked and unmarked computations by replacing queries one at a time, leaving an unmarked prefix and a marked suffix in each hybrid. The intervening unitaries preserve norms, giving \[ d_y:=\|\psi_{\mathrm{final}}^y-\psi_{\mathrm{final}}^0\| \le2\sum_{t=1}^r\sqrt{p_t(y)}. \] Here every final state may be purified by retaining all workspace. For a measurement, the difference between the probabilities of any event is at most the trace distance of the pure states, which is at most their vector norm distance. The required acceptance-probability difference of at least $1/3$ therefore implies $d_y\ge1/3$. Cauchy--Schwarz gives \[ \sum_{y=1}^N d_y^2 \le4r\sum_{t=1}^r\sum_{y=1}^N p_t(y)=4r^2. \] Thus $N/9\le4r^2$, proving the bound. The trace-distance inequality used above also follows directly by restricting the two pure states to their span and diagonalizing the difference of their rank-one projectors. $\square$

With $N=2^m$ possible witnesses, this is exponential in witness length $m$. It rules out a polynomial-query algorithm which receives no information about the verifier beyond oracle answers. SAT algorithms, however, receive a formula or circuit description. They may inspect clauses, decompose subcircuits, and exploit relations not available to a black-box algorithm. The lemma therefore establishes neither $\mathsf{NP}\nsubseteq\mathsf{BQP}$ nor a lower bound for every quantum algorithm reading a SAT formula. Converting it into such a claim would change the computational model.

Verification and quantifier audit.

The companion script uses exact Gaussian-integer path sums to test the Hadamard cancellation example and all short one-qubit words over $H,P$. It checks normalization by verifying $\sum_z|g_z|^2=2^h$, so no floating-point tolerance conceals cancellation. The search calculation uses only unitary norm preservation, normalization $\sum_y p_t(y)=1$, and Cauchy--Schwarz; it does not assume a particular search algorithm or a random marked item. The integer path simulation groups complete final strings, correctly treating discarded ancillas as an environment.

The classical dictionary algorithm proves a restricted upper bound, not $\mathsf{BQP}\subseteq\mathsf{NP}$ for unrestricted circuits. The query lemma proves a restricted lower bound, not $\mathsf{NP}\nsubseteq\mathsf{BQP}$. Both restrictions survive arbitrarily large finite experiments. Conversely, failure of these two approaches does not exclude a completely different algorithm or certificate representation.

First remaining gaps and outcome.

The quantifiers on the certificate track deserve one further separation. The desired containment would say that for each total language $L$ in BQP there is a fixed deterministic polynomial-time verifier $V_L$ and a polynomial $p_L$ such that \[ x\in L\quad\Longleftrightarrow\quad \exists w,\ |w|\le p_L(|x|):V_L(x,w)=1. \] The verifier and polynomial may depend on the language, but not on an individual input. A universal certificate scheme for every supplied quantum circuit satisfying an acceptance-gap promise would be sufficient in a suitable formulation, but is stronger than simply asserting these language-by-language verifiers. Conversely, exhibiting a short description of the quantum circuit is not itself a verifier: the soundness of the claimed answer still has to be checked in classical polynomial time. The same issue prevents treating a measurement transcript as a certificate. An outcome of a bounded-error experiment can occur on a no-input; verifying that the outcome was possible does not enforce NP's zero false-certificate condition. Repetition makes such outcomes rare but does not remove their existence, which is what an existential witness predicate tests.

UNRESOLVED. On the BQP-to-NP track the missing statement is a polynomial-length, deterministic-verifiable certificate for the appropriate acceptance gap of every total BQP language, with soundness on all no-inputs. The accepting-path proposal is explicitly false. On the NP-to-BQP track, a successful upper bound must exploit verifier syntax beyond black-box search; a successful lower bound must control those syntax-aware algorithms. Neither statement has been established. The checked contributions are exact path bookkeeping, two restricted classical simulations, and a fully derived query obstruction. They are elementary or standard results, with no novelty claim, and leave both truth values in the requested pair undetermined.

Sources

• S1 John Watrous, Quantum Computational Complexity, arXiv:0804.3401v1; language questions corroborated by Scott Aaronson lecture notes. https://arxiv.org/pdf/0804.3401v1. Formulation source.
• S2 Complexity Theory, Lecture 25: Quantum Computing $2$ — Markus Krötzsch, January 27, 2025. https://iccl.inf.tu-dresden.de/w/images/4/4d/CT2024-Lecture-25-overlay.pdf. Further reference; not a proof endorsement.
• S3 Introduction to Quantum Information Science lecture notes — Scott Aaronson. https://www.scottaaronson.com/qclec.pdf. Further reference; not a proof endorsement.
• S4 Random Permutations in Computational Complexity — Hitchcock, Sekoni and Shafei (November 11, 2025). https://arxiv.org/abs/2511.08786. Further reference; not a proof endorsement.
• E1 Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing 26$5$ $1997$, pp. 1510--1523. https://arxiv.org/abs/quant-ph/9701001. https://doi.org/10.1137/S0097539796300933. Primary source for the quantum search/oracle obstruction; consulted 27 September 2026. The particular hybrid estimate used here is proved in Lemma 16.2 and is not applied to algorithms with explicit verifier syntax.

BQP Versus NP: Complete Language-Class Relation

Definitions and mathematical statement

A total language belongs to $\mathsf{BQP}$ if uniformly generated polynomial-size quantum circuits accept yes-inputs with probability at least $2/3$ and no-inputs with probability at most $1/3$. Use precisely the fixed gates, ancillas, and measurement convention in the recorded scope. The class $\mathsf{NP}$ instead uses polynomial-length classical witnesses and deterministic verification. Determine the pair of truth values \[ \left(\mathsf{NP}\subseteq\mathsf{BQP},\quad \mathsf{BQP}\subseteq\mathsf{NP}\right). \] A complete answer distinguishes equality, one of the two strict containments, or incomparability. Oracle access, advice, and arbitrary uncomputable gate constants are excluded.

Formulation and concept references: [S1].

Short English statement

Which is stronger: efficient quantum decision-making or efficient classical verification, or are their powers incomparable?

Research attempt

Current frontier.

Research check: 27 September 2026. Watrous's Section III.2 explicitly uses the Toffoli, Hadamard, phase-$i$, ancillary and erasure gates recorded in this entry. His survey frequently uses promise problems, whereas the present target restricts to total languages; that restriction is maintained below. [S1]. The 2025 random-permutation manuscript strengthens a separation relative to certain random permutations, not an unrelativized separation. [S4]. The established black-box search lower bound also has an oracle hypothesis. [E1]. None decides either of the two requested containments for the ordinary classes.

Attack route.

For $\mathsf{NP}\subseteq\mathsf{BQP}$ one might exploit more than the unstructured witness-search oracle. For the opposite containment one might compress the cancellations in a quantum path sum into a classically checkable certificate. These are different tasks; a breakthrough on one would not answer the other. We investigate both at the exact fixed-gate level, locating the missing structural hypothesis in each.

Attempt: how far black-box witness search goes.

Let a verifier have $m$ witness bits and put $R=2^m$. Regard its accepting set temporarily as an arbitrary Boolean oracle on $R$ addresses. Compare the all-zero oracle with the oracle having its unique marked address at $j$. Purify the algorithm, defer measurements, and let $q_{t,j}$ be the probability of querying address $j$ immediately before query $t$ in the all-zero computation. A telescoping hybrid, replacing queries in an order that leaves the prefix equal to the all-zero computation, gives \[ \|\psi_j-\psi_0\|\leq2\sum_{t=1}^T\sqrt{q_{t,j}}. \] The suffix is unitary and does not increase the norm; a changed query acts only on the address-$j$ subspace and has operator norm difference at most two. Cauchy--Schwarz, followed by $\sum_jq_{t,j}=1$, yields \[ \sum_{j=1}^R\|\psi_j-\psi_0\|^2\leq4T\sum_{t,j}q_{t,j}=4T^2. \tag{16.1} \] For bounded-error distinction, the measured acceptance probabilities differ by at least $1/3$ for every $j$. Their difference is at most trace distance, which for pure states is at most their Euclidean distance. Hence $T\geq\sqrt R/6$. This is the standard hybrid obstruction, derived here with the quantities charged explicitly. [E1].

It rules out a universal polynomial-query search using only verifier calls. It does not rule out a polynomial-time algorithm that reads the verifier's description. For example, the circuit testing $y=j$ has a unique witness but exposes $j$ as its hardwired bit pattern. An oracle algorithm cannot read that pattern; a circuit-input algorithm can. To separate NP from BQP one must build a uniformly NP-verifiable family where even description-aware quantum computation fails. Formula $16.1$ does not construct that family.

Attempt: exact interference accounting in the other direction.

Fix a total-language BQP circuit $Q_n$ and input $x$. Move all erasures to the end by retaining their unused wires, and allocate all $|0\rangle$ ancillas initially. This leaves a pure unitary computation on polynomially many qubits, without changing the measured output probability. Let $h$ be its number of Hadamard gates. Index paths by their successive Hadamard output bits $a\in\{0,1\}^h$. Deterministic propagation through the Toffoli gates computes the final basis string $z(a)$ and the accumulated phase $i^{e(a)}$, with $e(a)\in{\mathbb{Z}}/4{\mathbb{Z}}$, in polynomial time. The Hadamard signs contribute phases $1$ or $-1$ and are included in $e$. Thus the amplitude at $z$ and the acceptance probability are exactly \[ \alpha_z=2^{-h/2}\sum_{a:z(a)=z}i^{e(a)},\qquad p_x=2^{-h}\!\sum_{a,b}\! 1_{z(a)=z(b)}1_{z(a)_{\rm out}=1}i^{e(a)-e(b)}. \tag{16.2} \] Conjugate pairs $(a,b)$ cancel imaginary parts. In particular \[ 2^hp_x=G_x:=\sum_{a,b} 1_{z(a)=z(b)}1_{z(a)_{\rm out}=1} \cos\!\left(\frac{\pi(e(a)-e(b))}{2}\right) \tag{16.3} \] is an integer, expressed as a sum of polynomial-time computable values in $\{-1,0,1\}$ over $2^{2h}$ pairs. The gate normalization in $16.2$ is important: using $2^{-2h}$ would give the wrong probability. The path-sum/classical-simulation viewpoint is established; this explicit integer form follows directly from the fixed gates. [S1].

Although $G_x$ has at most $h+1$ bits because $0\leq G_x\leq2^h$, merely writing down that integer is not a certificate of its correctness. Determining a count can be difficult even when its answer has few bits. A specific sufficient certificate lemma would be: for every such uniform total-language circuit family there is a deterministic polynomial-time verifier accepting a polynomial-length certificate exactly when \[ G_x>2^{h-1}, \tag{16.4} \] on the inputs of that family. The BQP gap makes this equivalent to membership in its language. Establishing this lemma for all families would imply $\mathsf{BQP}\subseteq\mathsf{NP}$; it is not established here. No assertion is made for arbitrary circuit descriptions with intermediate acceptance probabilities.

Attempt: a tractable cancellation representation and its failure.

A useful restricted test is to partition the path pairs in $16.3$ into polynomially many disjoint, explicitly described affine subspaces of ${\mathbb{F}}_2^{2h}$ on each of which the summand is a known constant. Gaussian elimination computes each cell's size, and summing its constant times $2^{\dim\text{cell}}$ computes $G_x$ in polynomial time. If the partition is constructed uniformly in polynomial time, this gives a P simulation, not just an NP certificate. Given only a purported partition, however, checking that the summand is constant on each entire cell is itself a universal assertion. Sampling points does not furnish deterministic soundness of a certificate.

Moreover there is no automatic low-degree closure for symbolic paths. Retain bits $a_1,\ldots,a_r$ and reversibly compute successive prefix products into new zero ancillas using Toffoli gates. The final bit is $a_1a_2\cdots a_r$, whose unique multilinear polynomial over ${\mathbb{F}}_2$ has degree $r$, despite every gate having degree at most two. The circuit is small and the function easy; it refutes bounded-degree closure, not efficient quantum simulation in general. It also shows why simply tracking a fixed list of pairwise correlations is not a closed method.

Stress test.

The query proof concerns arbitrary oracles and cannot be substituted for an ordinary lower bound. The path-sum formula handles phase-$i$ and traced-out wires, but produces an exponentially long signed count, not a polynomial certificate. A yes-certificate for a particular guessed value must be sound on every no-input, not merely plausible numerically. Finally, if both containments held, closure of BQP under complement would imply $\mathsf{NP}=\mathsf{coNP}$: the complement of any NP language would belong to BQP and hence NP. This additional consequence does not follow from either containment alone and is a useful dependency warning.

Outcome.

Outcome: Exploratory approach with unresolved gap. Both directions have been investigated separately. We obtain an exact black-box barrier, a fixed-gate signed-count formula, and a restricted tractable representation. Neither description-aware search hardness nor the required universal cancellation-certificate lemma is proved. Thus neither requested truth value, and consequently no complete language-class relation, is claimed to have been determined.

Sources

• S1 John Watrous, Quantum Computational Complexity, arXiv:0804.3401v1; language questions corroborated by Scott Aaronson lecture notes. https://arxiv.org/pdf/0804.3401v1. Catalogue formulation source.
• S2 Complexity Theory, Lecture 25: Quantum Computing $2$ — Markus Krötzsch, January 27, 2025. https://iccl.inf.tu-dresden.de/w/images/4/4d/CT2024-Lecture-25-overlay.pdf. Catalogue research/status reference; not a proof endorsement.
• S3 Introduction to Quantum Information Science lecture notes — Scott Aaronson. https://www.scottaaronson.com/qclec.pdf. Catalogue research/status reference; not a proof endorsement.
• S4 Random Permutations in Computational Complexity — Hitchcock, Sekoni and Shafei (November 11, 2025). https://arxiv.org/abs/2511.08786. Catalogue research/status reference; not a proof endorsement.
• E1 Charles H. Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing 26$5$ $1997$, 1510--1523; arXiv:quant-ph/9701001. https://arxiv.org/abs/quant-ph/9701001. Added research source. Quantum black-box lower bounds; the hybrid calculation here keeps the oracle hypothesis explicit. Consulted 27 September 2026.