PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity of stoquastic frustration-free Hamiltonians

Sergey Bravyi, Barbara Terhal

arXiv:0806.1746v1quant-ph

TL;DR

The paper asks how stoquastic frustration-free Hamiltonians connect quantum computation with classical probabilistic computation, and how their satisfiability problem fits into complexity theory. It analyzes random walks for these Hamiltonians and defines stoquastic k-SAT. It gives a classical sampling result for suitable adiabatic paths and shows that stoquastic 6-SAT captures MA promise problems under Karp reductions.

  • Problem

    The paper examines how much adiabatic evolution and ground-state complexity can be understood for stoquastic frustration-free Hamiltonians at the boundary of quantum and classical probabilistic computation.

    Source: §1 · pp. 1–2, §1.1 · p. 3

  • Method

    It analyzes a random-walk algorithm for simulating ground-state properties and formulates stoquastic k-SAT as a promise problem verified through a walk.

    Source: §2.1 · p. 5, §2.3 · p. 8

  • Results

    Under the stated adiabatic conditions, classical sampling approximates the final ground-state distribution within δ in time poly(n, δ^-1); stoquastic k-SAT is in MA for constant k and MA-reduces to stoquastic 6-SAT.

    Source: §1.1 · pp. 2, 4

  • Takeaways & Limitations

    Stoquastic 6-SAT provides a Cook-Levin-style characterization of MA promise problems.

    Source: §1.1 · p. 4

    The results do not settle classical simulation of general stoquastic adiabatic evolution, and no efficient algorithm is known for computing the required ground-state amplitude ratios.

    Source: §7 · p. 18

Abstract

from arXiv · show

We study several problems related to properties of non-negative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a "frustration free" ground-state. A Hamiltonian belongs to this class iff it can be represented as $H=\sum_a H_a$ where (1) every term $H_a$ acts non-trivially on a constant number of qubits, (2) every term $H_a$ has real non-positive off-diagonal matrix elements in the standard basis, and (3) the ground-state of $H$ is a ground-state of every term $H_a$. Secondly, we generalize the Cook-Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA -- a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call "stoquastic k-SAT" such that stoquastic k-SAT is contained in MA for any constant $k$, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first non-trivial example of a MA-complete promise problem.

1. Introduction.

The paper studies stoquastic frustration-free Hamiltonians at the boundary of quantum and classical probabilistic computation. It presents classical simulation results for adiabatic evolution and an MA-completeness result for stoquastic k-SAT.

1. Introduction.

  • Local-Hamiltonian ground-state properties connect quantum complexity to computation: adiabatic evolution can encode quantum algorithms [2], while ground-state energy is QMA-complete.The paper frames these results as a way to study quantum and matrix-valued complexity theory.Source: §1 · p. 1
  • The paper studies frustration-free local Hamiltonians whose terms are positive semidefinite and share a zero-energy ground state, with real non-positive off-diagonal entries in the standard basis.The terms act non-trivially on at most a constant number of qubits.Source: §1 · p. 2
  • For adiabatic paths satisfying the stated smoothness, gap, non-degeneracy, and initial-overlap conditions, the paper gives a classical probabilistic simulation for stoquastic frustration-free Hamiltonians.The path must remain stoquastic and frustration-free; the paper notes it need not be a linear interpolation because that can prevent frustration-freeness.Source: §1 · p. 1, §1.1 · p. 2

1.1. Summary of results.

  • The simulation samples from the final ground state's computational-basis distribution, and the adiabatic path is not required to be a linear interpolation.A linear interpolation may make it impossible to maintain frustration-freeness.Source: §1.1 · p. 2
  • Stoquastic k-SAT is in MA for every constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT, generalizing Cook-Levin to MA.Stoquastic k-SAT includes classical k-SAT as the special case of diagonal constraints.Source: §1.1 · p. 4

1.2. Previous work.

  • Prior work placed stoquastic ground-state energy in AM and represented coherent Gibbs states of classical local Hamiltonians as unique stoquastic frustration-free ground states [19].The paper also describes earlier links between stoquastic Hamiltonians and sampling from reversible Markov-chain stationary distributions [17].Source: §1.2 · pp. 4–5

2. Techniques.

The techniques rely on random walks built from non-negative ground states and projectors. The paper uses these walks both to track adiabatic ground-state distributions and to verify stoquastic k-SAT instances.

2. Techniques.

  • A random walk algorithm is the paper's main technical tool for simulating ground-state properties of stoquastic frustration-free Hamiltonians, with rigorous runtime and error bounds unlike GFMC's heuristic use.The paper compares its approach with Green Function Monte Carlo.Source: §2.1 · p. 5

