Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2506.15551

${\sf QMA}={\sf QMA}_1$ with an infinite counter

Stacey Jeffery, Freek Witteveen

Published Jun 18, 2025• 0 citations
arXivHTMLPDF

Abstract

A long-standing open problem in quantum complexity theory is whether ${\sf QMA}$, the quantum analogue of ${\sf NP}$, is equal to ${\sf QMA}_1$, its one-sided error variant. We show that ${\sf QMA}={\sf QMA}^{\infty}= {\sf QMA}_1^{\infty}$, where ${\sf QMA}_1^\infty$ is like ${\sf QMA}_1$, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an ``infinite counter'', and compare it to a program counter in a Las Vegas algorithm. The result ${\sf QMA}={\sf QMA}^\infty$ means such an infinite register does not increase the power of ${\sf QMA}$, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a ${\sf QMA}$-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous ${\sf QMA}$ amplifiers. Our new construction achieves completeness $1-2^{-q}$ using $O(1)$ calls to each of the original verifier and its inverse, and $O(\log q)$ other gates, proving that ${\sf QMA}$ has completeness doubly exponentially close to 1, i.e. ${\sf QMA}={\sf QMA}(1-2^{-2^r},2^{-r})$ for any polynomial $r$.

DOI
10.48550/arxiv.2506.15551

Related papers

Quantum-Merlin-Arthur Problems Have Perfect Completeness with an Infinite Counter

Stacey Jeffery, Freek Witteveen

A longstanding open problem in quantum complexity theory is whether Quantum Merlin-Arthur (QMA), the quantum analog of nondeterministic polynomial time, is equal to QMA_{1}, its one-sided error variant. We show that QMA=QMA^{∞}=QMA_{1}^{∞}, where QMA_{1}^{∞} is like QMA_{1}, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an "infinite counter," and compare it to a program counter in a Las Vegas algorithm. The result, QMA=QMA^{∞} means such an infinite register does not increase the power of QMA, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a QMA-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous QMA amplifiers. Our new construction achieves completeness 1-2^{-q} using O(1) calls to each of the original verifier and its inverse, and O(logq) other gates, proving that QMA has completeness doubly exponentially close to 1, i.e., QMA=QMA(1-2^{-2^{r}},2^{-r}) for any polynomial r.

Physical Review Letters•Apr 2, 2026•0 citations

A quantum characterization of NP

Hugue Blier, Alain Tapp

In this article we introduce a new complexity class called PQMA_log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts. We then show that PQMA_log(2) = NP. For this to be possible, it is important, when defining the class, not to give too much power to the verifier. This result, when compared to the fact that QMA_log = BQP, gives us new insight on the power of quantum information and the impact of entanglement.

arXiv:0709.0738•Sep 5, 2007•11 citations

Limits to black-box amplification in QMA

Scott Aaronson, Phillip Harris, Freek Witteveen

We study the limitations of black-box amplification in the quantum complexity class Q M A . Amplification is known to boost any inverse-polynomial gap between completeness and soundness to exponentially small error, and a recent result (Jeffery and Witteveen, 2025) shows that completeness can in fact be amplified to be doubly exponentially close to 1. We prove that this is optimal for black-box procedures: we provide a quantum oracle relative to which no Q M A verification procedure using polynomial resources can achieve completeness closer to 1 than doubly exponential, or a soundness which is super-exponentially small. This is proven by making the oracle separation from (Aaronson, 2009) between Q M A and Q M A 1 quantitative, using techniques from complex approximation theory.

arXiv:2509.21131•Quantum•Oct 6, 2026•0 citations

The Power of Unentanglement

Scott Aaronson, Salman Beigi, Andrew Drucker +2 more

The class $\mathsf{QMA}( k) $, introduced by Kobayashi et al., consists of all languages that can be verified using $k$ unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that $k$ quantum proofs are more powerful than one? Does $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for $k\geq2$? Can $\mathsf{QMA}( k) $ protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. We give a protocol by which a verifier can be convinced that a 3SAT formula of size $m$ is satisfiable, with constant soundness, given $\widetilde{O}(\sqrt{m}) $ unentangled quantum witnesses with $O( \log m) $ qubits each. Our protocol relies on the existence of very short PCPs. We show that assuming a weak version of the Additivity Conjecture from quantum information theory, any $\mathsf{QMA}( 2) $ protocol can be amplified to exponentially small error, and $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for all $k\geq2$. We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.

Theory of Computing•Jan 1, 2009•53 citations

The Power of Unentanglement

Scott Aaronson, Salman Beigi, Andrew Drucker +2 more

The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. *We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given O tilde(radicn) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on Dinur's version of the PCP Theorem and is inherently non-relativizing. *We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all kges=2. *We give evidence that QMA(2) sube PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•27 citations

The Power of Unentanglement

Scott Aaronson, Salman Beigi, Andrew Drucker +2 more

The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Does QMA(k)=QMA(2) for k>=2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. First, we give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given ~O(sqrt(n)) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on the existence of very short PCPs. Second, we show that assuming a weak version of the Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all k>=2. Third, we prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.

