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

Simple proofs for the detectability lemma and its converse

Anurag Anshu, Itai Arad, Thomas Vidick

Published Feb 3, 2016• 0 citations
OpenAlex

Abstract

The detectability lemma is a useful tool for probing the structure of gapped ground states of frustration-free Hamiltonians of lattice spin models. The lemma provides an estimate on the error incurred by approximating the ground space projector with a product of local projectors. We provide a new, simpler proof for the detectability lemma, which applies to an arbitrary ordering of the local projectors, and show that it is tight up to a constant factor. As an application we show how the lemma can be combined with a strong converse by Gao to obtain local spectral gap amplification: we show that by coarse-graining a local frustration-free Hamiltonian with a spectral gap $\gamma>0$ to a length scale $O(\gamma^{-1/2})$, one gets an Hamiltonian with an $\Omega(1)$ spectral gap.

Related papers

Simple proof of the detectability lemma and spectral gap amplification

Anurag Anshu, Itai Arad, Thomas Vidick

The detectability lemma is a useful tool for probing the structure of gapped ground states of frustration-free Hamiltonians of lattice spin models. The lemma provides an estimate on the error incurred by approximating the ground space projector with a product of local projectors. We provide a simpler proof for the detectability lemma which applies to an arbitrary ordering of the local projectors, and show that it is tight up to a constant factor. As an application, we show how the lemma can be combined with a strong converse by Gao to obtain local spectral gap amplification: We show that by coarse graining a local frustration-free Hamiltonian with a spectral gap $\ensuremath{\gamma}>0$ to a length scale $O\left({\ensuremath{\gamma}}^{\ensuremath{-}1/2}\right)$, one gets a Hamiltonian with an $\mathrm{\ensuremath{\Omega}}\left(1\right)$ spectral gap.

arXiv:1602.01210•Physical review. B./Physical review. B•May 23, 2016•32 citations

Improved local spectral gap thresholds for lattices of finite size

Anurag Anshu

Knabe's theorem lower bounds the spectral gap of a one-dimensional frustration-free local Hamiltonian in terms of the local spectral gaps of finite regions. It also provides a local spectral gap threshold for Hamiltonians that are gapless in the thermodynamic limit, showing that the local spectral gap must scale inverse linearly with the length of the region for such systems. Recent works have further improved upon this threshold, tightening it in the one-dimensional case and extending it to higher dimensions. Here, we show a local spectral gap threshold for frustration-free Hamiltonians on a finite-dimensional lattice that is optimal up to a constant factor that depends on the dimension of the lattice. Our proof is based on the detectability lemma framework and uses the notion of a coarse-grained Hamiltonian (introduced in [Anshu et al., Phys. Rev. B 93, 205142]) as a link connecting the (global) spectral gap and the local spectral gap.

arXiv:1909.01516•Physical review. B./Physical review. B•Apr 6, 2020•18 citations

Quantum Gibbs sampling through the detectability lemma

Di Fang, Jianfeng Lu, Yu Tong +1 more

Gibbs state preparation is an important subroutine in quantum computing. In this work we use the detectability lemma to improve Gibbs state preparation. Specifically, we design new Gibbs state preparation methods that do not rely on simulating Lindbladian evolution, thus avoiding the overhead from it. For local Lindbladians consisting of $M$ terms, this approach reduces the cost by a factor of $O(M)$. We also combine the detectability lemma operator and quantum singular value transformation to implement ground state projection operators of frustration-free Hamiltonians, resulting in a quadratic speedup in the spectral gap dependence. Applying this method to Lindbladians for the Gibbs state of local commuting Hamiltonians, we achieve quadratically better dependence on the Lindbladian spectral gap.

quant-pharXiv:2604.07214•Apr 9, 2026•0 citations

The detectability lemma and quantum gap amplification

Dorit Aharonov, Itai Arad, Zeph A. Landau +1 more

The quantum analogue of a constraint satisfaction problem is a sum of local Hamiltonians - each local Hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. Formalizing the intuitive connection between the ground (minimal) energy of the Hamiltonian and the minimum number of violated constraints is problematic, since the number of constraints being violated is not well defined when the terms in the Hamiltonian do not commute. The detectability lemma proved in this paper provides precisely such a quantitative connection. We apply the lemma to derive a quantum analogue of a basic primitive in classical complexity: amplification of probabilities by random walks on expander graphs. It holds under the restriction that the interaction graph of the local Hamiltonian is an expander. Our proofs are based on a novel structure imposed on the Hilbert space that we call the $XY$ decomposition, which enables a reduction from the quantum non-commuting case to the commuting case (where many classical arguments go through). The results may have several interesting implications. First, proving a quantum analogue to the PCP theorem is one of the most important challenges in quantum complexity theory. Our quantum gap amplification lemma may be viewed as the quantum analogue of the first of the three main steps in Dinur's PCP proof. Quantum gap amplification may also be related to spectral gap amplification, and in particular, to fault tolerance of adiabatic computation. Finally, the detectability lemma, and the $XY$ decomposition provide a handle on the structure of local Hamiltonians and their ground states.

