gpt 6 astra pro attempt on CS-9

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.