QMA versus QCMA Problem

QMA versus QCMA Problem

Definitions and mathematical statement

A QMA verifier is a uniform polynomial-time quantum computation receiving a polynomial-size quantum witness. A QCMA verifier has the same quantum computational power but receives only a polynomial-length classical bit string. Both use completeness at least $2/3$ and soundness at most $1/3$, with soundness quantified over every allowed witness on no-inputs. The question is \[ \mathsf{QMA}\stackrel{?}{=}\mathsf{QCMA}. \] The catalogue states a language formulation; a promise-problem version should be labeled separately rather than silently substituted. An oracle separation does not determine the ordinary unrelativized relation.

Formulation and concept references: [S1].

Short English statement

Can quantum evidence always be replaced by classical evidence without sacrificing efficient quantum verification?

Research attempt

Current frontier.

The cited Bostanci--Haferkamp--Nirkhe--Zhandry manuscript proves a classical-oracle separation, in a language formulation, and explains why witness-state complexity alone does not settle the unrelativized question. Theorem 1.1 and the accompanying discussion were checked in its January 2026 revision. [S1] The April 2026 revision of Bostanci--Huang--Vaikuntanathan gives another classical-oracle separation using coding ideas. [E1] Neither statement determines the relation of ordinary QMA and QCMA. We keep the supplied language convention and do not turn a promise-only spectral problem into a total language without a valid construction.

Attack routes.

To prove equality, one could compress an accepting quantum witness into a classical description of a preparable state. This needs existence of a succinct accepting state, not succinctness of every quantum state. To prove separation, one could try to force highly complex witnesses, but must also exclude a different QCMA verifier for the same language. A third possibility is to remove the oracle from the recent constructions; it requires an efficiently computable explicit object retaining the adversary lower bound, rather than an oracle chosen by diagonalization. The compression route is developed here to quantify one sufficient notion of classical describability and test its limitations.

Attempt I: acceptance operators and a compression lemma.

Fix an input $x$ of length $n\geq2$. A verifier acting on $m=m(n)$ witness qubits induces a positive operator $0\leq A_x\leq I$, with acceptance probability $\langle\psi,A_x\psi\rangle$ for a pure witness. Maximizing over density matrices gives $\|A_x\|$: diagonalize $A_x$, and observe that the expectation is a convex combination of its eigenvalues. Thus completeness is an eigenvalue-existence assertion, while soundness quantifies over the entire unit sphere.

Suppose that for every yes-input there is an accepting pure witness $\psi$, and a polynomial-size quantum circuit $U$, such that the probabilities \[ p_z=|\langle z,U^*\psi\rangle|^2 \quad(z\in\{0,1\}^m) \] have Shannon entropy $\sum_zp_z\log_2(1/p_z)\leq C\log_2 n$, where $C\geq1$ and the polynomial size bounds are fixed for the language (enlarging $C$ if necessary). The circuit $U$ need not be computable from $x$; it may be part of the classical witness.

Entropy-compression lemma. Under this extra hypothesis the language has a QCMA verifier.

Take $\delta=1/576$ and let $B=\{z:p_z\geq n^{-C/\delta}\}$. There are at most $n^{C/\delta}$ such strings. For $z\notin B$, $\log_2(1/p_z)>(C/\delta)\log_2 n$, so the entropy bound implies \[ \sum_{z\notin B}p_z\leq\delta. \] The normalized truncation $\phi$ of $U^*\psi$ to $B$ satisfies $|\langle\phi,U^*\psi\rangle|^2\geq1-\delta$. The trace distance between these pure states is at most $\sqrt\delta=1/24$. Therefore \[ \langle U\phi,A_xU\phi\rangle\geq\frac23-\frac1{24}. \] A classical description can list the support strings and their complex amplitudes rounded to inverse-polynomial accuracy. If there are $s$ entries, rounding each real and imaginary part within $O(1/s)$ and renormalizing makes the Euclidean error a fixed small constant; choosing more bits makes the resulting trace distance below $1/24$. The bit count is $O(s(m+\log s))$, hence polynomial in $n$.

