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:0811.3412 · ACM Symposium on Theory of Computing (STOC)

The detectability lemma and quantum gap amplification

Dorit Aharonov, Itai Arad, Zeph A. Landau, Umesh V. Vazirani

Published May 31, 2009• 79 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1145/1536414.1536472

Related papers

Gap Amplification for Local Hamiltonians with Combinatorial Soundness

Mitali Bafna, Quynh T. Nguyen, Tina Zhang

The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of many known strategies for proving the classical PCP theorem. In this work, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies the combinatorial gap of local Hamiltonians. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central ingredients in classical PCPs into the quantum setting. In particular, we build upon ideas from the recent classical PCP of Bafna--Minzer--Vyas based on high-dimensional expanders, and the circuit-to-Hamiltonian construction of Anshu--Breuckmann--Nguyen, in addition to several recent advances in quantum coding theory.

quant-pharXiv:2610.04952•Oct 6, 2026•0 citations

Quantum Hamiltonian complexity and the detectability lemma

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

Quantum Hamiltonian complexity studies computational complexity aspects of local Hamiltonians and ground states; these questions can be viewed as generalizations of classical computational complexity problems related to local constraint satisfaction (such as SAT), with the additional ingredient of multi-particle entanglement. This additional ingredient of course makes generalizations of celebrated theorems such as the PCP theorem from classical to the quantum domain highly non-trivial; it also raises entirely new questions such as bounds on entanglement and correlations in ground states, and in particular area laws. We propose a simple combinatorial tool that helps to handle such questions: it is a simplified, yet more general version of the detectability lemma introduced by us in the more restricted context on quantum gap amplification a year ago. Here, we argue that this lemma is applicable in much more general contexts. We use it to provide a simplified and more combinatorial proof of Hastings' 1D area law, together with a less than 1 page proof of the decay of correlations in gapped local Hamiltonian systems in any constant dimension. We explain how the detectability lemma can replace the Lieb-Robinson bound in various other contexts, and argue that it constitutes a basic tool for the study of local Hamiltonians and their ground states in relation to various questions in quantum Hamiltonian complexity.

arXiv:1011.3445•Nov 15, 2010•9 citations

The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach

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

The classical description of quantum states is in general exponential in the number of qubits. Can we get polynomial descriptions for more restricted sets of states such as ground states of interesting subclasses of local Hamiltonians? This is the basic problem in the study of the complexity of ground states, and requires an understanding of multi-particle entanglement and quantum correlations in such states. Area laws provide a fundamental ingredient in the study of the complexity of ground states, since they offer a way to bound in a quantitative way the entanglement in such states. Although they have long been conjectured for many body systems in arbitrary dimensions, a general rigorous was only recently proved in Hastings' seminal paper [8] for ID systems. In this paper, we give a combinatorial proof of the ID area law for the special case of frustration free systems, improving by an exponential factor the scaling in terms of the inverse spectral gap and the dimensionality of the particles. The scaling in terms of the dimension of the particles is a potentially important issue in the context of resolving the 2D case and higher dimensions, which is one of the most important open questions in Hamiltonian complexity. Our proof is based on a reformulation of the detectability lemma, introduced by us in the context of quantum gap amplification [1]. We give an alternative proof of the detectability lemma, which is not only simpler and more intuitive than the original proof, but also removes a key restriction in the original statement, making it more suitable for this new context. We also give a one page proof of Hastings' proof that the correlations in the ground states of gapped Hamiltonians decay exponentially with the distance, demonstrating the simplicity of the combinatorial approach for those problems.

Annual Symposium on Foundations of Computer Science•Oct 1, 2011•36 citations

Derandomised Tensor Product Gap Amplification for Quantum Hamiltonians

Thiago Bergamaschi, Tony Metger, Thomas Vidick +1 more

The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low-energy Hamiltonians even when the gap between "high" and "low" energy is large (constant). A natural proof strategy is gap amplification: start from the fact that high- and low-energy Hamiltonians are hard to distinguish if the gap is small (inverse polynomial) [Alexei Y. Kitaev et al., 2002] and amplify the Hamiltonians to increase the energy gap while preserving hardness. Such a gap amplification procedure is at the heart of Dinur’s proof of the classical PCP theorem [Dinur, 2007]. In this work, following Dinur’s model, we introduce a new quantum gap amplification procedure for Hamiltonians which uses random walks on expander graphs to derandomise (subsample the terms of) the tensor product amplification of a Hamiltonian. Curiously, our analysis relies on a new technique inspired by quantum de Finetti theorems, which have previously been used to rule out certain approaches to the quantum PCP conjecture [Fernando G. S. L. Brandão and Aram Wettroth Harrow, 2013].

arXiv:2510.01333•Leibniz international proceedings in informatics•Oct 1, 2025•0 citations

The Complexity of Quantum Fault Tolerance

Quynh The Nguyen

The theory of fault tolerance is a cornerstone of computing and many modern technologies. With the development of quantum science and engineering, fault tolerance has become increasingly important, as quantum systems are intrinsically susceptible to noise. This thesis presents several advances in quantum fault tolerance and develops new connections between fault tolerance and quantum complexity theory. In Part I, we construct a fault-tolerant quantum computation scheme with constant space overhead and near-logarithmic time overhead. This is the lowest overhead achieved to date and and provides the first rigorous proof that fault tolerance based on quantum low-density parity-check (qLDPC) codes can achieve better asymptotic spacetime overhead than conventional schemes. The construction relies on locally testable qLDPC codes and new quantum state distillation algorithms with improved spacetime overhead. Additionally, a variant of these algorithms yields the first magic state distillation algorithm with constant space overhead. In Part II, we make progress on the quantum probabilistically checkable proofs (PCP) conjecture by using ideas from fault tolerance. We introduce a new circuit-to-Hamiltonian mapping that allows Hamiltonians to inherit the fault tolerance properties of quantum circuits. Using this new mapping, we construct the first known template for quantum locality-preserving gap amplification---the quantum analogue of a central ingredient in the classical PCP theorem---and prove that it amplifies the combinatorial gap. The construction develops a new framework for reasoning about gap amplification in terms of fault-tolerant distributed computation, along with new tools in secure multiparty computation and high-dimensional expanders.

