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.
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.
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.
We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), and QSZK), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either QMA-complete or QMA(2)-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by employing prior work on entanglement purification protocols to prove that for each n-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in n.
The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, QCPH , uses classical proofs, and the second, QPH , uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, QΣ3 , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for QMA(2) , the variant of Quantum Merlin-Arthur ( QMA ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in Ppppp ). Second, because QMA(2)⊆QΣ3 , QMA(2) is strictly contained in NEXP unless QMA(2)=QΣ3 (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').
Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA, in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomial-time quantum computation. For some problems, the fact that a quantum proof state could be a superposition over exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP* that represent natural quantum analogues of IP, SZK, and MIP. While quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model. In this survey we provide an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, we discuss non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.
In QMA(2), two computationally unbounded provers submit unentangled quantum witnesses to a polynomial-time quantum verifier. We ask whether allowing limited shared entanglement between the two provers changes the power of QMA(2). To this end, we formalize QMA(2;h), a variant in which the provers initially share h EPR pairs, as suggested by Aaronson, Beigi, Drucker, Fefferman, and Shor (ToC~2009). We show that polynomially many shared EPR pairs give the provers no cheating advantage: QMA(2)⊆QMA(2;h) for h=poly(n). For logarithmically many pairs, the power of QMA(2) remains unchanged, strengthening this inclusion to QMA(2)=QMA(2;h) for h=O(logn). Finally, we introduce a variant that also allows classical communication between the provers when preparing the witnesses. This setting is particularly revealing for logarithmic-size witnesses: assuming NP⊈BQP, we show that superlogarithmically many shared EPR pairs strictly reduce the model's computational power.
Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. The beauty of quantum games-succinct in representation, rich in structures, explosive in complexity, dazzling for visualization, and sophisticated for strategic reasoning-has drawn us to play concrete games full of subtleties and to characterize abstract properties pertinent to complexity consequence. Going beyond individual games, we explore the tractability of quantum combinatorial games as whole, and address fundamental questions including: Quantum Leap in Complexity: Are there polynomial-time solvable games whose quantum extensions are intractable? Quantum Collapses in Complexity: Are there PSPACE-complete games whose quantum extensions fall to the lower levels of the polynomial-time hierarchy? Quantumness Matters: How do outcome classes and strategies change under quantum moves? Under what conditions doesn't quantumness matter? PSPACE Barrier for Quantum Leap: Can quantum moves launch PSPACE games into outer polynomial space We show that quantum moves not only enrich the game structure, but also impact their computational complexity. In settling some of these basic questions, we characterize both the powers and limitations of quantum moves as well as the superposition of game configurations that they create. Our constructive proofs-both on the leap of complexity in concrete Quantum Nim and Quantum Undirected Geography and on the continuous collapses, in the quantum setting, of complexity in abstract PSPACE-complete games to each level of the polynomial-time hierarchy-illustrate the striking computational landscape over quantum games and highlight surprising turns with unexpected quantum impact. Our studies also enable us to identify several elegant open questions fundamental to quantum combinatorial game theory (QCGT).