Such a sparse state can be prepared with polynomial overhead: prepare a register indexing its $s$ entries by successive controlled rotations, compute the listed support string reversibly, and erase the index using the inverse lookup on the distinct strings. Rotations and the supplied circuit can be approximated over a fixed universal gate set within the chosen total error. The quantum verifier checks the syntax and size bounds of the description, performs this preparation, and runs the original verifier. Its yes-acceptance probability is at least $7/12$. On no-inputs every resulting physical state is accepted with probability at most $1/3$, whether or not the claimed amplitudes or basis have any relation to the entropy condition. Malformed descriptions are rejected. Independent repetition with an intermediate threshold amplifies this constant gap to the standard parameters. This proves the lemma without requiring a classical algorithm to find the good support. QCMA completeness requires existence of the classical witness, not efficient discovery of it.

Attempt II: could spectral structure supply the hypothesis?

The lemma suggests seeking a polynomial-description basis in which some vector from the accepting spectral subspace has logarithmic measurement entropy. One might hope that the succinct circuit defining $A_x$ forces this. No such implication has been proved here. Describing an operator by a short circuit does not automatically describe one of its extremal eigenvectors by a short state-preparation circuit.

Two examples prevent weaker surrogate statements from closing the gap. For $A=|+\rangle\langle+|^{\otimes m}$, the top eigenvalue is one but every computational-basis vector has acceptance $2^{-m}$. A verifier restricted to basis-state witnesses fails completely. Nevertheless $|+\rangle^{\otimes m}$ is prepared by $m$ Hadamard gates, so classical verification is easy. Large entropy in one chosen basis is therefore not a witness-complexity lower bound. In the Hadamard basis its entropy is zero, exactly as the compression lemma allows.

Conversely, a counting argument shows that most states do not have polynomial-size descriptions, but gives no efficiently verifiable language for which all QCMA protocols fail. It must first link those states to an explicit verifier's accepting subspace, and then exclude alternative classical-witness verification strategies. The oracle separation source explicitly discusses this obstacle. [S1]

A spectral-gap projection does not solve the state-preparation issue either. Starting with a maximally mixed state and projecting onto an accepting subspace of dimension $r$ among $2^m$ dimensions has success probability $r/2^m$. Even a perfectly implementable projection is not a polynomial-time preparation when this probability is exponentially small. Renormalizing after projection is postselection, not a free operation in a QMA-to-QCMA simulation.

Stress test.

The entropy hypothesis is only sufficient; it is not claimed to characterize QCMA. The polynomial exponent $C/\delta$ is fixed once the language is fixed. Letting it grow with $n$ would destroy the complexity bound. The preparation argument supplies an actual state with a controlled trace-distance error and handles all classical certificates on no-inputs, not only honest descriptions.

The existing oracle constructions are evidence that a fully relativizing equality proof cannot succeed, but they are not unrelativized lower bounds. Nor does a separation between promise classes automatically supply the language separation selected here. Finally, an ordinary QMA/QCMA separation would imply $\mathsf P\ne\mathsf{PSPACE}$, using $\mathsf P\subseteq\mathsf{QCMA}\subseteq\mathsf{QMA}\subseteq \mathsf{PSPACE}$; the exponential-dimensional acceptance operator can be handled in polynomial space by the standard quantum-verification simulation. Thus making the last lower-bound step explicit would have major additional consequences, not merely establish an encoding fact.

The companion script checks the rank-one acceptance example and the trace-distance/truncation inequality on finite rational test vectors. Those checks certify neither an entropy bound for all QMA languages nor a complexity-class separation.

Outcome.

Outcome: Exploratory approach with unresolved gap.

A precise accepting-witness entropy condition has been shown to imply QCMA verification, with polynomial encoding size, preparation error, and soundness handled explicitly. No argument supplies that condition for every QMA language; it is not necessary for every possible QCMA protocol either. The basis-state and postselection shortcuts fail for specified reasons. No equality, separation, or novelty claim is made.

Sources

• S1 John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry, Separating QMA from QCMA with a classical oracle, Introduction. https://eccc.weizmann.ac.il/report/2025/176/revision/1/download/. Catalogue formulation source.
• E1 John Bostanci, Andrew Huang, and Vinod Vaikuntanathan. Separating Quantum and Classical Advice with Good Codes, ECCC TR26-020, revision 1, 12 April 2026. Abstract and introduction; the separation is relative to a classical oracle. https://eccc.weizmann.ac.il/report/2026/020/. Consulted 27 September 2026 for the indicated result or scope.