Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1804.06857

Hamiltonian surgery: Cheeger-type gap inequalities for nonpositive (stoquastic), real, and Hermitian matrices

Michael Jarret

Published Apr 18, 2018• 6 citations
arXivHTMLPDF

Abstract

Cheeger inequalities bound the spectral gap $γ$ of a space by isoperimetric properties of that space and vice versa. In this paper, I derive Cheeger-type inequalities for nonpositive matrices (aka stoquastic Hamiltonians), real matrices, and Hermitian matrices. For matrices written $H = L+W$, where $L$ is either a combinatorial or normalized graph Laplacian, I show that: (1) when $W$ is diagonal and $L$ has maximum degree $d_{\max}$, $2h \geq γ\geq \sqrt{h^2 + d_{\max}^2}-d_\max$; (2) when $W$ is real, we can often route negative-weighted edges along positive-weighted edges such that the Cheeger constant of the resulting graph obeys an inequality similar to that above; and (3) when $W$ is Hermitian, the weighted Cheeger constant obeys $2h \geq γ$ here $h$ is the weighted Cheeger constant of $H$. This constant reduces bounds on $γ$ to information contained in the underlying graph and the Hamiltonian's ground-state. If efficiently computable, the constant opens up a very clear path towards adaptive quantum adiabatic algorithms, those that adjust the adiabatic path based on spectral structure. I sketch a bashful adiabatic algorithm that aborts the adiabatic process early, uses the resulting state to approximate the weighted Cheeger constant, and restarts the process using the updated information. Should this approach work, it would provide more rigorous foundations for adiabatic quantum computing without \textit{a priori} knowledge of the spectral gap.

DOI
10.48550/arxiv.1804.06857

Related papers

Energy gaps of Hamiltonians from graph Laplacians

Abbas Al-Shimary, Jiannis K. Pachos

The Cheeger inequalities give an upper and lower bound on the spectral gap of discrete Laplacians defined on a graph in terms of the geometric characteristics of the graph. We generalise this approach and we employ it to determine if a given discrete Hamiltonian with non-positive elements is gapped or not in the thermodynamic limit. First, we define the graph that corresponds to such a generic Hamiltonian. Then we present a suitable generalisation of the Cheeger inequalities that overcomes scaling deficiencies of the original version. By employing simple examples we illustrate how the generalised Cheeger inequalities can successfully identify gapped or gapless phases and we comment on the computational complexity of this approach.

arXiv:1010.4130•Oct 20, 2010•6 citations

The complexity of stoquastic local Hamiltonian problems

Sergey B. Bravyi, David Peter Divincenzo, Roberto I. Oliveira +1 more

We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys the condition that 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 is in PostBPP.

Quantum Information and Computation•May 1, 2008•79 citations

Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians

Elizabeth Crosson, Bowen, John

We investigate the relationship between the energy spectrum of a local Hamiltonian and the geometric properties of its ground state. By generalizing a standard framework from the analysis of Markov chains to arbitrary (non-stoquastic) Hamiltonians we are naturally led to see that the spectral gap can always be upper bounded by an isoperimetric ratio that depends only on the ground state probability distribution and the range of the terms in the Hamiltonian, but not on any other details of the interaction couplings. This means that for a given probability distribution the inequality constrains the spectral gap of any local Hamiltonian with this distribution as its ground state probability distribution in some basis (Eldar and Harrow derived a similar result in order to characterize the output of low-depth quantum circuits). Going further, we relate the Hilbert space localization properties of the ground state to higher energy eigenvalues by showing that the presence of k strongly localized ground state modes (i.e. clusters of probability, or subsets with small expansion) in Hilbert space implies the presence of k energy eigenvalues that are close to the ground state energy. Our results suggest that quantum adiabatic optimization using local Hamiltonians will inevitably encounter small spectral gaps when attempting to prepare ground states corresponding to multi-modal probability distributions with strongly localized modes, and this problem cannot necessarily be alleviated with the inclusion of non-stoquastic couplings.

arXiv:1703.10133•Mar 29, 2017•10 citations

Complexity of Stoquastic Frustration-Free Hamiltonians

Sergey B. Bravyi, Barbara M. Terhal

We study several problems related to properties of nonnegative 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 nontrivially on a constant number of qubits, (2) every term $H_{a}$ has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term $H_{a}$. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—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 nontrivial example of a MA-complete promise problem.

SIAM Journal on Computing•Nov 20, 2009•124 citations

Complexity of stoquastic frustration-free Hamiltonians