arXiv:0811.3412•ACM Symposium on Theory of Computing (STOC)•May 31, 2009•79 citations

Divide and conquer method for proving gaps of frustration free Hamiltonians

Michael J Kastoryano, Angelo Lucia

Abstract Providing system-size independent lower bounds on the spectral gap of local Hamiltonian is in general a hard problem. For the case of finite-range, frustration free Hamiltonians on a spin lattice of arbitrary dimension, we show that a property of the ground state space is sufficient to obtain such a bound. We furthermore show that such a condition is necessary and equivalent to a constant spectral gap. Thanks to this equivalence, we can prove that for gapless models in any dimension, the spectral gap on regions of diameter n is at most o ( log ⁡ ( n ) 2 + ε n ) for any positive ϵ.

arXiv:1705.09491•Journal of Statistical Mechanics Theory and Experiment•Mar 1, 2018•18 citations

The detectability lemma and its applications to quantum Hamiltonian complexity

Dorit Aharonov, Itai Arad, Umesh V. Vazirani +1 more

Quantum Hamiltonian complexity, an emerging area at the intersection of condensed matter physics and quantum complexity theory, studies the properties of local Hamiltonians and their ground states. In this paper we focus on a seemingly specialized technical tool, the detectability lemma (DL), introduced in the context of the quantum PCP challenge (Aharonov et al 2009 arXiv:0811.3412), which is a major open question in quantum Hamiltonian complexity. We show that a reformulated version of the lemma is a versatile tool that can be used in place of the celebrated Lieb-Robinson (LR) bound to prove several important results in quantum Hamiltonian complexity. The resulting proofs are much simpler, more combinatorial and provide a plausible path toward tackling some fundamental open questions in Hamiltonian complexity. We provide an alternative simpler proof of the DL that removes a key restriction in the original statement (Aharonov et al 2009 arXiv:0811.3412), making it more suitable for the broader context of quantum Hamiltonian complexity. Specifically, we first use the DL to provide a one-page proof of Hastings' result that the correlations in the ground states of gapped Hamiltonians decay exponentially with distance (Hastings 2004 Phys. Rev. B 69 104431). We then apply the DL to derive a simpler and more intuitive proof of Hastings' seminal one-dimensional (1D) area law (Hastings 2007 J. Stat. Mech. (2007) P8024) (both these proofs are restricted to frustration-free systems). Proving the area law for two and higher dimensions is one of the most important open questions in the field of Hamiltonian complexity, and the combinatorial nature of the

