The Complexity of Stoquastic Sparse Hamiltonians

This paper establishes that the Stoquastic Sparse Hamiltonians problem is $\mathsf{StoqMA}$-complete and that its separable version is $\mathsf{StoqMA}(2)$-complete, thereby advancing the understanding of the power of the $\mathsf{StoqMA}$ complexity class.

The Gist

The Big Picture: The "Energy" Puzzle

Imagine you have a giant, complex machine made of thousands of tiny switches (quantum bits, or qubits). This machine has a specific "ground state," which is like its resting position or its lowest energy setting.

In the world of quantum physics, figuring out exactly what that lowest energy setting is for a complex machine is incredibly hard. It's like trying to find the absolute lowest point in a vast, foggy mountain range without a map. Computer scientists call this the Local Hamiltonian Problem.

Usually, this problem is so hard that it belongs to a class of problems called QMA (Quantum Merlin-Arthur). Think of QMA as a game where a powerful wizard (Merlin) tries to convince a skeptical judge (Arthur) that they found the lowest point. The judge can check the wizard's answer using a quantum computer.

The Special Case: "Stoquastic" Machines

The paper focuses on a special type of machine called a Stoquastic Hamiltonian.

• The Analogy: Imagine a normal machine where the switches can push or pull in confusing, negative ways (like a tug-of-war where the rope goes through a wall). This causes a "sign problem" that makes classical computers (like your laptop) fail to simulate them.
• The Stoquastic Difference: A Stoquastic machine is "nice." All its switches only push or pull in a way that keeps things positive. There are no confusing negative signs. Because of this, classical computers can simulate them much better using methods like Monte Carlo simulations (random guessing that gets smarter over time).

Even though these machines are "nicer," figuring out their lowest energy is still hard. It turns out this specific problem belongs to a class called StoqMA. This is a middle-ground class between standard classical guessing (MA) and more advanced classical guessing (AM).

The Main Discovery: Sparsity vs. Locality

The authors wanted to understand StoqMA better. To do this, they looked at a specific type of machine: Sparse Hamiltonians.

• Local Hamiltonians: Imagine a machine where every switch only talks to its immediate neighbors (like people in a line only talking to the person next to them).
• Sparse Hamiltonians: Imagine a machine where a switch might talk to anyone in the room, but each switch only talks to a very small, fixed number of people (say, 10 people out of a million). It's "sparse" because most connections are empty.

The Paper's Claim:
The authors proved that figuring out the lowest energy of these "Sparse" machines is exactly as hard as the "Local" machines.

• The Result: The "Stoquastic Sparse Hamiltonian" problem is StoqMA-complete.
• What this means: If you can solve the sparse version efficiently, you can solve the local version, and vice versa. They are equally difficult. This is surprising because sparse machines are much more general and flexible than local ones, yet they don't get any "easier" to solve in this specific quantum context.

How They Did It: The "Hadamard" Test

To prove this, the authors had to build a new way for the judge (Arthur) to check the wizard's (Merlin's) answer.

• The Problem: The usual way to check energy involves complex quantum math (Phase Estimation) that the "Stoquastic" judge isn't allowed to do because their tools are too simple (they can't handle the "negative" math).
• The Solution: The authors invented a clever trick. They broke the big machine down into tiny, single-connection pieces (1-sparse terms). Then, they created a "Hadamard-like" test.
  • The Metaphor: Imagine the judge asks the wizard to hold a coin. The judge flips a switch that randomly connects the coin to a specific neighbor. The judge then checks if the coin landed in a specific way. By doing this many times with different random connections, the judge can calculate the total energy of the machine without needing a full quantum supercomputer.

The "Separable" Twist: Two Wizards, No Telepathy

The paper also looked at a variation called the Separable Stoquastic Sparse Hamiltonian.

