Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference

This paper introduces the complexity class $\sf StoqMA(2)$ for unentangled stoquastic Merlin-Arthur proof systems and demonstrates that, despite the absence of destructive interference, it is surprisingly powerful by containing $\sf NP$ with polylogarithmic error while being contained within $\sf EXP$ and $\sf PSPACE$ under specific conditions, thereby revealing the distinct computational power of unentanglement in sign-problem-free settings.

The Gist

Imagine you are trying to solve a very difficult puzzle. In the world of computer science, there are different "levels" of difficulty for these puzzles, and different types of "provers" (think of them as wizards) who try to convince a "verifier" (a skeptical judge) that they have the solution.

This paper explores a specific, unusual type of puzzle-solving contest involving two wizards who are not allowed to talk to each other (they are "unentangled") and who are restricted to using a special kind of magic that never cancels itself out (this is called "stoquasticity").

Here is a breakdown of what the authors discovered, using simple analogies:

1. The Setting: Two Wizards and a "No-Cancel" Rule

• The Wizards (Merlin): In standard quantum puzzles, wizards can use "entanglement," which is like having a secret telepathic link. If they are entangled, they can coordinate their answers perfectly. In this paper, the wizards are unentangled. They are like two strangers in a room who cannot communicate; they must each bring their own piece of the puzzle.
• The Magic (Stoquasticity): Usually, quantum magic involves waves that can cancel each other out (like noise-canceling headphones). This paper focuses on a special kind of magic where the waves never cancel. Everything is positive and additive. Think of it like a game where you can only add points to your score; you can never subtract them. This makes the math much simpler and more predictable.

2. The Big Question

The authors asked: If you take away the "telepathy" (entanglement) AND remove the "cancellation" (destructive interference), does the system become weak and easy to solve?

• The Intuition: You might think that removing both superpowers would make the wizards useless.
• The Surprise: The authors found that no, the system is still incredibly powerful. Even without telepathy and without cancellation, these two wizards can still solve very hard problems (specifically, problems in the class NP, which includes things like Sudoku and scheduling).

3. The Lower Bound: How Powerful Are They?

The paper proves that these "No-Cancel, No-Telepathy" wizards are strong enough to verify solutions for almost any problem that can be checked quickly.

• The Analogy: Imagine you have a massive library of books (the problem). Usually, you need a super-intelligent librarian with a magical connection to the books to find the right one. Here, the authors show that you only need two regular librarians who are just looking at the books independently, and they can still find the right book efficiently.
• The Catch: To do this, the wizards need to bring a "proof" that is slightly larger than usual (about the square root of the problem size), but it's still very small compared to the whole problem.

4. The Upper Bound: How Hard Are They to Solve?

The authors also asked: "How hard is it for a computer to simulate these wizards?"

• The Old Problem: For general quantum wizards (with entanglement and cancellation), we don't know the limit. The best guess is that it's so hard it takes an unimaginable amount of time (NEXP).
• The New Discovery: Because these wizards use "No-Cancel" magic, the authors found a way to simulate them much faster.
  • If the wizards are very precise (perfect completeness), the problem can be solved in PSPACE (a class of problems solvable with a lot of memory but reasonable time).
  • If the wizards are slightly less precise, the problem is in EXP (exponential time).
• The Metaphor: Imagine trying to find a needle in a haystack.
  • General Quantum: The needle might be hidden in a magical dimension that changes every second. We don't know how to find it quickly.
  • This Paper's System: The needle is in a normal haystack, but the hay is sticky and positive. The authors found a specific "sieve" (an algorithm called Sum-of-Squares) that can sift through the hay much faster than we thought possible.

5. The "Rectangular" Secret

How did they solve the upper bound? They discovered a hidden geometric structure in the way these wizards work.

• The Analogy: Imagine the wizards are trying to fill a grid. In the "No-Cancel" world, the valid solutions always form a perfect rectangle.
• The Test: The authors created a test to see if a grid is a "closed rectangle." If the wizards are telling the truth, their answers will always stay inside this rectangle. If they are lying, the rectangle will eventually "leak" or break. This geometric test allows a computer to check the wizards' claims efficiently.

6. The "Perfect" vs. "Almost Perfect" Distinction