arXiv:0804.0802•Electronic colloquium on computational complexity•Apr 4, 2008•2 citations
QMA=QMA1{\sf QMA}={\sf QMA}_1QMA=QMA1​ with an infinite counter
A long-standing open problem in quantum complexity theory is whether QMA{\sf QMA}QMA, the quantum analogue of NP{\sf NP}NP, is equal to QMA1{\sf QMA}_1QMA1​, its one-sided error variant. We show that QMA=QMA∞=QMA1∞{\sf QMA}={\sf QMA}^{\infty}= {\sf QMA}_1^{\infty}QMA=QMA∞=QMA1∞​, where QMA1∞{\sf QMA}_1^\inftyQMA1∞​ is like QMA1{\sf QMA}_1QMA1​, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an ``infinite counter'', and compare it to a program counter in a Las Vegas algorithm. The result QMA=QMA∞{\sf QMA}={\sf QMA}^\inftyQMA=QMA∞ means such an infinite register does not increase the power of QMA{\sf QMA}QMA, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a QMA{\sf QMA}QMA-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous QMA{\sf QMA}QMA amplifiers. Our new construction achieves completeness 1−2−q1-2^{-q}1−2−q using O(1)O(1)O(1) calls to each of the original verifier and its inverse, and O(log⁡q)O(\log q)O(logq) other gates, proving that QMA{\sf QMA}QMA has completeness doubly exponentially close to 1, i.e. QMA=QMA(1−2−2r,2−r){\sf QMA}={\sf QMA}(1-2^{-2^r},2^{-r})QMA=QMA(1−2−2r,2−r) for any polynomial rrr.
A longstanding open problem in quantum complexity theory is whether Quantum Merlin-Arthur (QMA), the quantum analog of nondeterministic polynomial time, is equal to QMA_{1}, its one-sided error variant. We show that QMA=QMA^{∞}=QMA_{1}^{∞}, where QMA_{1}^{∞} is like QMA_{1}, but the verifier has an infinite register, as part of their witness system, in which they can efficiently perform a shift (increment) operation. We call this register an "infinite counter," and compare it to a program counter in a Las Vegas algorithm. The result, QMA=QMA^{∞} means such an infinite register does not increase the power of QMA, but does imply perfect completeness. By truncating our construction to finite dimensions, we get a QMA-amplifier that only amplifies completeness, not soundness, but does so in significantly less time than previous QMA amplifiers. Our new construction achieves completeness 1-2^{-q} using O(1) calls to each of the original verifier and its inverse, and O(logq) other gates, proving that QMA has completeness doubly exponentially close to 1, i.e., QMA=QMA(1-2^{-2^{r}},2^{-r}) for any polynomial r.
In this article we introduce a new complexity class called PQMA_log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts. We then show that PQMA_log(2) = NP. For this to be possible, it is important, when defining the class, not to give too much power to the verifier. This result, when compared to the fact that QMA_log = BQP, gives us new insight on the power of quantum information and the impact of entanglement.
We study the limitations of black-box amplification in the quantum complexity class Q M A . Amplification is known to boost any inverse-polynomial gap between completeness and soundness to exponentially small error, and a recent result (Jeffery and Witteveen, 2025) shows that completeness can in fact be amplified to be doubly exponentially close to 1. We prove that this is optimal for black-box procedures: we provide a quantum oracle relative to which no Q M A verification procedure using polynomial resources can achieve completeness closer to 1 than doubly exponential, or a soundness which is super-exponentially small. This is proven by making the oracle separation from (Aaronson, 2009) between Q M A and Q M A 1 quantitative, using techniques from complex approximation theory.
The class $\mathsf{QMA}( k) $, introduced by Kobayashi et al., consists of all languages that can be verified using kkk unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that kkk quantum proofs are more powerful than one? Does $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for k≥2k\geq2k≥2? Can $\mathsf{QMA}( k) $ protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. We give a protocol by which a verifier can be convinced that a 3SAT formula of size mmm is satisfiable, with constant soundness, given $\widetilde{O}(\sqrt{m}) $ unentangled quantum witnesses with $O( \log m) $ qubits each. Our protocol relies on the existence of very short PCPs. We show that assuming a weak version of the Additivity Conjecture from quantum information theory, any $\mathsf{QMA}( 2) $ protocol can be amplified to exponentially small error, and $\mathsf{QMA}( k) =\mathsf{QMA}( 2) $ for all k≥2k\geq2k≥2. We prove the nonexistence of “perfect disentanglers” for simulating multiple Merlins with one.
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can we show any upper bound on QMA(k), besides the trivial NEXP? Does QMA(k)=QMA(2) for kges2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. *We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given O tilde(radicn) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on Dinur's version of the PCP Theorem and is inherently non-relativizing. *We show that assuming the famous Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all kges=2. *We give evidence that QMA(2) sube PSPACE, by showing that this would follow from "strong amplification" of QMA(2) protocols. *We prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.
The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Does QMA(k)=QMA(2) for k>=2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. First, we give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given ~O(sqrt(n)) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on the existence of very short PCPs. Second, we show that assuming a weak version of the Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all k>=2. Third, we prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one.