• The Scenario: Imagine the machine is split into two halves (Left and Right). The judge wants to know the lowest energy, but with a rule: The wizard must provide two separate, unentangled answers (one for the Left half, one for the Right). They cannot share a "quantum telepathy" link (entanglement) between them.
• The Result: The authors showed that this specific problem is StoqMA(2)-complete.
  • StoqMA(2) is a class where the judge gets two unentangled wizards.
  • This is a big deal because it shows that even if you force the wizards to work separately (no quantum teamwork), the problem remains just as hard as the general case.

The "Two Wizards are Enough" Rule

Finally, the authors asked: "What if we have three wizards, or ten wizards? Does that make the judge's job easier or harder?"

• The Finding: They proved that for this specific type of quantum game, two wizards are enough.
• The Analogy: Even if you have a team of 100 wizards trying to convince the judge, the judge can simulate the whole team by just asking two of them to send the exact same message and checking if they are telling the truth. You don't need more than two to capture the full power of the system.

Summary

1. Stoquastic machines are a special, "nicer" kind of quantum machine that avoids the "sign problem."
2. The authors proved that finding the lowest energy of Sparse Stoquastic machines is just as hard as finding it for Local ones. Both are StoqMA-complete.
3. They developed a new testing method that allows a restricted judge to verify these energies without needing full quantum power.
4. They showed that even if you split the machine in half and force the wizards to work separately, the problem remains hard (StoqMA(2)-complete).
5. They proved that having more than two unentangled wizards doesn't give you any extra power; two are sufficient to simulate any number of them.

This work helps map the landscape of quantum complexity, showing exactly where the "hard" problems live and how different types of quantum machines relate to one another.

Technical Summary

Problem Statement

The paper addresses the computational complexity of the Stoquastic Sparse Hamiltonian (StoqSH) problem. While the complexity of local stoquastic Hamiltonians is well-understood (known to be StoqMA-complete), the complexity of sparse stoquastic Hamiltonians had not been directly established.

Sparse Hamiltonians are a broader class than local Hamiltonians; a $k$-local Hamiltonian with $m$ terms is $2^{km}$-sparse. The StoqSH problem asks, given a $d$-sparse stoquastic Hamiltonian $H$ (where off-diagonal elements are non-positive) and parameters $\alpha, \beta$, whether the ground state energy $\lambda_{\min}(H) \le \alpha$ or $\lambda_{\min}(H) \ge \beta$, promised that one case holds.

The central challenge is that standard techniques for proving containment in StoqMA for local Hamiltonians (which rely on converting local terms into specific projections) do not extend to the sparse setting. Furthermore, standard quantum verification methods like Phase Estimation (used for general sparse Hamiltonians in QMA) are inherently quantum and cannot be simulated by the restricted stoquastic verifiers, which are limited to classical reversible circuits and Hadamard basis measurements.

Methodology

The authors employ a verification procedure that bridges the gap between sparse Hamiltonian structure and the limitations of stoquastic verifiers. The methodology consists of three main components:

1. Sparse Decomposition:
   The authors utilize a known decomposition (from [BCC+14]) where any $d$-sparse Hamiltonian $H$ can be written as a sum of $d^2$ 1-sparse terms ($H = \sum H_j$). Crucially, if $H$ is stoquastic, each term $H_j$ in this decomposition is also stoquastic, and the non-zero matrix elements are uniquely assigned to specific terms.

2. Generalized StoqMA Verifiers (gStoqMA):
   To handle the verification, the authors introduce a generalization of the StoqMA verifier. Standard StoqMA verifiers measure a single qubit in the Hadamard basis. The authors define gStoqMA, where the verifier can measure a polynomial number of qubits in the Hadamard, $|0\rangle$, or $|1\rangle$ bases.

   • They prove that this generalization does not increase the computational power of the class; it can be simulated by a standard StoqMA verifier with a linear loss in the completeness/soundness gap (Theorem 1.2). This allows the use of multi-qubit measurements (specifically Swap tests) within the stoquastic framework.