The paper makes a subtle but important distinction:

• Without Perfect Completeness: If the wizards are allowed to make tiny mistakes, they are as powerful as the most powerful quantum systems we know (NEXP).
• With Perfect Completeness: If the wizards must be 100% perfect (no mistakes allowed), their power drops significantly (to PSPACE).
• Why it matters: This shows that the "No-Cancel" rule imposes a strict limit. You can't have the best of both worlds (perfect accuracy and maximum power) in this specific system.

Summary

This paper is a "power analysis" of a specific type of quantum proof system.

1. It's Strong: Even without entanglement and without destructive interference, two wizards can still solve very hard problems.
2. It's Controllable: Because the magic is "positive-only," we can simulate these wizards much faster than we can simulate general quantum wizards.
3. It's Optimal: The authors proved that their methods are the best possible; you can't make the wizards any stronger or the simulation any faster without breaking fundamental assumptions about computer science (specifically, the Exponential Time Hypothesis).

In short: Removing the "cancellation" feature of quantum mechanics doesn't make the system weak; it actually makes it easier to analyze while keeping it surprisingly powerful.

Technical Summary

1. Problem Statement and Motivation

The paper investigates the computational power of StoqMA(2), a complexity class defined by combining two distinct concepts in quantum complexity theory:

1. Stoquasticity: A restriction on quantum Hamiltonians (and verification circuits) where off-diagonal matrix elements are real and non-positive. This eliminates the "sign problem," preventing destructive interference and allowing the system to be modeled via stochastic processes (e.g., random walks). The class StoqMA (single prover) is known to be intermediate between MA and AM.
2. Unentanglement: The restriction that the witness (proof) provided by the prover(s) must be a separable state across multiple registers. The class QMA(2) (two unentangled provers) generalizes QMA but is notoriously difficult to bound; its best known upper bound is NEXP, and it is not known if it collapses to QMA.

The Core Question:
Does the combination of unentanglement and stoquasticity (i.e., StoqMA(2)) yield a class that is:

• Powerful enough to recover the strong lower bounds of QMA(2) (e.g., capturing NP with short proofs)?
• Restricted enough by the absence of destructive interference to admit upper bounds significantly better than NEXP (which remains the best bound for general QMA(2))?

2. Methodology

The authors employ a hybrid of techniques from quantum complexity, distribution testing, and combinatorial optimization:

• Distribution Testing via Branch-Overlap: The authors leverage the connection between StoqMA verification and distribution testing. A stoquastic verifier can be viewed as performing a "branch-overlap test" on reversible circuits. By analyzing the squared amplitudes of computational basis branches, they map the verification process to testing properties of product distributions.
• Stoquastic Product Test & Symmetrization: They develop a "stoquastic product test" to verify if a state is a product state and a "stoquastic equality test" to check if multiple proofs are identical. These tools allow them to compress multiple provers into two and symmetrize witnesses, establishing the robustness of the class definition.
• Rectangular Closure Testing: For the upper bound analysis, the authors introduce a novel combinatorial technique. They observe that for StoqMA(2) with perfect (or near-perfect) completeness, the support of the witness state forms a "rectangle" (a Cartesian product of two sets). They design an algorithm to test the "rectangular closure" of these sets under the verifier's permutation. If the set is not closed, the "escaping mass" grows exponentially, leading to rejection.
• Sum-of-Squares (SoS) Hierarchy: For the general upper bound, they utilize and refine the Sum-of-Squares algorithm by Barak, Kelner, and Steurer (BKS). They tighten the analysis of the BKS algorithm to show that the degree of the required SoS relaxation depends quadratically on the number of provers ($t^2$) rather than cubically ($t^3$), which is crucial for establishing optimality under the Exponential Time Hypothesis (ETH).

3. Key Contributions and Results

A. Lower Bounds: Power of Unentanglement

The paper demonstrates that StoqMA(2) is surprisingly powerful, recovering the best-known lower bounds for QMA(2) despite the lack of destructive interference.

