REVIEW
The Complexity of Stoquastic Local Hamiltonian Problems
Quantum Physics · Submitted 16 Jun 2006 · 31 references
Pith's verdict: The AM containment is solid and is the result that matters; the 2-local MA-hardness claim leans on a perturbative gadget whose error control is order-counting rather than a proved remainder bound.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Stoquastic local Hamiltonians — those whose off-diagonal entries are real and non-positive — have a ground-energy problem that lies in AM, is MA-hard at 2-local, and falls into PostBPP when the spectral gap is polynomially large.
The reading
What carries the argument
Three devices carry the argument. First, the trace-power-to-cardinality reduction: $Tr(G^L)$ for a non-negative black-box matrix is rewritten as $2^{-mL}|Omega|$ for a set $Omega$ whose membership test is a product of $L$ matrix elements, converting an eigenvalue question into the Approximate Set Size problem that AM can handle. Second, the clock Hamiltonian built from a circuit of Toffoli gates acting on $|+rangle$ coin qubits and a quantum witness; because every gate is classical and reversible and every coin enters in a non-negative superposition, all off-diagonal entries of the resulting Hamiltonian are non-positive, which is what makes the MA-hardness construction land inside the stoquastic class. Third, the perturbation gadgets: a subdivision gadget reducing $k$-local to $3$-local interactions, a new three-qubit gadget whose mediator Hamiltonian $-tfrac{1}{2}Delta_x (X_1X_2X_3 - I) - tfrac{1}{4}Delta_z (Z_1Z_2 + Z_2Z_3 + Z_1Z_3 - 3I)$ forbids direct transitions between its ground state $|Psi^+rangle$ and first excited state $|Psi^-rangle$ so that the leading correction is the desired triple-$X$ term, and the original Kempe-Kitaev-Regev three-qubit gadget for the final step to 2-local. The post-selection argument is the fourth device: extending $G$ to a doubly-stochastic $F$ on one extra qubit lets a random walk leak out of under-normalized rows, and conditioning on the leak never happening yields independent samples from a distribution close to the ground state.
Extended reading notes
Core claim
The central claim is that the Local Hamiltonian Problem restricted to stoquastic Hamiltonians belongs to AM. The route is a reduction to approximate counting. Given a stoquastic $H$, form the non-negative matrix $G = I - H/C$ with $C$ a polynomial bound on $||H||$, whose largest eigenvalue is $1 - O(1/C)$ times the ground energy, and consider $Z = Tr(G^L)$ for $L = 2n p_1(n)$. For positive instances $Z$ is at least $(1-O(1/C))^L$ times the negative-instance value, a separation of order $2^n$. Writing $G$ as an average of $0,1$-matrices $G(t)$ over a short random string $t$ turns $Z$ into a sum of an efficiently computable Boolean function $F$ over strings of length $(m+n)L$, so $Z$ is proportional to the cardinality of an explicitly verifiable set $Omega$. Merlin then proves a lower bound on $|Omega|$ using the Goldwasser-Sipser two-round approximate counting protocol with Carter-Wegman universal hashing, which is exactly what AM allows. Two further results bracket the problem from below and from the side: 6-local (hence, after gadget reductions, 2-local) stoquastic LH-MIN is MA-hard, proved by compiling an MA verifier into a circuit of classical reversible gates fed with $|+rangle$ coins and applying Kitaev's clock construction, whose Hamiltonian stays stoquastic; and if the Hamiltonian has a polynomial spectral gap, a post-selected classical random walk on a doubly-stochastic extension of $G$ samples from the ground-state distribution well enough to estimate the top eigenvalue, placing the problem in PostBPP.
Load-bearing premise
The reduction from $k$-local to 2-local stoquastic Hamiltonians rests on a perturbative gadget whose error is estimated by counting powers of small parameters rather than by a theorem with explicit constants: the self-energy is computed to third order, the fourth-order term is bounded only by order of magnitude, and a footnote absorbs all factors of the interaction norms and the number of terms into an order-one constant on the grounds that the energy penalty can be chosen polynomially large.
Editorial extensions
If this is right
- Unless QMA is contained in AM, no stoquastic local Hamiltonian problem is QMA-complete, so the folklore mapping of $d$-dimensional quantum ground states onto $(d+1)$-dimensional classical statistical models cannot hold in the generality it is usually stated.
- Because 2-local stoquastic LH-MIN is MA-hard and also in AM, the complexity of the problem does not change with the locality $k$ for constant $k$, which is evidence that it is complete for some class strictly between MA and AM.
- Any decision problem solved by an adiabatic quantum algorithm whose path uses only stoquastic Hamiltonians with polynomial gap lies in PostBPP, and hence in $Sigma_3^p$.
- Combined with Barahona's NP-hardness of Ising spin-glass ground states, the results bracket stoquastic LH-MIN between NP-hard and AM.
- The AM argument applies to any non-negative black-box matrix with efficiently computable entries, not only to local Hamiltonians, so it covers stoquastic systems lacking locality or sparsity structure.
Reading between the lines
- The authors remark that a sequel strengthens the upper bound to SBP; if that holds, the natural next target is a completeness theorem placing stoquastic LH-MIN exactly at some class between MA and AM, which would make the locality-independence result a statement about a genuine complexity class rather than an interval.
- The PostBPP simulation cost is set by the gap, not the system size: the number of post-selected walks scales like $n^{2c}$ for target precision $n^{-c}$ and the walk length like $5n,r(n)^2$ where $r$ encodes the gap, so a shrinking gap is the real resource, which suggests testing the algorithm's practical behaviour on gapped versus nearly gapless instances of the same size.
- The AM proof needs only entry-wise non-negativity of $G$, so the operative boundary is non-negativity of the Gibbs matrix rather than any spin-model structure; this predicts that a system made stoquastic by a local basis change remains in AM even when the change destroys geometric locality, which is a claim worth checking against specific frustrated models.
- The MA-hardness construction uses only classical reversible gates plus $|+rangle$ coins, and the authors note that a final measurement in the $x$-basis might still leave the Hamiltonian stoquastic; if so, the gap between the MA lower bound and the AM upper bound could narrow without any new counting machinery.
Original abstract
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class AM -- a probabilistic version of NP with two rounds of communication between the prover and the verifier. We also show that 2-local stoquastic LH-MIN is hard for the class MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class POSTBPP=BPPpath -- a generalization of BPP in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians lies in PostBPP.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class AM -- a probabilistic version of NP with two rounds of communication between the prover and the verifier. We also show that 2-local stoquastic LH-MIN is hard for the class MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class POSTBPP=BPPpath -- a generalization of BPP in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians lies in PostBPP.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: all off-diagonal matrix elements in the standard basis are real and non-positive. | contribution 0.76 | 0.73 | 0.05 | asserted 0.75 |
| s1 | We will call such Hamiltonians, which are common in the natural world, stoquastic. | background 0.90 | 0.34 | 0.02 | asserted 0.99 |
| s2 | An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. | background 0.97 | 0.22 | 0.03 | asserted 1.00 |
| s3 | We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class AM -- a probabilistic version of NP with two rounds of communication between the prover and the verifier. | result 1.00 | 0.96 | 0.60 | asserted 1.00 |
| s4 | We also show that 2-local stoquastic LH-MIN is hard for the class MA. | result 0.99 | 0.96 | 0.10 | asserted 1.00 |
| s5 | With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class POSTBPP=BPPpath -- a generalization of BPP in which a post-selective readout is allowed. | result 1.00 | 0.95 | 0.15 | asserted 1.00 |
| s6 | This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians lies in PostBPP. | interpretation 0.95 | 0.85 | 0.14 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v4
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:quant-ph/0606140 by the authors.
References
How later papers used it
59 later papers cite it
1 later paper by other authors is listed below: 1 built on it.
Builds on it 1 paper
-
Added a step to this chain of reductions, obtaining universal stochastic and stoquastic Hamiltonians resembling those arising in some systems of superconducting qubits.
QMA-complete problems for stoquastic Hamiltonians and Markov matrices (2009) · 0.90 · paraphrased: the licence does not allow quoting
How the literature uses it
58 arXiv papers cite this in 96 sentences
Papers citing it · 59 sentences without a confident label
Builds on it 1 paper
-
Here we add one more step to this chain, obtaining universal stochastic and stoquastic Hamiltonians which resemble those arising in some systems of superconducting qubits [ref] .
QMA-complete problems for stoquastic Hamiltonians and Markov matrices · Discussion and conclusions · 0.90
Uses its method or tool 1 paper
-
The MAhardness reduction utilises the Feynman-Kitaev clock construction, specifically the proof of Bravyi et al. [ref] who originally considered this idea for the Local Stoquastic Hamiltonian problem.
On the Complexity of the Succinct State Local Hamiltonian Problem · Class Hardness · 0.87
Cites it as background 29 papers
-
In [ref] it was shown that for any fixed $k$, stoquastic $k$-local Hamiltonian is contained in the complexity class AM.
QMA-complete problems for stoquastic Hamiltonians and Markov matrices · Introduction · 0.82
-
To stochastically compress the density matrix within the QMC framework, despite the sign problem [ref] from both non-stoquastic Hamiltonians [ref] and coherent evolution [ref] , we define a set of complex-signed walkers [ref] , ${w^(α)_t }^N^tot_t_α=1$, where $N^tot_t$ is the total number of walkers at time $t$, as a stochastic representation of $ρ(t)$.
Real-time Sign-Problem-Suppressed Quantum Monte Carlo Algorithm For Noisy Quantum Circuit Simulations · Introduction · 0.81
-
We assume $$ is stoquastic in the computational basis [ref] , which means that in this basis each $H_j,j+1$ is a real symmetric matrix with nonpositive off-diagonal entries, ⟨z | H_j,j+1 |z'⟩≤0 for all z,z'∈{-1,1}^n with z≠z'.
Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians · Introduction · 0.87
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.