3. Verification Procedure for StoqSH:
   The core contribution is a verification protocol for StoqSH that accepts a witness state $|\psi\rangle$ with a probability linearly related to the energy expectation $\langle \psi | H | \psi \rangle$. The verifier randomly chooses between two sub-procedures ($V_1$ and $V_2$):

   • Procedure $V_1$: Uses the oracle for the Hamiltonian matrix elements to construct a state dependent on $|\psi\rangle$ and the 1-sparse term $H_j$. It performs a "Hadamard-like" test involving a controlled oracle query and measurements in the $X$ and $Z$ bases. The acceptance probability relates to the off-diagonal elements and the energy.
   • Procedure $V_2$: A complementary procedure that measures the last qubit in the $Z$ basis.
   • Combined Result: By averaging the acceptance probabilities of $V_1$ and $V_2$, the total acceptance probability becomes $1/2 - \frac{1}{4d^2}\langle \psi | H | \psi \rangle$. This linear relationship allows the verifier to distinguish between low-energy (YES) and high-energy (NO) instances.

Key Contributions and Results

1. StoqMA-Completeness of StoqSH
The primary result is Theorem 1.1, which states that the Stoquastic Sparse Hamiltonian problem is StoqMA-complete.

• Hardness: Follows immediately because local stoquastic Hamiltonians are a special case of sparse stoquastic Hamiltonians and are already known to be StoqMA-hard.
• Containment: Established via the verification procedure described above, proving that StoqSH $\in$ StoqMA.

2. Separable Stoquastic Sparse Hamiltonians and StoqMA(2)
The authors extend their analysis to the Separable Stoquastic Sparse Hamiltonian (SepStoqSH) problem, where the witness is restricted to be a product state $|\psi\rangle = |\chi_A\rangle \otimes |\chi_B\rangle$.

• They define StoqMA(k), the stoquastic analogue of QMA(k), involving $k$ unentangled provers.
• Theorem 1.4 (Simplified): They show that for certain completeness and soundness parameters, $k$ provers can be simulated by 2 provers ($StoqMA(k) \subseteq StoqMA(2)$). The proof adapts the "Product Test" protocol from [HM13] to the stoquastic setting, leveraging the ability of stoquastic verifiers to perform multi-qubit measurements (via the gStoqMA generalization).
• Theorem 4.5: The SepStoqSH problem is StoqMA(2)-complete. The hardness proof adapts the circuit-to-Hamiltonian construction for separable sparse Hamiltonians [CS12] to the stoquastic setting, utilizing perturbation theory to handle the lack of error amplification in StoqMA(2).

3. Generalization of StoqMA
The paper introduces gStoqMA and proves that allowing polynomial-sized measurements does not increase the class's power beyond a parameter shift (Theorem 3.5). This property is highlighted as potentially of independent interest for the study of stoquastic proof systems.

Significance and Claims

The paper claims to advance the understanding of the StoqMA complexity class, which sits between the randomized classes MA and AM ($NP \subseteq MA \subseteq StoqMA \subseteq AM$).

• Completeness: By identifying StoqSH as a complete problem for StoqMA, the authors provide a more general natural problem for this class, moving beyond restricted local models.
• Separable Proofs: The work places StoqMA(2) as an interesting intermediate model between single-prover stoquastic verification and general multi-prover quantum verification. It provides a natural complete problem (SepStoqSH) for StoqMA(2), analogous to the role of separable sparse Hamiltonians for QMA(2).
• Robustness: The results suggest that the power of stoquastic verifiers is robust even when the witness is restricted to be separable, provided the Hamiltonian is sparse.

The authors note that while they show StoqMA(k) collapses to StoqMA(2) for specific parameters, the robustness of this collapse under tighter error bounds remains an open question. Additionally, the complexity of the Separable Stoquastic Local Hamiltonian problem remains open, as current techniques for local density matrix consistency do not directly apply to the stoquastic setting.

In summary, the paper establishes the computational hardness of sparse stoquastic Hamiltonians, introduces a new verification technique utilizing multi-qubit measurements, and characterizes the power of stoquastic proof systems with multiple unentangled provers.