• Short Proofs for NP:
  • Result: $\text{NP} \subseteq \text{StoqMA}(2)$ with $\tilde{O}(\sqrt{n})$-qubit proofs and completeness error $2^{-\text{polylog}(n)}$.
  • Significance: This matches the best-known QMA(2) protocols (e.g., [ABD+09, CD10]) that use $\tilde{O}(\sqrt{n})$ qubits to capture NP, except for the loss of perfect completeness.
  • Logarithmic Proofs: They also show $\text{NP} \subseteq \text{StoqMA}(2)$ with $O(\log n)$-qubit proofs and inverse-polynomial gap, matching the Blier-Tapp protocol [BT12].
• Precise Complexity:
  • Result: $\text{PreciseStoqMA}(2) = \text{NEXP}$.
  • Significance: This establishes that with exponentially small promise gaps, StoqMA(2) is as powerful as PreciseQMA(2).
• Robustness: They prove that for negligible completeness error, $\text{StoqMA}(k) = \text{StoqMA}(2)$ for any $k \ge 2$, showing the class is robust under prover compression.

B. Upper Bounds: Structural Limitations

The authors show that stoquasticity imposes exploitable structure, yielding upper bounds much stronger than the trivial NEXP bound for QMA(2).

• Near-Perfect Completeness:
  • Result: $\text{StoqMA}(2)^1$ (with completeness error $2^{-2^{\text{poly}(n)}}$) is contained in PSPACE.
  • Result: $\text{PreciseStoqMA}(2)^1$ (with triple-exponentially small error) is contained in EXP.
  • Significance: This contrasts sharply with QMA(2), where even perfect completeness does not yield a better bound than NEXP. It implies that $\text{PreciseStoqMA}(2)^1 \subsetneq \text{PreciseStoqMA}(2)$ unless $\text{EXP} = \text{NEXP}$, highlighting a fundamental difference between single-prover and multi-prover stoquastic systems regarding perfect completeness.
• General Upper Bound:
  • Result: $\text{StoqMA}(k) \subseteq \text{EXP}$ for polynomially bounded $k$.
  • Method: Derived via a refined Sum-of-Squares (SoS) algorithm.
  • Optimality: The authors prove that their parameters are essentially optimal under the Exponential Time Hypothesis (ETH). Any improvement in the dependence on the number of provers or proof length in their protocols or the SoS algorithm would imply a subexponential-time algorithm for SAT, violating ETH.

C. Separation of Perfect Completeness

A subtle but significant finding is the behavior of perfect completeness:

• In the single-prover case, $\text{PreciseStoqMA} = \text{PreciseStoqMA}^1 = \text{PSPACE}$.
• In the two-prover case, $\text{PreciseStoqMA}(2) = \text{NEXP}$, but $\text{PreciseStoqMA}(2)^1 \subseteq \text{EXP}$.
• This suggests that the power of unentanglement in the precise regime is lost when perfect completeness is enforced, a phenomenon not observed in the general quantum case (where $\text{PreciseQMA}(2) = \text{PreciseQMA}(2)^1$).

4. Significance and Impact

1. Bridging Quantum and Classical: The paper provides a rigorous framework for understanding how "sign-problem-free" quantum systems (stoquastic) behave when combined with the non-convex constraint of unentanglement. It shows that while unentanglement boosts power (capturing NEXP), the lack of destructive interference (stoquasticity) simultaneously restricts the class enough to fall within EXP/PSPACE for specific error regimes.
2. Optimality of Algorithms: By tightening the analysis of the BKS Sum-of-Squares algorithm, the authors establish that current algorithms for tensor optimization are likely optimal under ETH. This provides a concrete barrier for future algorithmic improvements in this domain.
3. New Techniques: The introduction of Rectangular Closure Testing offers a new combinatorial tool for analyzing separable states in stoquastic systems, potentially applicable to other problems involving product states and local Hamiltonians.
4. Complexity Landscape: The results refine the hierarchy of quantum complexity classes, specifically clarifying the relationship between MA, AM, StoqMA, QMA, and QMA(2) under various constraints (unentanglement, sign problem, perfect completeness).

In summary, the paper demonstrates that StoqMA(2) is a "sweet spot" in complexity theory: it is powerful enough to simulate the hardest known unentangled proof systems (NEXP) but structured enough (due to stoquasticity) to admit efficient upper bounds (EXP/PSPACE) that are impossible for general QMA(2).