Perfect completeness for quantum Merlin-Arthur proof systems: does QMA = QMA1, and is there a direct reduction from PreciseQMA to PreciseQMA with perfect completeness?

The problem, stated explicitly in Yulong Li's 2022 note 'A Simple Proof of PreciseQMA = PSPACE', is whether quantum Merlin-Arthur proof systems can achieve perfect completeness. Two linked questions arise. (1) Is QMA, the quantum analogue of NP, equal to QMA$_1$, its perfect-completeness (one-sided-error) variant? Classically MA = MA$_1$, and for quantum verifiers with classical witnesses QCMA = QCMA$_1$, but for quantum witnesses the question has been open since the mid-2000s, and Aaronson's quantum-oracle separation rules out all black-box proofs of equality. (2) In the exponentially-small-promise-gap regime, PreciseQMA = PSPACE = PreciseQMA$^{c=1}$ is known (Fefferman-Lin, with Li's simplified proof), but every known route to perfect completeness first re-expresses the language as a PSPACE computation; Li asks whether a direct reduction from PreciseQMA to PreciseQMA$^{c=1}$ exists. A 2025 line of work brackets the core question tightly: completeness can be black-box amplified to $1-2^{-2^{r}}$, and equals $1$ for verifiers with an infinite-counter register, yet provably no black-box procedure can do better. Both questions remain open.

Background

A promise problem $L=(L_{\mathrm{yes}},L_{\mathrm{no}})$ is in QMA (Quantum Merlin-Arthur), the quantum analogue of NP, if a polynomial-time quantum verifier circuit $V_x$ can be convinced of membership in $L_{\mathrm{yes}}$ by a quantum witness state $|\psi\rangle$: for $x\in L_{\mathrm{yes}}$ some witness is accepted with probability at least $c$ (the completeness), while for $x\in L_{\mathrm{no}}$ every witness is accepted with probability at most $s$ (the soundness). QMA is the union of the classes $\mathrm{QMA}(c,s)$ over completeness-soundness gaps $c-s$ at least inverse-polynomial in the input length. The canonical QMA-complete problem is the local Hamiltonian problem, estimating the ground-state energy of a sum of few-qubit interactions, the quantum counterpart of SAT. Marriott and Watrous showed that the gap can be amplified, reducing both errors exponentially without increasing the witness length, but such amplification never makes the completeness exactly $1$.

This failure is exceptional. Classically, the randomized proof class MA equals its perfect-completeness variant MA$_1$, and for quantum verifiers restricted to classical witnesses one equally has QCMA $=$ QCMA$_1$ (Jordan, Kobayashi, Nagaj, and Nishimura, 2011), by a direct 'additive adjustment' construction that is quantumly nonrelativizing; and with even slight interaction, every QMA problem has a two-message quantum interactive proof with perfect completeness (Kobayashi, Le Gall, and Nishimura, 2012). Whether $\mathrm{QMA}=\mathrm{QMA}_1$, where QMA$_1$ (also written QMA$^{c=1}$) requires YES-instances to be accepted with probability exactly $1$, has been open since the mid-2000s. Aaronson (2008) explained why: there is a quantum oracle, an oracle unitary available to the verifier, relative to which QMA $\neq$ QMA$_1$, so the equality, if true, cannot be established by any technique that relativizes to quantum oracles. The question is a fixture of the 'quantum NP' landscape (Gharibian's 2023 survey), and even the robustness of QMA$_1$ to the choice of universal gate set is delicate, because the Solovay-Kitaev theorem, which approximates arbitrary gates by a fixed finite set necessarily with error, is incompatible with exact acceptance (Rudolph 2024).

A second thread concerns very small promise gaps. PreciseQMA is the union of $\mathrm{QMA}(c,s)$ over gaps $c-s\ge 2^{-\mathrm{poly}(n)}$. Fefferman and Lin proved the characterization PreciseQMA $=$ PSPACE, and, in a companion paper on unitary quantum space, that PreciseQMA even admits perfect completeness: PreciseQMA $=$ PSPACE $=\mathrm{QMA}(1,\,1-2^{-\mathrm{poly}})\equiv\mathrm{PreciseQMA}^{c=1}$ (Proposition 23, assuming a gate set in which the Hadamard and Toffoli gates are exactly implementable). Yulong Li (2022) gave a short alternative proof: a polynomial-space computation can be made reversible (Bennett's construction), simulated by a unitary circuit with perfect completeness, and encoded as a Feynman-Kitaev history-state Hamiltonian, the Quantum Cook-Levin construction. A history state is a uniform superposition over the steps of the computation, weighted so that a QMA verifier can check it locally; on YES instances its energy is exactly zero. However, in Li's proof, as in Fefferman-Lin's, the perfect-completeness protocol is obtained only by first re-expressing the language as a PSPACE computation; the transformation of an arbitrary PreciseQMA verifier into a perfect-completeness one is indirect.

The frontier has recently been sharply bracketed. Jeffery and Witteveen (2025) proved $\mathrm{QMA}=\mathrm{QMA}^{\infty}=\mathrm{QMA}_1^{\infty}$, where the superscript $\infty$ denotes verifiers equipped with an infinite-dimensional 'counter' register supporting an increment operation: such a register confers perfect completeness but is not a standard finite quantum verifier. Truncating their construction yields a black-box, completeness-only amplifier achieving $\mathrm{QMA}=\mathrm{QMA}(1-2^{-2^{r}},\,2^{-r})$ for any polynomial $r$. Aaronson, Harris, and Witteveen (2025) then proved, by a quantitative quantum-oracle construction, that this is optimal: no black-box procedure using polynomial resources can drive QMA completeness closer to $1$ than doubly-exponentially close, or achieve super-exponentially small soundness. The remaining gap, from $1-2^{-2^{r}}$ to exactly $1$, is therefore provably beyond black-box amplification, and any resolution of $\mathrm{QMA}$ versus $\mathrm{QMA}_1$ must exploit the internal structure of the verifier in a non-black-box way.

Problem Statement

The problem has two linked parts sharing one scientific objective: determine whether one-sided-error (perfectly complete) quantum verification is as powerful as two-sided-error quantum verification, and by what explicit transformation.

Q1 (core, named problem). Is $\mathrm{QMA}=\mathrm{QMA}_1$? Formally: for every promise problem $L=(L_{\mathrm{yes}},L_{\mathrm{no}})$ having a P-uniform family (i.e., the verifier circuit for input $x$ is produced by a polynomial-time algorithm) of polynomial-size quantum verifier circuits with completeness $c\ge 2/3$ and soundness $s\le 1/3$, does there also exist a P-uniform polynomial-size verifier family with completeness exactly $1$ (on every $x\in L_{\mathrm{yes}}$ some witness is accepted with probability exactly $1$) and soundness at most $1/2$? A complete answer is either a construction with a correctness proof establishing equality, or an unconditional proof that some QMA language admits no perfect-completeness QMA verifier.

Q2 (precise-gap variant, posed by Li 2022). Let PreciseQMA $=\bigcup_{c-s\ge 2^{-\mathrm{poly}}}\mathrm{QMA}(c,s)$ and PreciseQMA$^{c=1}=\mathrm{QMA}(1,\,1-2^{-\mathrm{poly}})$. It is known that PreciseQMA $=$ PSPACE $=$ PreciseQMA$^{c=1}$, but every known proof converts a PreciseQMA verifier into a perfect-completeness one only by first re-expressing the language as a polynomial-space computation (reversible space-bounded simulation plus a Feynman-Kitaev history-state Hamiltonian). Does there exist a direct reduction: an explicitly specified, polynomial-time-computable transformation of the verifier circuit family producing an equivalent perfect-completeness verifier without passing through the PSPACE representation, in the spirit of the direct QCMA to QCMA$_1$ transformation of Jordan et al.?

The parts are distinct but jointly serve the objective: Q1 asks whether perfect completeness is achievable at all with quantum witnesses; Q2 asks for it constructively and directly in the regime where the class-level equality is already known and only the method is indirect. Note that black-box constructions are already known to be insufficient for the final step to exact completeness, so an answer must exploit the verifier's internal structure.

References

1. Yulong Li. A Simple Proof of PreciseQMA = PSPACE. arXiv:2206.09230 (2022). DOI: 10.48550/arXiv.2206.09230. https://arxiv.org/abs/2206.09230
2. Scott Aaronson. On Perfect Completeness for QMA. arXiv:0806.0450 (2008). DOI: 10.48550/arXiv.0806.0450. https://arxiv.org/abs/0806.0450
3. Bill Fefferman, Cedric Lin. Quantum Merlin Arthur with Exponentially Small Gap. arXiv:1601.01975 (2016). DOI: 10.48550/arXiv.1601.01975. https://arxiv.org/abs/1601.01975
4. Bill Fefferman, Cedric Yen-Yu Lin. A Complete Characterization of Unitary Quantum Space. arXiv:1604.01384 (2016). DOI: 10.48550/arXiv.1604.01384. https://arxiv.org/abs/1604.01384
5. Chris Marriott, John Watrous. Quantum Arthur-Merlin Games. arXiv:cs/0506068 (2005). DOI: 10.48550/arXiv.cs/0506068. https://arxiv.org/abs/cs/0506068
6. Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. arXiv:1111.5306 (2011). DOI: 10.48550/arXiv.1111.5306. https://arxiv.org/abs/1111.5306
7. Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura. Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete. arXiv:1210.1290 (2012). DOI: 10.48550/arXiv.1210.1290. https://arxiv.org/abs/1210.1290
8. Sevag Gharibian. The 7 faces of quantum NP. arXiv:2310.18010 (2023). DOI: 10.48550/arXiv.2310.18010. https://arxiv.org/abs/2310.18010
9. Hugo Delavenne, Francois Le Gall, Yupan Liu, Masayuki Miyamoto. Quantum Merlin-Arthur proof systems for synthesizing quantum states. arXiv:2303.01877 (2023); published as Quantum 9, 1688 (2025), DOI: 10.22331/q-2025-04-03-1688. https://arxiv.org/abs/2303.01877
10. Dorian Rudolph. Towards a universal gateset for QMA1. arXiv:2411.02681 (2024). DOI: 10.48550/arXiv.2411.02681. https://arxiv.org/abs/2411.02681
11. Stacey Jeffery, Freek Witteveen. QMA = QMA1 with an infinite counter. arXiv:2506.15551 (2025). DOI: 10.48550/arXiv.2506.15551. https://arxiv.org/abs/2506.15551
12. Scott Aaronson, Phillip Harris, Freek Witteveen. Limits to black-box amplification in QMA. arXiv:2509.21131 (2025). DOI: 10.48550/arXiv.2509.21131. https://arxiv.org/abs/2509.21131
13. Jonas Kamminga, Dorian Rudolph. On the Complexity of Pure-State Consistency of Local Density Matrices. arXiv:2411.03096 (2024). DOI: 10.48550/arXiv.2411.03096. https://arxiv.org/abs/2411.03096
14. David Miloschewsky, Supartha Podder, Dorian Rudolph. En Route to a Standard QMA1 vs. QCMA Oracle Separation. arXiv:2604.26921 (2026). DOI: 10.48550/arXiv.2604.26921. https://arxiv.org/abs/2604.26921
15. Fernando Granha Jeronimo, Pei Wu, Itai Leigh. The QMA(2) Universe: Complexity, Entanglement, and Optimization. ACM SIGACT News 57(1) (2026). DOI: 10.1145/3802807.3802814. https://doi.org/10.1145/3802807.3802814