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:1503.02269

Local Hamiltonians with Approximation-Robust Entanglement

Lior Eldar

Published Mar 8, 2015• 4 citations
arXivHTMLPDF

Abstract

Quantum entanglement is considered, by and large, to be a very delicate and non-robust phenomenon that is very hard to maintain in the presence of noise, or non-zero temperatures. In recent years however, and motivated, in part, by a quest for a quantum analog of the PCP theorem researches have tried to establish whether or not we can preserve quantum entanglement at "constant" temperatures that are independent of system size. This would imply that any quantum state with energy at most, say 0.05 of the total available energy of the Hamiltonian, would be highly-entangled. To this date, no such systems were found, and moreover, it became evident that even embedding local Hamiltonians on robust, albeit "non-physical" topologies, namely expanders, does not guarantee entanglement robustness. In this study, we indicate that such robustness may be possible after all: We construct an infinite family of O(1)-local Hamiltonians, corresponding to check terms of a quantum error-correcting code with the following property of inapproximability: any quantum state with energy at most 0.05 w.r.t. the total available energy cannot be even approximately simulated by classical circuits of bounded (sub-logarithmic) depth. In a sense, this implies that even providing a "witness" to the fact that the local Hamiltonian can be "almost" satisfied, already requires some measure of long-range entanglement. Our construction is but a first step in what, we believe, is a whole range of possible entanglement - robust local Hamiltonians. A natural next step, we believe, is to devise such local Hamiltonians that resist approximation in terms of bounded-depth quantum circuits (e.g. NLTS), and even find such robust forms of entanglement that are useful for some computation.

DOI
10.48550/arxiv.1503.02269

Related papers

Local Hamiltonians Whose Ground States Are Hard to Approximate

Lior Eldar, Aram W. Harrow

Ground states of local Hamiltonians can be generally highly entangled: any quantum circuit that generates them, even approximately, must be sufficiently deep to allow coupling (entanglement) between any pair of qubits. Until now this property was not known to be “robust” - the marginals of such states to a subset of the qubits containing all but a small constant fraction of them may be only locally entangled, and hence approximable by shallow quantum circuits. In this work we construct a family of 16-local Hamiltonians for which any marginal of a ground state to a fraction at least 1-10-8of the qubits must be globally entangled. This provides evidence that quantum entanglement is not very fragile, and perhaps our intuition about its instability is an artifact of considering local Hamiltonians which are not only local but spatially local. Formally, it provides positive evidence for two wide-open conjectures in condensed-matter physics and quantum complexity theory which are the qLDPC conjecture, positing the existence of “good” quantum LDPC codes, and the NLTS conjecture [1] positing the existence of local Hamiltonians in which any low-energy state is highly entangled. Our Hamiltonian is based on applying the hypergraph product by Tillich-Zemor [2] to the repetition code with checks from an expander graph. A key tool in our proof is a new lower bound on the vertex expansion of the output of low-depth quantum circuits, which may be of independent interest.

arXiv:1510.02082•Annual Symposium on Foundations of Computer Science•Oct 1, 2017•57 citations

Circuit lower bounds for quantum code Hamiltonians and an almost linear NLTS theorem

Anurag Anshu, Chinmay Nirkhe

The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation, 2014) -- which posits the existence of a local Hamiltonian with a super-constant circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this paper, we provide new techniques, based on entropic and local indistinguishability arguments, for proving circuit lower bounds for the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate and polynomial-distance LDPC stabilizer codes, we prove a super-constant circuit lower bounds for the complexity of all states of energy o(n) (which can be viewed as an almost linear NLTS theorem). Such codes are known to exist and, in general, are not locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a constant-dimensional lattice, showing that complex entanglement at high energies can persist in physically relevant systems.

•Nov 3, 2020•0 citations

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1 more

The local Hamiltonian (LH) problem is the canonical $\mathsf{QMA}$-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2^{(1-\varepsilon)n})$ for any $\varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time $O(2^{(1-\varepsilon)n/2})$ for any $\varepsilon>0$ under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$-time quantum circuit acting on $N$ qubits into a $(d+1)$-local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.

quant-pharXiv:2602.14379•Leibniz international proceedings in informatics•Feb 17, 2026•0 citations

Sustained growth of quantum circuit complexity in many-body Hamiltonian dynamics

Wonjun Lee, Saúl Pilatowsky-Cameo, Soonwon Choi