•Jan 1, 2026•0 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 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.
The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of many known strategies for proving the classical PCP theorem. In this work, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies the combinatorial gap of local Hamiltonians. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central ingredients in classical PCPs into the quantum setting. In particular, we build upon ideas from the recent classical PCP of Bafna--Minzer--Vyas based on high-dimensional expanders, and the circuit-to-Hamiltonian construction of Anshu--Breuckmann--Nguyen, in addition to several recent advances in quantum coding theory.
Quantum Hamiltonian complexity studies computational complexity aspects of local Hamiltonians and ground states; these questions can be viewed as generalizations of classical computational complexity problems related to local constraint satisfaction (such as SAT), with the additional ingredient of multi-particle entanglement. This additional ingredient of course makes generalizations of celebrated theorems such as the PCP theorem from classical to the quantum domain highly non-trivial; it also raises entirely new questions such as bounds on entanglement and correlations in ground states, and in particular area laws. We propose a simple combinatorial tool that helps to handle such questions: it is a simplified, yet more general version of the detectability lemma introduced by us in the more restricted context on quantum gap amplification a year ago. Here, we argue that this lemma is applicable in much more general contexts. We use it to provide a simplified and more combinatorial proof of Hastings' 1D area law, together with a less than 1 page proof of the decay of correlations in gapped local Hamiltonian systems in any constant dimension. We explain how the detectability lemma can replace the Lieb-Robinson bound in various other contexts, and argue that it constitutes a basic tool for the study of local Hamiltonians and their ground states in relation to various questions in quantum Hamiltonian complexity.
The classical description of quantum states is in general exponential in the number of qubits. Can we get polynomial descriptions for more restricted sets of states such as ground states of interesting subclasses of local Hamiltonians? This is the basic problem in the study of the complexity of ground states, and requires an understanding of multi-particle entanglement and quantum correlations in such states. Area laws provide a fundamental ingredient in the study of the complexity of ground states, since they offer a way to bound in a quantitative way the entanglement in such states. Although they have long been conjectured for many body systems in arbitrary dimensions, a general rigorous was only recently proved in Hastings' seminal paper [8] for ID systems. In this paper, we give a combinatorial proof of the ID area law for the special case of frustration free systems, improving by an exponential factor the scaling in terms of the inverse spectral gap and the dimensionality of the particles. The scaling in terms of the dimension of the particles is a potentially important issue in the context of resolving the 2D case and higher dimensions, which is one of the most important open questions in Hamiltonian complexity. Our proof is based on a reformulation of the detectability lemma, introduced by us in the context of quantum gap amplification [1]. We give an alternative proof of the detectability lemma, which is not only simpler and more intuitive than the original proof, but also removes a key restriction in the original statement, making it more suitable for this new context. We also give a one page proof of Hastings' proof that the correlations in the ground states of gapped Hamiltonians decay exponentially with the distance, demonstrating the simplicity of the combinatorial approach for those problems.
The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low-energy Hamiltonians even when the gap between "high" and "low" energy is large (constant). A natural proof strategy is gap amplification: start from the fact that high- and low-energy Hamiltonians are hard to distinguish if the gap is small (inverse polynomial) [Alexei Y. Kitaev et al., 2002] and amplify the Hamiltonians to increase the energy gap while preserving hardness. Such a gap amplification procedure is at the heart of Dinur’s proof of the classical PCP theorem [Dinur, 2007]. In this work, following Dinur’s model, we introduce a new quantum gap amplification procedure for Hamiltonians which uses random walks on expander graphs to derandomise (subsample the terms of) the tensor product amplification of a Hamiltonian. Curiously, our analysis relies on a new technique inspired by quantum de Finetti theorems, which have previously been used to rule out certain approaches to the quantum PCP conjecture [Fernando G. S. L. Brandão and Aram Wettroth Harrow, 2013].
The theory of fault tolerance is a cornerstone of computing and many modern technologies. With the development of quantum science and engineering, fault tolerance has become increasingly important, as quantum systems are intrinsically susceptible to noise. This thesis presents several advances in quantum fault tolerance and develops new connections between fault tolerance and quantum complexity theory. In Part I, we construct a fault-tolerant quantum computation scheme with constant space overhead and near-logarithmic time overhead. This is the lowest overhead achieved to date and and provides the first rigorous proof that fault tolerance based on quantum low-density parity-check (qLDPC) codes can achieve better asymptotic spacetime overhead than conventional schemes. The construction relies on locally testable qLDPC codes and new quantum state distillation algorithms with improved spacetime overhead. Additionally, a variant of these algorithms yields the first magic state distillation algorithm with constant space overhead. In Part II, we make progress on the quantum probabilistically checkable proofs (PCP) conjecture by using ideas from fault tolerance. We introduce a new circuit-to-Hamiltonian mapping that allows Hamiltonians to inherit the fault tolerance properties of quantum circuits. Using this new mapping, we construct the first known template for quantum locality-preserving gap amplification---the quantum analogue of a central ingredient in the classical PCP theorem---and prove that it amplifies the combinatorial gap. The construction develops a new framework for reasoning about gap amplification in terms of fault-tolerant distributed computation, along with new tools in secure multiparty computation and high-dimensional expanders.
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