Quantum computing · Theory (AI-assisted)
Separating QMA from the QCMA Hierarchy via a Switching Lemma for Polynomials
arXiv:2611.23693v1 ↗PDF ↗Submitted 18 November 2026
- Question
- QMA allows a quantum proof and QCMA only a classical one. Recent classical-oracle separations of the two place the separating problem in AM, so it reduces with randomness to an NP problem whose proofs are classical. Does some problem need a quantum proof so essentially that even the hierarchy of iterated QCMA oracle reductions, QCMAH, cannot decide it?
- Result
- A classical oracle relative to which QMA is not contained in QCMAH. The same technique gives oracles relative to which PromiseQCMA collapses to PromiseP while PromiseQMA stays strictly larger, and relative to which PromiseQMA collapses to PromiseP while PromisePP does not, which answers a question of Aaronson, Ingram and Kretschmer. The main tool is a switching lemma for bounded polynomials: under a random restriction, a bounded polynomial of degree \(T\) is \(\eta\)-approximated by a decision tree of depth less than \(t\) except with probability at most \((O(pT^2)/\eta)^t\), independent of the number of variables.
The paper in detail
Two natural quantum versions of NP differ in the proof they accept: QMA verifiers receive a quantum state, QCMA verifiers a classical string. Aaronson and Kuperberg separated them relative to a quantum oracle in 2007, and classical-oracle separations followed only recently, from spectral forrelation and from a variant of the Yamakawa–Zhandry code-intersection problem. Both rest on the set-size-estimation framework of Fefferman and Kimmel, which puts the separating problem in AM. Since \(\mathsf{AM}\subseteq\mathsf{BPP}^{\mathsf{NP}}\) relativizes, those problems reduce with randomness to an NP problem, whose proofs are classical. The paper asks for a separation that survives all such reductions, using QCMAH, the union of \(\mathsf{QCMA}\), \(\mathsf{QCMA}^{\mathsf{QCMA}}\) and so on, as the analogue of the polynomial hierarchy.
The starting point is the Fefferman–Kimmel extractor. If a QCMA verifier accepts on a large hidden set \(O\) with witness \(w\) and rejects on the empty set, then running it on an oracle that marks only the points found so far, and measuring a random query, finds a new point of \(O\) with probability at least \(1/\mathrm{poly}\). Repeating extracts many points from the witness alone; guessing \(w\) costs only \(2^{-|w|}\), whereas a random YES instance is unlikely to contain any fixed large set, a contradiction when \(|w|\) is polynomial. Wang observes that the extractor only needs the restricted problem to have large decision-tree depth, and that it works for any bounded polynomial once query weights are replaced by fractional certificates. This is a switching lemma.
A QCMA algorithm is an OR, over witnesses, of quantum query algorithms, and Agarwal and Ben-David showed that a level-\(d\) QCMAH algorithm becomes a depth-\(2d\), quasipolynomial-size circuit of unbounded OR gates and quantum query gates. Restrictions are applied level by level, using nested random sets \(D_0\supseteq D_1\supseteq\dots\supseteq D_d\) in which a fixed set is unlikely to survive into the next level; the polynomial switching lemma collapses query gates into shallow decision trees, and Håstad's lemma collapses the ORs. The separating problem asks whether \(f=R\lor\mathbf 1_D\), with \(R\) a random function and \(D\) a code-intersection set, or \(f=R\). After the restriction that leaves \(D\) free and sets everything else to \(R\), the circuit is constant with high probability, so it cannot accept the YES instance and reject the NO instance. A QMA verifier, on the other hand, decodes a point of \(D\) from a quantum witness.
The collapse results need a convention for oracles that answer out-of-promise queries. Wang evaluates a circuit of partial functions by its consistent completions, in which each gate's undefined outputs are fixed once and reused wherever the gate appears, and assigns those values during the diagonalisation. The open problems include a random-oracle separation, the ClonableQMA hierarchy, QMA-completeness of a succinct version of the code-intersection problem, and whether the switching lemma can simplify Turturean's recent proof of the Aaronson–Ambainis conjecture.
Transferable methods
A switching lemma for bounded polynomials, proved with a blind sampler
To show that a random restriction usually leaves a function with a shallow decision tree, build a sampler that never sees the random set but, whenever the tree is deep, lands inside the set unusually often. Because the sampler cannot know the set, the restriction distribution caps how often it can succeed, and comparing the two probabilities bounds the bad event.
Fractional block sensitivity gives each input \(x\) weights \(c_{i,x}\ge0\) with \[|f(x)-f(y)|\le\sum_{i:\,x_i\ne y_i}c_{i,x},\qquad\sum_ic_{i,x}\le\mathrm{fbs}(f),\] the dual of a linear program over blocks of flipped bits. For a bounded polynomial of degree \(T\), \(\mathrm{fbs}(f)=O(T^2)\). The restriction \(\rho_{x,D}\) leaves the coordinates in a random set \(D\) free and fixes the rest to \(x\). \(D\) is \(t\)-wise \(p\)-bounded when \(\Pr[S\subseteq D]\le p^{|S|}\) for every \(|S|\le t\).
The sampler starts at \(x_0=x\) and for \(k=1,\dots,t\) picks \(i_k\) with probability \(c_{i,x_{k-1}}/\mathrm{fbs}(f)\), then re-randomises that bit. Suppose \(\mathrm{DT}_\eta(f_{\rho_{k-1}})\ge t-k+1\). Then the current subcube contains two points whose values differ by at least \(2\eta\), so some \(y\) differing from \(x_{k-1}\) only in free coordinates has \(|f(y)-f(x_{k-1})|\ge\eta\), and the weights there sum to at least \(\eta\). The next pick is therefore a new point of \(D\) with probability at least \(\eta/\mathrm{fbs}(f)\), and the random bit keeps the depth condition with probability at least \(1/2\). The sampler thus outputs \(t\) distinct points of \(D\) with probability at least \((\eta/2\,\mathrm{fbs}(f))^t\) whenever the tree is deep.
Since the sampler is independent of \(D\), \(t\)-wise \(p\)-boundedness gives \(\Pr[\text{its output}\subseteq D]\le p^t\). Comparing, \[\Pr_D\bigl[\mathrm{DT}_\eta(f_\rho)\ge t\bigr]\le\Bigl(\frac{2p\,\mathrm{fbs}(f)}{\eta}\Bigr)^t,\] with no dependence on the number of variables. For a \(T\)-query quantum algorithm the acceptance probability has degree at most \(2T\), which gives Corollary 5.2, \((12\pi^2pT^2)^t\). Editorial check: exhaustive enumeration on six-bit functions confirms the bound with room to spare.
How to reuse it
The template, a sampler blind to the random object that would succeed too often if the bad event were likely, proves restriction lemmas whenever a function has a local sensitivity certificate of bounded total weight. It is the information-theoretic core of Fefferman–Kimmel-style lower bounds against classical witnesses.
Level-by-level restrictions for a hierarchy of OR and query gates
Each level of QCMAH adds an existential choice over classical witnesses, which becomes an OR gate over quantum query gates. A single restriction cannot simplify every level at once, so the oracle's hidden set is built as a chain of nested random sets, one per level, in which no fixed set is likely to survive from one level to the next.
In the construction of Section 6.2, \(D_{d,k}\) keeps the codewords of a list-recoverable code consistent with a random head function and with tail functions \(T_1,\dots,T_k\), each bit of which is 1 with probability \(1-(1-p)^{1/d}\). Lemma 6.4: conditioned on \(D_{d,k-1}\), every \(S\) with \(|S|\le2^\lambda\) satisfies \[\Pr[S\subseteq D_{d,k}\mid S\subseteq D_{d,k-1}]\le\exp\!\Bigl(-\frac{\lambda}{3d}|S|\Bigr),\] because list recoverability forces the points of \(S\) to use many distinct symbols across the coordinates, each of which must avoid a fresh random mark.
A promise problem in level \(d\) of QCMAH has, for each input, a circuit of size \(2^{\mathrm{poly}(n)}\) and depth \(2d\) whose gates are unbounded ORs and partial functions computed by polynomial-query quantum algorithms (Proposition 5.3, with consistent completions fixing undefined gate values once). Applying restrictions down the chain, the polynomial switching lemma turns query gates into shallow trees, Håstad's lemma collapses each OR of shallow trees, and Theorem 6.5 bounds the probability that the final restricted function is nonconstant by \[s\bigl(1000\,e^{-\lambda/100d}\,T^2\bigr)^{e^{\lambda/20d}}+e^{-\lambda/20d}.\]
Editorial step for the final comparison: under the restriction that leaves \(D_H\) free and fixes every other point to \(R\), both \(R\lor\mathbf 1_{D_H}\) (all ones on \(D_H\)) and \(R\) (random on \(D_H\)) lie in the restricted subcube. A constant restricted function gives them the same answer, so the YES and NO acceptance probabilities can differ only by the failure probability above, which is negligible for polynomial size, depth and query count. The QMA side uses the code-intersection decoder, with soundness from a matrix Bernstein bound on the verifier's maximum acceptance probability.
How to reuse it
Separating a class from a whole hierarchy built on it works by matching each level of quantifiers with one stage of a nested random restriction. Any family of random sets with this one-step survival bound and a planted structure that only quantum witnesses can locate is a candidate for separating other quantum proof hierarchies.
Context & limitations
Why it matters. The separating language lies outside the polynomial hierarchy and outside \(\mathsf{BQP}^{\mathsf{QCMA}}\), hence outside \(\mathsf{BPP}^{\mathsf{NP}}\) and coNP relative to the oracle, so the need for a quantum proof cannot be reduced away by classical-proof systems of any constant depth. The switching lemma reinterprets the Fefferman–Kimmel extraction argument behind earlier separations and plays for quantum query algorithms the role Håstad's lemma plays for constant-depth circuits. Collapsing QCMA while keeping QMA is a step toward classical-oracle separations between quantum-native cryptographic primitives.
Limitations. All results are relative to oracles. The oracle is structured: each YES instance carries a planted code-intersection block that a random oracle would contain only with doubly exponentially small probability, so a random-oracle separation remains open. The argument relies on an explicit description of all witnesses and does not extend to ClonableQMA, and the switching lemma does not apply to QMA query algorithms. Cakan independently and concurrently separated QMA from QCMAH by a different route. The paper reports that GPT-6 Astra produced an initial proof of a weaker separation, suggested proof elements and audited the final proof, finding a convention issue in Proposition 5.3; the author states that the switching lemma and the QCMAH lower bound were derived independently and that all content was verified.