2.1. A random walk associated with a SFF Hamiltonian.

  • Non-negative ground-state amplitudes define a walk on the state's support with stationary distribution given by squared amplitudes, and local terms make each step efficiently simulatable.The support may depend on the ground state; a Hamiltonian can have distinct stationary distributions on disjoint supports.Source: §2.1 · pp. 5–6

2.2. Simulation of the adiabatic evolution.

  • Adiabatic simulation advances between walks by using warm starts: sufficiently fine discretization and mixing let one walk's endpoint seed the next with high probability.The analysis uses t-balanced strings and bounds the walk's spectral gap using the Hamiltonian gap.Source: §2.2 · pp. 6–7

2.3. Stoquastic k-SAT is contained in MA.

  • For stoquastic k-SAT, the verifier receives a witness string and simulates a walk that rejects upon reaching a bad string; positive instances support a walk within satisfying assignments.For negative instances, the probability of avoiding bad strings decays approximately as (1 − βǫ/M)^L, becoming exponentially small for polynomial L.Source: §2.3 · pp. 7–8

2.4. MA-hardness.

  • The MA-hardness argument for stoquastic 6-SAT follows from the MA-hardness of the stoquastic 6-local Hamiltonian problem and is reproduced with minor modifications.The cited prior result is Lemma 3 in.Source: §2.4 · p. 8

3. Examples of stoquastic frustration-free Hamiltonians.

The examples show that stoquastic frustration-free Hamiltonians can represent coherent versions of classical probability distributions. They cover Gibbs states and outputs of classical reversible circuits.

3.1. Coherent thermal states of classical Hamiltonians.

  • A coherent version of a Gibbs state for a classical local Hamiltonian can be the unique ground state of a stoquastic frustration-free Hamiltonian.Measuring the coherent Gibbs state in the standard basis samples the Gibbs distribution.Source: §3.1 · pp. 8–9

3. Examples of stoquastic frustration-free Hamiltonians.

  • For any precision δ > 0, a SFF Hamiltonian acting on poly(n, δ−1) qubits has a unique ground state |ψ⟩ with overlap at least 1−δ with |π⟩⊗|φa⟩ for some simple ancillary state |φa⟩.Source: §3.2 · p. 9

3.2. Coherent probabilistic computation.

  • For a polynomial-size classical reversible circuit, a coherent version of its output distribution can be approximated by a unique ground state of a stoquastic frustration-free Hamiltonian.For precision δ, the construction uses poly(n, δ^-1) qubits and a clock-Hamiltonian construction.Source: §3.2 · p. 9, §3.1 · p. 9

4. Non-negative matrices: basic properties.

The section establishes structural properties of non-negative projectors and ground spaces that support the paper's random-walk arguments. In particular, stoquastic ground spaces admit non-negative bases, and local transitions from a supported string preserve support.

4. Non-negative matrices: basic properties.

  • For a Hermitian operator with non-positive off-diagonal entries, the projector onto its smallest-eigenvalue subspace is non-negative.The proof expresses the projector as a scaled zero-temperature limit of e^-βH, whose matrix is non-negative.Source: §4 · p. 9
  • Every non-negative projector decomposes into orthogonal non-negative states, with disjoint supports forming rank-one blocks.The block structure follows from positivity of entries within each connected block and the Perron-Frobenius theorem.Source: §4 · pp. 9–10
  • The ground subspace of any stoquastic Hamiltonian has an orthonormal basis of non-negative ground states.This follows by applying the projector characterization to the ground-space projector.Source: §4 · pp. 9–10
  • In a stoquastic frustration-free Hamiltonian, a negative off-diagonal transition from a supported string leads to another string in the same ground-state support.This support-closure property follows from the non-negative local zero-energy projectors and the lemma on their action on non-negative states.Source: §4 · pp. 10–11

5. Simulation of the adiabatic evolution.

The simulation tracks ground-state distributions with random walks and controls whether each step begins from a warm start. A spectral-gap and overlap argument bounds the probability that this condition fails along the path.

5. Simulation of the adiabatic evolution.

  • The nonnegative operator G(j) has a unique top eigenvector |ψ(j)⟩ and a spectral gap of at least βΔ.The associated walk P(j) inherits a spectral gap of at least βΔ, supporting the bound on fidelity between consecutive stationary distributions.Source: §5 · p. 12
  • The algorithm generates strings by taking L steps of P(j), starting from a string with nonzero ground-state amplitude.At each stage, the endpoint becomes the starting string for the next walk.Source: §5 · pp. 11–12
  • A warm start is a string whose probabilities under two distributions have ratio between t^-1 and t.The argument uses t-balanced strings to show that a sample from one stationary distribution is likely to be a warm start for the next.Source: §5 · pp. 13–14
  • The simulation scheme fails with probability at most δ ∼ J^2Δ^-2T^-1, with T = poly(n, δ^-1).The bound follows from maintaining the warm-start condition across the walk sequence.Source: §5 · p. 14

