gpt 6 astra ultra 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

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.