New Journal of Physics•Nov 30, 2011•29 citations
The detectability lemma is a useful tool for probing the structure of gapped ground states of frustration-free Hamiltonians of lattice spin models. The lemma provides an estimate on the error incurred by approximating the ground space projector with a product of local projectors. We provide a new, simpler proof for the detectability lemma, which applies to an arbitrary ordering of the local projectors, and show that it is tight up to a constant factor. As an application we show how the lemma can be combined with a strong converse by Gao to obtain local spectral gap amplification: we show that by coarse-graining a local frustration-free Hamiltonian with a spectral gap γ>0\gamma>0γ>0 to a length scale O(γ−1/2)O(\gamma^{-1/2})O(γ−1/2), one gets an Hamiltonian with an Ω(1)\Omega(1)Ω(1) spectral gap.
The detectability lemma is a useful tool for probing the structure of gapped ground states of frustration-free Hamiltonians of lattice spin models. The lemma provides an estimate on the error incurred by approximating the ground space projector with a product of local projectors. We provide a simpler proof for the detectability lemma which applies to an arbitrary ordering of the local projectors, and show that it is tight up to a constant factor. As an application, we show how the lemma can be combined with a strong converse by Gao to obtain local spectral gap amplification: We show that by coarse graining a local frustration-free Hamiltonian with a spectral gap $\ensuremath{\gamma}>0$ to a length scale $O\left({\ensuremath{\gamma}}^{\ensuremath{-}1/2}\right)$, one gets a Hamiltonian with an $\mathrm{\ensuremath{\Omega}}\left(1\right)$ spectral gap.
Knabe's theorem lower bounds the spectral gap of a one-dimensional frustration-free local Hamiltonian in terms of the local spectral gaps of finite regions. It also provides a local spectral gap threshold for Hamiltonians that are gapless in the thermodynamic limit, showing that the local spectral gap must scale inverse linearly with the length of the region for such systems. Recent works have further improved upon this threshold, tightening it in the one-dimensional case and extending it to higher dimensions. Here, we show a local spectral gap threshold for frustration-free Hamiltonians on a finite-dimensional lattice that is optimal up to a constant factor that depends on the dimension of the lattice. Our proof is based on the detectability lemma framework and uses the notion of a coarse-grained Hamiltonian (introduced in [Anshu et al., Phys. Rev. B 93, 205142]) as a link connecting the (global) spectral gap and the local spectral gap.
Gibbs state preparation is an important subroutine in quantum computing. In this work we use the detectability lemma to improve Gibbs state preparation. Specifically, we design new Gibbs state preparation methods that do not rely on simulating Lindbladian evolution, thus avoiding the overhead from it. For local Lindbladians consisting of MMM terms, this approach reduces the cost by a factor of O(M)O(M)O(M). We also combine the detectability lemma operator and quantum singular value transformation to implement ground state projection operators of frustration-free Hamiltonians, resulting in a quadratic speedup in the spectral gap dependence. Applying this method to Lindbladians for the Gibbs state of local commuting Hamiltonians, we achieve quadratically better dependence on the Lindbladian spectral gap.
The quantum analogue of a constraint satisfaction problem is a sum of local Hamiltonians - each local Hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. Formalizing the intuitive connection between the ground (minimal) energy of the Hamiltonian and the minimum number of violated constraints is problematic, since the number of constraints being violated is not well defined when the terms in the Hamiltonian do not commute. The detectability lemma proved in this paper provides precisely such a quantitative connection. We apply the lemma to derive a quantum analogue of a basic primitive in classical complexity: amplification of probabilities by random walks on expander graphs. It holds under the restriction that the interaction graph of the local Hamiltonian is an expander. Our proofs are based on a novel structure imposed on the Hilbert space that we call the XYXYXY decomposition, which enables a reduction from the quantum non-commuting case to the commuting case (where many classical arguments go through). The results may have several interesting implications. First, proving a quantum analogue to the PCP theorem is one of the most important challenges in quantum complexity theory. Our quantum gap amplification lemma may be viewed as the quantum analogue of the first of the three main steps in Dinur's PCP proof. Quantum gap amplification may also be related to spectral gap amplification, and in particular, to fault tolerance of adiabatic computation. Finally, the detectability lemma, and the XYXYXY decomposition provide a handle on the structure of local Hamiltonians and their ground states.
Abstract Providing system-size independent lower bounds on the spectral gap of local Hamiltonian is in general a hard problem. For the case of finite-range, frustration free Hamiltonians on a spin lattice of arbitrary dimension, we show that a property of the ground state space is sufficient to obtain such a bound. We furthermore show that such a condition is necessary and equivalent to a constant spectral gap. Thanks to this equivalence, we can prove that for gapless models in any dimension, the spectral gap on regions of diameter n is at most o ( log ⁡ ( n ) 2 + ε n ) for any positive ϵ.
Quantum Hamiltonian complexity, an emerging area at the intersection of condensed matter physics and quantum complexity theory, studies the properties of local Hamiltonians and their ground states. In this paper we focus on a seemingly specialized technical tool, the detectability lemma (DL), introduced in the context of the quantum PCP challenge (Aharonov et al 2009 arXiv:0811.3412), which is a major open question in quantum Hamiltonian complexity. We show that a reformulated version of the lemma is a versatile tool that can be used in place of the celebrated Lieb-Robinson (LR) bound to prove several important results in quantum Hamiltonian complexity. The resulting proofs are much simpler, more combinatorial and provide a plausible path toward tackling some fundamental open questions in Hamiltonian complexity. We provide an alternative simpler proof of the DL that removes a key restriction in the original statement (Aharonov et al 2009 arXiv:0811.3412), making it more suitable for the broader context of quantum Hamiltonian complexity. Specifically, we first use the DL to provide a one-page proof of Hastings' result that the correlations in the ground states of gapped Hamiltonians decay exponentially with distance (Hastings 2004 Phys. Rev. B 69 104431). We then apply the DL to derive a simpler and more intuitive proof of Hastings' seminal one-dimensional (1D) area law (Hastings 2007 J. Stat. Mech. (2007) P8024) (both these proofs are restricted to frustration-free systems). Proving the area law for two and higher dimensions is one of the most important open questions in the field of Hamiltonian complexity, and the combinatorial nature of the