The quantum circuit complexity of an evolving many-body quantum system is believed to exhibit a sustained growth, maintained for timescales much longer than the onset of thermalization. Most previous works have focused on models which violate energy conservation, such as random unitary circuits. Here we study generic, local time-independent Hamiltonian dynamics. We unconditionally prove that for generic local Hamiltonians and typical initial product states at high effective temperature, the robust quantum circuit complexity must grow over a very long period of time, attaining an exponentially large value at late times. Our approach relies on two structural properties that we prove rigorously: (i) generic local Hamiltonians satisfy generalized spectral no-resonance conditions of arbitrary order, and (ii) typical high-temperature product states are effectively supported in exponentially many energy eigenstates. These properties have been widely assumed without proof in prior works. As corollaries of this result, we show the late-time state displays robust volume-law entanglement that is irremovable by polynomial-size circuits, and we establish a no fast-forwarding result for generic local Hamiltonians. We also lower bound the complexity of preparing sufficiently large subsystems with local quantum channels, in contrast with sufficiently small thermalizing regions which we show retain low complexity at late times.

quant-pharXiv:2609.26885•Sep 24, 2026•0 citations

Robust Quantum Entanglement at (Nearly) Room Temperature

Lior Eldar

We formulate a mixed-state analog of the NLTS conjecture [FH14] by asking whether there exist topologically-ordered systems for which the thermal Gibbs state for constant temperature is globally-entangled in the sense that it cannot even be approximated by shallow quantum circuits. We then prove this conjecture holds for nearly optimal parameters: when the "inverse temperature" is almost a constant (temperature decays as 1/loglog(n))) and the Hamiltonian is nearly local (log(n)-local). The construction and proof combine quantum codes that arise from high-dimensional manifolds [Has17, LLZ19], the local-decoding approach to quantum codes [LTZ15, FGL18] and quantum locally-testable codes [AE15].

arXiv:1911.04461•Leibniz international proceedings in informatics•Nov 11, 2019•5 citations

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians

Ranitha Mataraarachchi, François Le Gall, Suguru Tamaki

Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et al. (PRL 2025) recently broke the natural Grover bound $O(2^{n/2})$, where $n$ denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter $d\ge 0$, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-$d$ states (i.e., states obtained by applying a depth-$d$ circuit to the all-zero state), together with an estimate of this energy. For the class of Hamiltonians with depth-$d$ ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions.