6. Stoquastic k-SAT is contained in MA.

The paper gives a one-message prover-verifier protocol for stoquastic k-SAT and analyzes its completeness and soundness. It also describes a graph-walk interpretation for a simplified class of constraints.

6. Stoquastic k-SAT is contained in MA.

  • The prover sends a string w, and the verifier runs a random walk using randomly selected constraints and checks the visited strings.The prover's proposed string is the largest-amplitude basis string of a satisfying assignment in a yes-instance.Source: §6 · pp. 14–15

6.1. Completeness of the protocol.

  • For yes-instances, the verifier outputs yes with probability 1 when the prover supplies a satisfying assignment's largest-amplitude string.The walk stays within the satisfying state's support, and the endpoint test is passed.Source: §6.1 · pp. 15–16

6.2. Soundness of the protocol.

  • For no-instances, the verifier outputs yes with probability at most 1/3.With finite-precision transition probabilities, the acceptance-probability correction is of order Lδ and can be controlled by choosing δ ≪ L^-1.Source: §6.2 · pp. 16–17

6.3. Simplified stoquastic k-SAT.

  • For projectors with matrix elements 0, 1/2, and 1, constraints define a graph whose edges join strings coupled by a projector.The walk moves to a neighboring vertex with probability 1/(2M), otherwise staying put; satisfiability is equivalent to a connected component containing only good vertices.Source: §6.3 · p. 17

7. Discussion.

The discussion explains why randomness is needed for the simplified stoquastic k-SAT verifier and identifies derandomization and broader stoquastic simulation as open questions.

Discussion

  • Randomness is needed because an all-good connected component may be exponentially large to explore or list, while promised no-instances yield bad vertices under random walks.For yes-instances, a walk from a prover-supplied vertex in the good component stays within it.Source: §7 · p. 18
  • General stoquastic adiabatic simulation remains open because efficient computation of ground-state amplitude ratios is unknown, and a modified walk's stationary distribution may not relate to ground-state weights.Source: §7 · p. 18

Appendix A.

Appendix A defines MA and MA-completeness for promise problems, motivating this formulation by the lack of known MA-complete problems or problems in MA not known to lie in NP.

Appendix A

  • The paper motivates the study of MA promise problems by noting that no MA-complete problems or problems in MA not known to be in NP were then known.Source: Appendix A · p. 18
  • An MA verifier runs in probabilistic polynomial time, accepts some witness with probability 1 on yes-instances, and accepts every witness with probability at most 1/3 on no-instances.Source: Appendix A · p. 19
  • MA-completeness requires every MA promise problem to reduce to the problem via a deterministic polynomial-time mapping.Source: Appendix A · p. 19
  • MA is treated as a class of promise problems, separating yes-instances from no-instances and allowing verifier behavior outside the promise to be arbitrary.Source: Appendix A · p. 19

Appendix B.

Appendix B uses clock Hamiltonians to relate circuit computation to frustration-free constraints, prove adiabatic-simulation properties, and establish MA-hardness of stoquastic 6-SAT.

Appendix B

  • The section's three aims are to prove the adiabatic-simulation proposition, establish MA-hardness of stoquastic 6-SAT, and explain the SFF connection to classical probabilistic computation.The arguments draw on the clock-Hamiltonian construction and prior analyses.Source: Appendix B · p. 19
  • The clock Hamiltonian encodes circuit time in unary and constrains ancilla initialization and gate-by-gate propagation, yielding a frustration-free ground subspace of legal computational paths.Source: Appendix B · pp. 19–20
  • The clock Hamiltonian has spectral gap Ω(1/L^2), and its ground state approximates the circuit output when the final 1−δ fraction of gates are identities.Source: Appendix B · p. 20
  • The MA-hardness construction converts a classical verifier into one using classical reversible gates, ancillary states, and an encoded final-measurement constraint.Source: Appendix B · p. 21
  • The resulting constraint system is stoquastic 6-SAT; perfect acceptance gives unsat(C)=0, whereas acceptance at most 1−ε yields inverse-polynomial unsat and MA-hardness.Source: Appendix B · p. 21
Loading 0806.1746v1…