BQP versus QMA

BQP versus QMA

Definitions and mathematical statement

A promise problem has disjoint yes- and no-sets; algorithms have no obligations outside their union. In QMA, a uniform polynomial-size quantum verifier $V_x$ receives a polynomial number of witness qubits and obeys \[ x\in A_{\rm yes}\Rightarrow\exists\rho:\Pr[V_x(\rho)=1]\ge2/3,\qquad x\in A_{\rm no}\Rightarrow\forall\rho:\Pr[V_x(\rho)=1]\le1/3. \] The corresponding BQP verifier receives no witness. Determine whether every QMA promise problem has such a BQP algorithm. Fixed effective gate sets, ordinary uniformity, and the promise convention are essential parts of this comparison.

Formulation and concept references: [S1].

Short English statement

Can every problem with efficiently checkable quantum evidence also be decided efficiently without that evidence?

Research attempt

Current frontier.

Literature and model check, 27 September 2026. The relevant definitions and inverse-polynomial-gap local Hamiltonian completeness theorem are in Sections V.1--V.2 of [S1]; they concern promise problems, as does this entry. Strong error reduction preserves the witness length and yields $\mathsf{QMA}\subseteq\mathsf{PP}$, but it does not provide a bounded-error, witness-free simulation [S1], Theorem 10 and Section V.4; [E1]. The April 2026 version of [S4] gives classical-oracle separations involving quantum versus classical proofs and advice. The oracle and advice qualifiers are essential; those results are not unrelativized separations of the two classes here. No complete containment or separation is extracted from the surveyed results.

Attack route.

The verifier is efficiently evaluable, but its optimal witness can occupy an exponentially small part of Hilbert space. Three routes are therefore natural: prepare a high-acceptance state; estimate the spectral distribution of the acceptance operator; or prove that a carefully encoded family defeats all uniform quantum algorithms. The second route gives a provable special case with an explicit success probability. We then test whether amplification, padding, or a black-box lower bound removes its missing spectral-density hypothesis. It does not.

Attempt.

1. The acceptance operator and a physically implementable filter. Fix an input $x$ of length $n$ and a unitary purification $U=U_x$ of its verifier. All discarded registers can be retained until the end. Let the witness space have dimension $D=2^{w(n)}$, let $J:\psi\mapsto\psi\otimes|0^{a(n)}\rangle$ append the work registers, and let $P$ project onto output bit one. Define \[ M=J^*U^*PUJ,\qquad 0\le M\le I. \] The best witness acceptance probability is $\lambda_{\max}(M)$. Thus the QMA promise gives $\lambda_{\max}(M)\ge2/3$ on yes inputs and $\lambda_{\max}(M)\le1/3$ on no inputs. These statements quantify over all witnesses, including entangled states internal to the witness register.

A single filter round starts with a witness and zero work registers, applies $U$, measures $P$, applies $U^*$ on the accepting branch, and tests whether all work registers are zero. A failed test makes the round fail. On the branch where both tests succeed, the unnormalized witness is \[ J^*U^*PUJ\psi=M\psi. \] Hence $j$ successful rounds have Kraus operator $M^j$. If a trial starts with the maximally mixed witness $I/D$, its probability of complete success is exactly \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-35-3a-6d-6f-6d-65-6e-74} p_j=\frac{\operatorname{Tr}(M^{2j})}{D}. \end{equation} The maximally mixed state is efficiently prepared by choosing a uniformly random computational-basis witness, or by discarding half of Bell pairs. Crucially, (eq:30006695:moment) is an unconditional probability of a recorded success event. We have not granted the algorithm free postselection. After a failure the current trial ends, and a new independent trial starts from a fresh mixed witness.

2. An inverse-polynomial spectral-density criterion. Suppose there is a known integer-valued polynomial bound $p(n)\ge1$ such that on every yes input at least $D/p(n)$ eigenvalues of $M$ are at least $2/3$. This hypothesis is stronger than ordinary QMA completeness. Choose the smallest positive integer $j$ satisfying \[ 4^j\ge6p(n),\qquad a_j=\frac1{p(n)}\left(\frac49\right)^j,\qquad b_j=\left(\frac19\right)^j. \] Equation (eq:30006695:moment) then gives \[ p_j\ge a_j\quad\hbox{on yes inputs},\qquad p_j\le b_j\le a_j/6\quad\hbox{on no inputs}. \] Since $j=O(\log p(n))=O(\log n)$, $a_j$ is inverse polynomial. Run independent trials and accept when the observed success fraction exceeds $a_j/2$. For $R$ trials, Hoeffding's elementary Bernoulli bound gives an error at most $\exp(-2R(a_j/3)^2)$ in either case, after weakening the larger yes-case margin. Taking $R=O(a_j^{-2})$ with a sufficiently large absolute constant makes the error at most $1/3$. Each trial uses at most $j$ applications of $U$ and $U^*$ and polynomial-size register tests. Therefore this spectral-density promise problem belongs to $\mathsf{BQP}$.

One can work with a standard fixed gate set with efficient inverse gates; efficient gate-set simulation and an inverse-polynomial error allowance below the displayed probability gap give the same conclusion in the usual fixed-gate convention of the question. This uses ordinary approximate circuit implementation, not arbitrary real constants or input-dependent advice; see the circuit conventions in [S1].

When $w(n)=O(\log n)$, even one accepting eigenvector has inverse-polynomial relative dimension, so the criterion recovers the familiar fact that logarithmic quantum witnesses do not enlarge BQP [E1]. For polynomially many witness qubits, it still applies when the accepting spectral subspace occupies an inverse-polynomial fraction. The criterion and calculation are supplied here, but no historical novelty is asserted.

3. Why amplification and padding do not establish that hypothesis. In the allowed rank-one case $M=|z\rangle\langle z|$, all the moments in (eq:30006695:moment) equal $1/D$. A polynomial spectral filter $F(M)$ that maps $0$ to $0$ and $1$ to $1$ leaves this operator unchanged. Eigenvalue separation is perfect already; the difficulty is access to its one-dimensional image. Thus error reduction alone need not create inverse-polynomial overlap with a mixed starting state. The exponential probabilities in the standard $\mathsf{QMA}\subseteq\mathsf{PP}$ proof express precisely this distinction [S1], Section V.4.

Appending $t$ ignored witness qubits changes $M$ to $M\otimes I_{2^t}$. Both the good rank and the total dimension are multiplied by $2^t$, so their ratio is unchanged. Requiring acceptance of $t$ separate witnesses instead gives $M^{\otimes t}$ for an all-accept test; in the rank-one case the good fraction becomes $D^{-t}$, which is worse.

A thin accepting subspace is not, by itself, evidence of computational hardness. If $z=0^{w(n)}$ is explicitly known, the rank-one witness can be prepared immediately. Indeed, a verifier that accepts only this witness on every input describes a trivial all-yes promise problem. The lemma is a sufficient simulation criterion, not a necessary characterization of BQP. To prove a containment by this route one would need an efficient way to find a good initial state or to transform arbitrary verifiers into spectrally thick ones while preserving the promise. Neither is supplied.

4. An explicit black-box stress test. For comparison, consider a query oracle marking either no label or one unknown label $z\in[D]$. A classical label supplied as a quantum basis witness is checked with one query. A witness-free quantum algorithm requires $\Omega(\sqrt D)$ queries. Here is the hybrid calculation, included to identify exactly what this lower bound uses [E2].

Purify the algorithm, and let $\psi_t$ be its state immediately before query $t$ when the oracle marks nothing. Let $\Pi_z$ project onto query label $z$, including all response and work registers, and put $a_{t,z}=\|\Pi_z\psi_t\|$. Then $\sum_z a_{t,z}^2=1$. Telescoping the marked-oracle computation against the unmarked one gives \[ d_z:=\|\psi^{(z)}_{\rm final}-\psi^{(0)}_{\rm final}\| \le 2\sum_{t=1}^T a_{t,z}. \] To see why only the unmarked states occur on the right, expand the difference of the two products of query-and-processing unitaries one factor at a time, putting marked factors after the differing factor and unmarked factors before it. The later factors preserve the norm, and the differing query has norm at most $2$ on the label-$z$ subspace. Cauchy--Schwarz and summation now give \[ \sum_z d_z^2\le4T\sum_{t,z}a_{t,z}^2=4T^2. \] Bounded-error distinction for every $z$ requires an output-probability difference at least $1/3$. That difference is at most $2d_z$, so $d_z\ge1/6$ and $T\ge\sqrt D/12$.

This is a lower bound with an arbitrary oracle. In the original problem, the verifier's circuit is explicit and the algorithm may exploit its structure. Replacing oracle queries by an explicit circuit does not retain the lower bound merely because the same acceptance matrix occurs. Thus this calculation refutes a uniform black-box witness-removal method, not an unrelativized containment.

Stress test.

The filter is not an illicit implementation of a nonunitary map with unit success probability: every lost branch is charged in (eq:30006695:moment). Neither estimating an exponentially small probability nor conditioning on an exponentially unlikely event is counted as a polynomial-time BQP procedure. The spectrum is not diagonalized explicitly; only the verifier and its inverse are used. Uniformity holds because the polynomial density bound and all repetition counts are fixed algorithms, not advice about the yes instance.

The two directions of the original comparison remain separate. A universal witness-free simulation would also give $\mathsf{NP}\subseteq\mathsf{BQP}$, since classical witnesses are special quantum witnesses. This is not a proof that $\mathsf P=\mathsf{NP}$. Conversely, an oracle query lower bound is not a separation for explicit uniform circuits. The quantum PCP discussion in UnsolvedMath problem 30006691 would connect a constant-gap energy algorithm to this problem, but neither that conjecture nor its restricted obstructions settle it.

Outcome.

Outcome: Exploratory approach with unresolved gap. The attempt proves an explicit BQP simulation under an inverse-polynomial accepting-spectral-density hypothesis, with all filter probabilities and repetitions accounted for. Rank-one, padding, and hybrid-query calculations pinpoint why several natural upgrades fail. These auxiliary results are not asserted to be new complexity-theoretic discoveries.

What is missing is a uniform, non-black-box method removing the density or state-preparation hypothesis for every QMA verifier, or a lower-bound argument against all explicit uniform quantum algorithms for an appropriate QMA promise problem. No such method or lower bound has been established here.

Sources

• S1 John Watrous, Quantum Computational Complexity; author-hosted survey,44pages; not attested identical to arXiv0804.3401. https://cs.uwaterloo.ca/~watrous/Papers/QuantumComputationalComplexity.pdf. Catalogue formulation source.
• S2 CountCrypt: Quantum Cryptography between QCMA and PP. https://eprint.iacr.org/2024/1707. Catalogue research/status reference; not a proof endorsement.
• S3 Separating Quantum Indistinguishability Obfuscation from Falsifiable Assumptions. https://arxiv.org/abs/2608.25195. Catalogue research/status reference; not a proof endorsement.
• S4 Separating Quantum and Classical Advice with Good Codes. https://arxiv.org/abs/2602.09385. Catalogue research/status reference; not a proof endorsement.
• E1 Chris Marriott and John Watrous, Quantum Arthur--Merlin Games, Computational Complexity 14 $2005$, 122--152; arXiv:cs/0506068, strong error reduction and its applications to logarithmic witnesses and PP containment. https://arxiv.org/abs/cs/0506068. Established amplification results, not a QMA=BQP result; consulted 27 September 2026.
• E2 Charles H. Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing 26 $1997$, 1510--1523; arXiv:quant-ph/9701001, Section 3. https://arxiv.org/abs/quant-ph/9701001. Quantum query hybrid argument and its oracle scope; consulted 27 September 2026.