quant-pharXiv:2605.18241•May 19, 2026•0 citations
Quantum entanglement is considered, by and large, to be a very delicate and non-robust phenomenon that is very hard to maintain in the presence of noise, or non-zero temperatures. In recent years however, and motivated, in part, by a quest for a quantum analog of the PCP theorem researches have tried to establish whether or not we can preserve quantum entanglement at "constant" temperatures that are independent of system size. This would imply that any quantum state with energy at most, say 0.05 of the total available energy of the Hamiltonian, would be highly-entangled. To this date, no such systems were found, and moreover, it became evident that even embedding local Hamiltonians on robust, albeit "non-physical" topologies, namely expanders, does not guarantee entanglement robustness. In this study, we indicate that such robustness may be possible after all: We construct an infinite family of O(1)-local Hamiltonians, corresponding to check terms of a quantum error-correcting code with the following property of inapproximability: any quantum state with energy at most 0.05 w.r.t. the total available energy cannot be even approximately simulated by classical circuits of bounded (sub-logarithmic) depth. In a sense, this implies that even providing a "witness" to the fact that the local Hamiltonian can be "almost" satisfied, already requires some measure of long-range entanglement. Our construction is but a first step in what, we believe, is a whole range of possible entanglement - robust local Hamiltonians. A natural next step, we believe, is to devise such local Hamiltonians that resist approximation in terms of bounded-depth quantum circuits (e.g. NLTS), and even find such robust forms of entanglement that are useful for some computation.
Ground states of local Hamiltonians can be generally highly entangled: any quantum circuit that generates them, even approximately, must be sufficiently deep to allow coupling (entanglement) between any pair of qubits. Until now this property was not known to be “robust” - the marginals of such states to a subset of the qubits containing all but a small constant fraction of them may be only locally entangled, and hence approximable by shallow quantum circuits. In this work we construct a family of 16-local Hamiltonians for which any marginal of a ground state to a fraction at least 1-10-8of the qubits must be globally entangled. This provides evidence that quantum entanglement is not very fragile, and perhaps our intuition about its instability is an artifact of considering local Hamiltonians which are not only local but spatially local. Formally, it provides positive evidence for two wide-open conjectures in condensed-matter physics and quantum complexity theory which are the qLDPC conjecture, positing the existence of “good” quantum LDPC codes, and the NLTS conjecture [1] positing the existence of local Hamiltonians in which any low-energy state is highly entangled. Our Hamiltonian is based on applying the hypergraph product by Tillich-Zemor [2] to the repetition code with checks from an expander graph. A key tool in our proof is a new lower bound on the vertex expansion of the output of low-depth quantum circuits, which may be of independent interest.
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation, 2014) -- which posits the existence of a local Hamiltonian with a super-constant circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this paper, we provide new techniques, based on entropic and local indistinguishability arguments, for proving circuit lower bounds for the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate and polynomial-distance LDPC stabilizer codes, we prove a super-constant circuit lower bounds for the complexity of all states of energy o(n) (which can be viewed as an almost linear NLTS theorem). Such codes are known to exist and, in general, are not locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a constant-dimensional lattice, showing that complex entanglement at high energies can persist in physically relevant systems.
The local Hamiltonian (LH) problem is the canonical QMA\mathsf{QMA}QMA-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on nnn qubits cannot be solved classically in time O(2(1−ε)n)O(2^{(1-\varepsilon)n})O(2(1−ε)n) for any ε>0\varepsilon>0ε>0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2(1−ε)n/2)O(2^{(1-\varepsilon)n/2})O(2(1−ε)n/2) for any ε>0\varepsilon>0ε>0 under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of QMA\mathsf{QMA}QMA problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in O(2n)O(\sqrt{2^n})O(2n​) time for an arbitrary 1/poly(n)1/\mathrm{poly}(n)1/poly(n) relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a TTT-time quantum circuit acting on NNN qubits into a (d+1)(d+1)(d+1)-local Hamiltonian acting on N+O(T1/d)N+O(T^{1/d})N+O(T1/d) qubits. This improves the standard construction based on the unary clock, which uses N+O(T)N+O(T)N+O(T) qubits.
The quantum circuit complexity of an evolving many-body quantum system is believed to exhibit a sustained growth, maintained for timescales much longer than the onset of thermalization. Most previous works have focused on models which violate energy conservation, such as random unitary circuits. Here we study generic, local time-independent Hamiltonian dynamics. We unconditionally prove that for generic local Hamiltonians and typical initial product states at high effective temperature, the robust quantum circuit complexity must grow over a very long period of time, attaining an exponentially large value at late times. Our approach relies on two structural properties that we prove rigorously: (i) generic local Hamiltonians satisfy generalized spectral no-resonance conditions of arbitrary order, and (ii) typical high-temperature product states are effectively supported in exponentially many energy eigenstates. These properties have been widely assumed without proof in prior works. As corollaries of this result, we show the late-time state displays robust volume-law entanglement that is irremovable by polynomial-size circuits, and we establish a no fast-forwarding result for generic local Hamiltonians. We also lower bound the complexity of preparing sufficiently large subsystems with local quantum channels, in contrast with sufficiently small thermalizing regions which we show retain low complexity at late times.
We formulate a mixed-state analog of the NLTS conjecture [FH14] by asking whether there exist topologically-ordered systems for which the thermal Gibbs state for constant temperature is globally-entangled in the sense that it cannot even be approximated by shallow quantum circuits. We then prove this conjecture holds for nearly optimal parameters: when the "inverse temperature" is almost a constant (temperature decays as 1/loglog(n))) and the Hamiltonian is nearly local (log(n)-local). The construction and proof combine quantum codes that arise from high-dimensional manifolds [Has17, LLZ19], the local-decoding approach to quantum codes [LTZ15, FGL18] and quantum locally-testable codes [AE15].
Low-energy estimation and state preparation for general kkk-local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et al. (PRL 2025) recently broke the natural Grover bound O(2n/2)O(2^{n/2})O(2n/2), where nnn denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter d≥0d\ge 0d≥0, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-ddd states (i.e., states obtained by applying a depth-ddd circuit to the all-zero state), together with an estimate of this energy. For the class of Hamiltonians with depth-ddd ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions.