No relativizing reduction from QMA to QCMA

Unconditional · against relativizing reductions · BHNZ25, BHV26

Statement

No relativizing proof places QMA inside QCMA: there is a standard classical oracle relative to which $\mathbf{QMA}⊈\mathbf{QCMA}$ — BHNZ25. The separating problem is spectral Forrelation: decide whether some quantum state has computational-basis measurement supported on one oracle-defined set and Fourier-basis measurement supported on another. BHV26 give a simpler proof using good error-correcting codes.

Notes

• Earlier, restricted separations of the same pair: a quantum unitary oracle — AK07; an in-place quantum oracle — BFM23; a distributional classical oracle, with the honest witness depending only on the oracle distribution — NN23; a classical oracle against verifiers of bounded adaptivity — BK24.
• AK07 (quantum oracle) and BHV26 (classical oracle) also separate $\mathbf{BQP}/\mathrm{qpoly}$ from $\mathbf{BQP}/\mathrm{poly}$.
• Unrelativized, whether $\mathbf{QMA}\subseteq \mathbf{QCMA}$ is open — standard. The reverse inclusion $\mathbf{QCMA}\subseteq \mathbf{QMA}$ holds — folklore; see QCMA ⊆ QMA.