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 k ≥ 2? 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 Õ (√n) 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 k ≥ 2. • We give evidence that QMA(2) ⊆ 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? Can we show any upper bound on QMA(k), besides the trivial NEXP? 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. • We give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given Õ (√n) 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 k ≥ 2. • We give evidence that QMA(2) ⊆ 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.

Jan 1, 20080 citations

The power of unentanglement without destructive interference

Yupan Liu, Pei Wu

Stoquasticity, originating in sign-problem-free physical systems, gives rise to $\sf StoqMA$ , introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between $\sf MA$ and $\sf AM$ . Unentanglement similarly gives rise to ${\sf QMA}(2)$ , introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes $\sf QMA$ to two unentangled proofs and still has only the trivial $\sf NEXP$ upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via ${\sf StoqMA}(2)$ , the class of unentangled stoquastic Merlin--Arthur proof systems. Beyond its complexity-theoretic interest, ${\sf StoqMA}(2)$ is connected to the optimality of non-negative tensor optimization algorithms. We highlight: 1. ${\sf NP} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{n})$ -qubit proofs and completenes $1-2^{-{\rm polylog}(n)}$ . Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for ${\sf StoqMA}(2)$ . Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH. 2. For logarithmic-size proofs, ${\sf NP} \subseteq {\sf StoqMA}(2)_{\log}$ with completeness $1-O(n^{-2})$ and vanishing gap, while ${\sf StoqMA}(2)_{\log} \subseteq {\sf MA}$ . Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption ${\sf MA}={\sf NP}$ . 3. For ${\sf StoqMA}(2)_1$ , the parameter dependence in the general ETH-optimal time bound can be exponentially improved, or the bound achieved simultaneously with polynomial space. Our lower bounds are obtained by stoquastizing the short-proof ${\sf QMA}(2)$ protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.Stoquasticity, originating in sign-problem-free physical systems, gives rise to $\sf StoqMA$, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between $\sf MA$ and $\sf AM$. Unentanglement similarly gives rise to ${\sf QMA}(2)$, introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes $\sf QMA$ to two unentangled proofs and still has only the trivial $\sf NEXP$ upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via ${\sf StoqMA}(2)$, the class of unentangled stoquastic Merlin--Arthur proof systems. Beyond its complexity-theoretic interest, ${\sf StoqMA}(2)$ is connected to the optimality of non-negative tensor optimization algorithms. We highlight: 1. ${\sf NP} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{n})$-qubit proofs and completenes $1-2^{-{\rm polylog}(n)}$. Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for ${\sf StoqMA}(2)$. Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH. 2. For logarithmic-size proofs, ${\sf NP} \subseteq {\sf StoqMA}(2)_{\log}$ with completeness $1-O(n^{-2})$ and vanishing gap, while ${\sf StoqMA}(2)_{\log} \subseteq {\sf MA}$. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption ${\sf MA}={\sf NP}$. 3. For ${\sf StoqMA}(2)_1$, the parameter dependence in the general ETH-optimal time bound can be exponentially improved, or the bound achieved simultaneously with polynomial space. Our lower bounds are obtained by stoquastizing the short-proof ${\sf QMA}(2)$ protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.

quant-pharXiv:2604.27886May 1, 20260 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.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.0802Electronic colloquium on computational complexityApr 4, 20082 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.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 ComputingJan 1, 200953 citations

Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs

Masayuki Miyamoto

We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$ , $\mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right).$ Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have $\mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right),$ where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse $\mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}.$ Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[ \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[ \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \] Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.

quant-pharXiv:2608.07986Aug 11, 20260 citations

Quantum Merlin-Arthur with an Internally Separable Proof

Roozbeh Bassirian, Bill Fefferman, Itai Leigh +2 more

We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP $\ne$ NEXP. This gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our modification endows each proof with a form of *multipartite* unentanglement: after tracing out one register, a small number of qubits are separable from the rest of the state.We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP $\ne$ NEXP. This gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our modification endows each proof with a form of *multipartite* unentanglement: after tracing out one register, a small number of qubits are separable from the rest of the state.

arXiv:2410.19152Leibniz international proceedings in informaticsOct 24, 20240 citations

Stoquasticity, originating in sign-problem-free physical systems, gives rise to

\sf StoqMA

, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between

\sf MA

and

\sf AM

. Unentanglement similarly gives rise to

{\sf QMA}(2)

, introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes

\sf QMA

to two unentangled proofs and still has only the trivial

\sf NEXP

upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via

{\sf StoqMA}(2)

, the class of unentangled stoquastic Merlin--Arthur proof systems. Beyond its complexity-theoretic interest,

{\sf StoqMA}(2)

is connected to the optimality of non-negative tensor optimization algorithms. We highlight: 1.

{\sf NP} \subseteq {\sf StoqMA}(2)

with

\widetilde{O}(\sqrt{n})

-qubit proofs and completenes

1-2^{-{\rm polylog}(n)}

. Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for

{\sf StoqMA}(2)

. Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH. 2. For logarithmic-size proofs,

{\sf NP} \subseteq {\sf StoqMA}(2)_{\log}

with completeness

1-O(n^{-2})

and vanishing gap, while

{\sf StoqMA}(2)_{\log} \subseteq {\sf MA}

. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption

{\sf MA}={\sf NP}

. 3. For

{\sf StoqMA}(2)_1

, the parameter dependence in the general ETH-optimal time bound can be exponentially improved, or the bound achieved simultaneously with polynomial space. Our lower bounds are obtained by stoquastizing the short-proof

{\sf QMA}(2)

protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.

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.

We study gap amplification of the class

\mathsf{QMA}^{+}(2)

characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of

\mathsf{NEXP}

for some small constant gap, it is equal to

\mathsf{QMA}(2)

for larger constant gap. This is in stark contrast to

\mathsf{QMA}(2)

where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness

c

and soundness

s

with

c-s=1/\mathrm{poly}(n)

\mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right).

Our result gives a clean complexity phase transition for

\mathsf{QMA}^{+}(2)

since we have

\mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right),

where

\mathsf{QMA}^{\mathbb R}(2)

denotes

\mathsf{QMA}(2)

with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse

\mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}.

Our proof combines symmetric-subspace projections with the relation

\mathsf{QMA}^{+}(1)=\mathsf{NEXP}

of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.

We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP

\ne

NEXP. This gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our modification endows each proof with a form of *multipartite* unentanglement: after tracing out one register, a small number of qubits are separable from the rest of the state.