QMA(2) with Limited Shared Entanglement

AI summary

Overview

Research area: Quantum computational complexity, specifically quantum multiprover proof systems and the role of shared entanglement. Technical level: Advanced. Scope: This paper formalizes and analyzes QMA(2;h), a variant of QMA(2) in which two provers may share h EPR pairs, and determines how limited shared entanglement affects the class’s computational power.

What This Paper Is About

In QMA(2), two computationally unbounded provers send unentangled quantum witnesses to a polynomial-time quantum verifier. The paper asks whether relaxing that unentanglement promise — by allowing the provers to share a limited number of EPR pairs before preparing their witnesses — changes the power of QMA(2). The question traces back to Aaronson, Beigi, Drucker, Fefferman, and Shor, who suggested the QMA(2;h) model.

Key Contributions

1. Formalizes QMA(2;h) and characterizes its legal witnesses. Pure legal witnesses are “flat” states with equal nonzero Schmidt coefficients and Schmidt rank 2^t for 0 ≤ t ≤ h; mixed legal witnesses have Schmidt number at most 2^h.
2. Proves that polynomially many shared EPR pairs give no cheating advantage. For polynomially bounded h ≤ H, the paper shows QMA(2;h) ⊆ QMA(2;H), and hence QMA(2) ⊆ QMA(2;H).
3. Proves equality for logarithmically many EPR pairs. For h = O(log n), the paper shows QMA(2;h) = QMA(2), using a four-witness simulation combined with the Harrow–Montanaro equality QMA(4) = QMA(2).
4. Introduces an LOCC variant and identifies an entanglement threshold. In QMA_log^LOCC(2;h), provers may also communicate classically while preparing witnesses; assuming NP ⊄ BQP, sharing H = ω(log n) EPR pairs strictly reduces power: QMA_log^LOCC(2;H) ⊊ QMA_log(2).

Main Findings

• Monotonicity for polynomial entanglement: For polynomially bounded h ≤ H, QMA(2;h) ⊆ QMA(2;H) (Theorem 6). Increasing the number of shared EPR pairs does not decrease the model’s power.
• Padding collapse: If QMA(2;n^ε) = QMA(2) for any constant ε > 0, then QMA(2;h) = QMA(2) for every polynomially bounded h (Corollary 7). Thus a very small polynomial suffices to settle the general polynomial case.
• Logarithmic equality: For h = O(log n), QMA(2;h) = QMA(2) (Theorem 10). The result preserves constant completeness–soundness gaps and extends to the LOCC setting.
• Strict loss above logarithmic entanglement: Assuming NP ⊄ BQP, for every H = ω(log n), QMA_log^LOCC(2;H) ⊊ QMA_log(2) (Corollary 16). Once the shared EPR pairs exceed the witness size, the provers can prepare any state on the joint registers, collapsing the model to QMA_log = BQP.
• Witness structure: Pure witnesses in QMA(2;h) must be flat, with Schmidt rank 2^t, 0 ≤ t ≤ h. Mixed witnesses are convex combinations of pure states of Schmidt rank at most D = 2^h.
• Known upper bound: For polynomially bounded h, QMA(2;h) ⊆ NEXP, via the Kobayashi–Matsumoto bound.
• Technical bottleneck: The four-witness simulation achieves a completeness–soundness gap of Ω(1/(poly(n) D^2)), where D = 2^h. For h = poly(n), this becomes exponentially small because the Bell step can succeed with probability as low as D^{-2} even on honest proper encodings.

Methodology in Plain English

The authors define a preparation rule: the two provers start with h shared EPR pairs plus local quantum workspace, apply arbitrary local quantum channels, and send the resulting state to the verifier. They then characterize exactly which joint states can arise this way.

For the polynomial-entanglement result, the verifier asks the provers to submit a legal witness together with the surplus EPR pairs, then performs Bell measurements on the surplus pairs. The proof shows that tampering with those pairs cannot increase the verifier’s acceptance probability, so extra entanglement provides no cheating advantage.

