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.
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 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≥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 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≥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? 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? 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.