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

Study of Unentanglement in Quantum Computers

Rayan Chikhi

Published Jan 1, 2008• 0 citations
OpenAlex

Abstract

This report explains the research work done during a February-June 2008 internship at MIT under the supervision of Scott Aaronson and Seth Lloyd. It exposes some necessary background knowledge in quantum mechanics, quantum computing and quantum complexity theory, and then focuses on the work conducted during this internship. The subject of this internship is to study two important classes of quantum problems, QMA and QMA(2), which consist of all languages that can be verified using respectively one and two unentangled quantum proofs. Whether these classes are equal or distinct is an open problem of great interest in quantum computing. To prove that they are the same, one can possibly simulate QMA(2) problems in QMA using a quantum operation called a disentangler. However, it has been conjectured that polynomial disentanglers do not exist, and therefore this approach fails. In this report, we investigate this conjecture and give two results: in a specific situation, when exponential precision is required, this conjecture holds as long as P 6 = NP. Moreover, in the same situation, we show that the conjecture could be proven unconditionally using a stronger hypothesis.

Related papers

The Power of Unentanglement (Extended Abstract)

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 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, 2008•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.

arXiv:0804.0802•Theory of Computing•Jan 1, 2009•70 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•31 citations

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes

Fernando Granha Jeronimo, Pei Wu

Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.

arXiv:2402.18790•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•16 citations

The QMA(2) UniverseComplexity, Entanglement, and Optimization

Fernando Granha Jeronimo, Pei Wu, Itai Leigh

The complexity class QMA(2), featuring two unentangled quantum provers, occupies a central yet poorly understood position in quantum complexity theory. While superficially a modest extension of QMA, unentanglement fundamentally changes both the algorithmic and complexitytheoretic landscape, connecting QMA(2) to deep questions in separability testing, polynomial optimization, and hardness of approximation. Over the past two decades, QMA(2) has inspired a rich body of work spanning restricted verification models, semidefinite and Sum-of-Squares hierarchies, and surprising links to classical problems such as the Unique Games Conjecture. This survey provides an overview of these developments, emphasizing structural insights, algorithmic techniques, and known barriers, while highlighting how progress on QMA(2) continues to illuminate the interplay between quantum information, convex optimization, and classical complexity theory.

ACM SIGACT News•Mar 31, 2026•5 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.

quant-pharXiv:2604.27886•May 1, 2026•4 citations
This report explains the research work done during a February-June 2008 internship at MIT under the supervision of Scott Aaronson and Seth Lloyd. It exposes some necessary background knowledge in quantum mechanics, quantum computing and quantum complexity theory, and then focuses on the work conducted during this internship. The subject of this internship is to study two important classes of quantum problems, QMA and QMA(2), which consist of all languages that can be verified using respectively one and two unentangled quantum proofs. Whether these classes are equal or distinct is an open problem of great interest in quantum computing. To prove that they are the same, one can possibly simulate QMA(2) problems in QMA using a quantum operation called a disentangler. However, it has been conjectured that polynomial disentanglers do not exist, and therefore this approach fails. In this report, we investigate this conjecture and give two results: in a specific situation, when exponential precision is required, this conjecture holds as long as P 6 = NP. Moreover, in the same situation, we show that the conjecture could be proven unconditionally using a stronger hypothesis.
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 $\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.
Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.
The complexity class QMA(2), featuring two unentangled quantum provers, occupies a central yet poorly understood position in quantum complexity theory. While superficially a modest extension of QMA, unentanglement fundamentally changes both the algorithmic and complexitytheoretic landscape, connecting QMA(2) to deep questions in separability testing, polynomial optimization, and hardness of approximation. Over the past two decades, QMA(2) has inspired a rich body of work spanning restricted verification models, semidefinite and Sum-of-Squares hierarchies, and surprising links to classical problems such as the Unique Games Conjecture. This survey provides an overview of these developments, emphasizing structural insights, algorithmic techniques, and known barriers, while highlighting how progress on QMA(2) continues to illuminate the interplay between quantum information, convex optimization, and classical complexity theory.
Stoquasticity, originating in sign-problem-free physical systems, gives rise to StoqMA\sf StoqMAStoqMA, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between MA\sf MAMA and AM\sf AMAM. Unentanglement similarly gives rise to QMA(2){\sf QMA}(2)QMA(2), introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes QMA\sf QMAQMA to two unentangled proofs and still has only the trivial NEXP\sf NEXPNEXP upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via StoqMA(2){\sf StoqMA}(2)StoqMA(2), the class of unentangled stoquastic Merlin--Arthur proof systems. Beyond its complexity-theoretic interest, StoqMA(2){\sf StoqMA}(2)StoqMA(2) is connected to the optimality of non-negative tensor optimization algorithms. We highlight: 1. NP⊆StoqMA(2){\sf NP} \subseteq {\sf StoqMA}(2)NP⊆StoqMA(2) with O~(n)\widetilde{O}(\sqrt{n})O(n​)-qubit proofs and completenes 1−2−polylog(n)1-2^{-{\rm polylog}(n)}1−2−polylog(n). Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for StoqMA(2){\sf StoqMA}(2)StoqMA(2). Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH. 2. For logarithmic-size proofs, NP⊆StoqMA(2)log⁡{\sf NP} \subseteq {\sf StoqMA}(2)_{\log}NP⊆StoqMA(2)log​ with completeness 1−O(n−2)1-O(n^{-2})1−O(n−2) and vanishing gap, while StoqMA(2)log⁡⊆MA{\sf StoqMA}(2)_{\log} \subseteq {\sf MA}StoqMA(2)log​⊆MA. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption MA=NP{\sf MA}={\sf NP}MA=NP. 3. For StoqMA(2)1{\sf StoqMA}(2)_1StoqMA(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 QMA(2){\sf QMA}(2)QMA(2) protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.