Sergey B. Bravyi, Barbara M. Terhal

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.

arXiv:0806.1746•Jun 10, 2008•3 citations

Efficient quantum algorithm for Heisenberg spin systems

Sergey Bravyi, David Gosset, Yinchen Liu +1 more

We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by $2μ$, where $μ$ is the magnetic field along the $Z$ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.

quant-pharXiv:2607.14401•Jul 17, 2026•0 citations
Cheeger inequalities bound the spectral gap γγγ of a space by isoperimetric properties of that space and vice versa. In this paper, I derive Cheeger-type inequalities for nonpositive matrices (aka stoquastic Hamiltonians), real matrices, and Hermitian matrices. For matrices written H=L+WH = L+WH=L+W, where LLL is either a combinatorial or normalized graph Laplacian, I show that: (1) when WWW is diagonal and LLL has maximum degree dmax⁡d_{\max}dmax​, 2h \geq γ\geq \sqrt{h^2 + d_{\max}^2}-d_\max; (2) when WWW is real, we can often route negative-weighted edges along positive-weighted edges such that the Cheeger constant of the resulting graph obeys an inequality similar to that above; and (3) when WWW is Hermitian, the weighted Cheeger constant obeys 2h≥γ2h \geq γ2h≥γ here hhh is the weighted Cheeger constant of HHH. This constant reduces bounds on γγγ to information contained in the underlying graph and the Hamiltonian's ground-state. If efficiently computable, the constant opens up a very clear path towards adaptive quantum adiabatic algorithms, those that adjust the adiabatic path based on spectral structure. I sketch a bashful adiabatic algorithm that aborts the adiabatic process early, uses the resulting state to approximate the weighted Cheeger constant, and restarts the process using the updated information. Should this approach work, it would provide more rigorous foundations for adiabatic quantum computing without \textit{a priori} knowledge of the spectral gap.
The Cheeger inequalities give an upper and lower bound on the spectral gap of discrete Laplacians defined on a graph in terms of the geometric characteristics of the graph. We generalise this approach and we employ it to determine if a given discrete Hamiltonian with non-positive elements is gapped or not in the thermodynamic limit. First, we define the graph that corresponds to such a generic Hamiltonian. Then we present a suitable generalisation of the Cheeger inequalities that overcomes scaling deficiencies of the original version. By employing simple examples we illustrate how the generalised Cheeger inequalities can successfully identify gapped or gapless phases and we comment on the computational complexity of this approach.
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys the condition that 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 222-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 is in PostBPP.
We investigate the relationship between the energy spectrum of a local Hamiltonian and the geometric properties of its ground state. By generalizing a standard framework from the analysis of Markov chains to arbitrary (non-stoquastic) Hamiltonians we are naturally led to see that the spectral gap can always be upper bounded by an isoperimetric ratio that depends only on the ground state probability distribution and the range of the terms in the Hamiltonian, but not on any other details of the interaction couplings. This means that for a given probability distribution the inequality constrains the spectral gap of any local Hamiltonian with this distribution as its ground state probability distribution in some basis (Eldar and Harrow derived a similar result in order to characterize the output of low-depth quantum circuits). Going further, we relate the Hilbert space localization properties of the ground state to higher energy eigenvalues by showing that the presence of k strongly localized ground state modes (i.e. clusters of probability, or subsets with small expansion) in Hilbert space implies the presence of k energy eigenvalues that are close to the ground state energy. Our results suggest that quantum adiabatic optimization using local Hamiltonians will inevitably encounter small spectral gaps when attempting to prepare ground states corresponding to multi-modal probability distributions with strongly localized modes, and this problem cannot necessarily be alleviated with the inclusion of non-stoquastic couplings.
We study several problems related to properties of nonnegative 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=∑aHaH=\sum_{a}H_{a}H=∑a​Ha​ where (1) every term HaH_{a}Ha​ acts nontrivially on a constant number of qubits, (2) every term HaH_{a}Ha​ has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term HaH_{a}Ha​. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—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 nontrivial example of a MA-complete promise problem.
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=∑aHaH=\sum_a H_aH=∑a​Ha​ where (1) every term HaH_aHa​ acts non-trivially on a constant number of qubits, (2) every term HaH_aHa​ has real non-positive off-diagonal matrix elements in the standard basis, and (3) the ground-state of HHH is a ground-state of every term HaH_aHa​. 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 kkk, 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.
We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by 2μ2μ2μ, where μμμ is the magnetic field along the ZZZ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.