For the logarithmic result, the authors simulate a QMA(2;h) protocol using four unentangled witnesses. Two witnesses encode the local Schmidt bases with index registers, and two additional copies are used for consistency and “properness” tests. A Bell measurement on the index registers reconstructs the original witness with probability D^{-2}. The resulting protocol has an inverse-polynomial gap when h = O(log n), and the Harrow–Montanaro equality QMA(4) = QMA(2) reduces it to QMA(2).

The paper also includes an explicit AI usage disclosure: OpenAI’s GPT-5.6 Sol and GPT-6 Astra, together with Anthropic’s Claude 5.0 Opus, contributed substantially to the research and manuscript, including the four-witness simulation, a direct two-witness simulation, and Results 1, 2, and 4.

Why This Matters

This work sharpens the boundary between QMA(2) and related multiprover models. It shows that polynomial shared entanglement does not obviously strengthen QMA(2), while logarithmic entanglement leaves the class unchanged, and superlogarithmic entanglement can strictly weaken a logarithmic-witness LOCC variant. These results help isolate what the unentanglement promise actually contributes to QMA(2) and connect the model to longstanding questions about entanglement as a computational resource.

The paper reports no direct real-world applications or experiments. Potential long-term application areas, not claimed by the paper, include:

• Quantum verification protocols: Understanding whether shared entanglement helps or harms verification is relevant to designing protocols for untrusted quantum devices.
• Entanglement as a resource: The results quantify when shared EPR pairs are computationally useful and when they are not.
• Quantum cloud computing: Verifying computations performed by remote quantum servers may depend on how much entanglement those servers can share.
• Complexity-theoretic cryptography: The LOCC variant and its collapse threshold connect to assumptions such as NP ⊄ BQP.

Industry relevance: The work is foundational rather than immediately practical. It is most relevant to quantum computing companies and research groups working on quantum verification, multiprover protocols, and the theoretical limits of entanglement-assisted computation.

Future Directions

• Can polynomially many shared EPR pairs capture NEXP? The paper notes that for polynomially bounded h, QMA(2) ⊆ QMA(2;h) ⊆ NEXP, but does not identify a setting where QMA(2;h) reaches NEXP.
• Do polynomially many EPR pairs change QMA(2) at all? Results 2 and 3 make progress but do not settle the original question. The D^{-2} loss in the Bell step prevents the current technique from handling polynomial h.
• Does the LOCC collapse extend to QMA(2;h)? The paper asks whether the same collapse occurs in the non-LOCC model, and whether QMA^flat = QMA, where the witness is promised to be a pure flat state across a fixed bipartition.
• Direct two-witness simulation: The AI disclosure mentions that later interactions produced a direct two-witness simulation bypassing QMA(4); the authors retained the four-witness proof for clarity. Further simplification or formalization may be possible.

Target Audience

This paper is aimed at researchers and graduate students in quantum computational complexity, quantum proof systems, and entanglement theory. It will be most useful to readers already familiar with QMA, QMA(2), Schmidt rank, and standard quantum verification techniques. It is not an introductory paper, but its main results are stated clearly enough for adjacent researchers to follow.

Authors’ abstract

In $\mathsf{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 $\mathsf{QMA}(2)$. To this end, we formalize $\mathsf{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: $\mathsf{QMA}(2)\subseteq\mathsf{QMA}(2;h)$ for $h=\operatorname{poly}(n)$. For logarithmically many pairs, the power of $\mathsf{QMA}(2)$ remains unchanged, strengthening this inclusion to $\mathsf{QMA}(2)=\mathsf{QMA}(2;h)$ for $h=O(\log n)$. 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 $\mathsf{NP}\nsubseteq\mathsf{BQP}$, we show that superlogarithmically many shared EPR pairs strictly reduce the model's computational power.