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

Sub-exponential algorithm for 2D frustration-free spin systems with gapped subsystems

Nilin Abrahamsen

Published Apr 6, 2020• 1 citation
OpenAlex

Abstract

We show that in the setting of the subvolume law of [Anshu, Arad, Gosset '19] for 2D locally gapped frustration-free spin systems there exists a randomized classical algorithm which computes the ground states in sub-exponential time. The running time cannot be improved to polynomial unless SAT can be solved in randomized polynomial time, as even the special case of classical constraint satisfaction problems on the 2D grid is known to be NP-hard.

Related papers

Solving degenerate 2D frustration-free spin systems in sub-exponential time

Nilin Abrahamsen

We give an improved analysis of approximate ground space projectors (AGSPs) to obtain a sharp error reduction bound in the setting a degenerate ground space. The improved tools imply that the recently proven 2D area law directly extends to sub-exponentially degenerate ground spaces and also yields a sub-exponential-time classical algorithm to compute the ground states. This time complexity cannot be improved beyond sub-exponential, even for the special case of classical unfrustrated systems in 2D.

arXiv:2004.02850•Apr 6, 2020•0 citations

On Efficiently Solvable Cases of Quantum k-SAT

Marco Aldi, Niel de Beaudrap, Sevag Gharibian +1 more

Abstract Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is $$\hbox {QMA}_1$$ QMA 1 -complete (for $$k\ge 3$$ k ≥ 3 , and where $$\hbox {QMA}_1$$ QMA 1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But whereas k-SAT has been well-studied for special tractable cases, as well as from a “parameterized complexity” perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state. Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or clauses. (2) We give a “parameterized algorithm” for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry.

arXiv:1712.09617•Communications in Mathematical Physics•Dec 24, 2020•5 citations

An area law and sub-exponential algorithm for 1D systems

Arad, Itai, Kitaev, Alexei, Landau, Zeph +1 more

We give a new proof for the area law for general 1D gapped systems, which exponentially improves Hastings' famous result \cite{ref:Has07}. Specifically, we show that for a chain of d-dimensional spins, governed by a 1D local Hamiltonian with a spectral gap \eps>0, the entanglement entropy of the ground state with respect to any cut in the chain is upper bounded by $O{\frac{\log^3 d}{\eps}}$. Our approach uses the framework Arad et al to construct a Chebyshev-based AGSP (Approximate Ground Space Projection) with favorable factors. However, our construction uses the Hamiltonian directly, instead of using the Detectability lemma, which allows us to work with general (frustrated) Hamiltonians, as well as slightly improving the $1/\eps$ dependence of the bound in Arad et al. To achieve that, we establish a new, "random-walk like", bound on the entanglement rank of an arbitrary power of a 1D Hamiltonian, which might be of independent interest: \ER{H^\ell} \le (\ell d)^{O(\sqrt{\ell})}. Finally, treating d as a constant, our AGSP shows that the ground state is well approximated by a matrix product state with a sublinear bond dimension $B=e^{O(\log^{3/4}n/\eps^{1/4})}. Using this in conjunction with known dynamical programing algorithms, yields an algorithm for a 1/\poly(n) approximation of the ground energy with a subexponential running time T\le \exp(e^{O(\log^{3/4}n/\eps^{1/4})}).

arXiv:1301.1162•Jan 7, 2013•88 citations

On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma

András Gilyén, Or Sattath

A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously. In general, even deciding whether a Hamiltonian is frustration-free is a hard task, as it is closely related to the QMA1-complete quantum satisfiability problem (QSAT) - the quantum analogue of SAT, which is the archetypal NP-complete problem in classical computer science. This connection shows that the frustration-free property is not only relevant to physics but also to computer science. The Quantum Lovasz Local Lemma (QLLL) provides a sufficient condition for frustration-freeness. Is there an efficient way to prepare a frustration-free state under the conditions of the QLLL? Previous results showed that the answer is positive if all local terms commute. These works were based on Moser's “compression argument” which was the original analysis technique of the celebrated resampling algorithm. We generalise and simplify the “compression argument”, so that it provides a simplified version of the previous quantum results, and improves on some classical results as well. More importantly, we improve on the previous constructive results by designing an algorithm that works efficiently for non-commuting terms as well, assuming that the system is “uniformly” gapped, by which we mean that the system and all its subsystems have an inverse polynomial energy gap. Similarly to the previous results, our algorithm has the charming feature that it uses only local measurement operations corresponding to the local Hamiltonian terms.

arXiv:1611.08571•Annual Symposium on Foundations of Computer Science•Oct 1, 2017•12 citations

Entanglement subvolume law for 2d frustration-free spin systems

Anurag Anshu, Itai Arad, David Gosset

Let H be a frustration-free Hamiltonian describing a 2D grid of qudits with local interactions, a unique ground state, and local spectral gap lower bounded by a positive constant. For any bipartition defined by a vertical cut of length L running from top to bottom of the grid, we prove that the corresponding entanglement entropy of the ground state of H is upper bounded by Õ(L 5/3). For the special case of a 1D chain, our result provides a new area law which improves upon prior work, in terms of the scaling with qudit dimension and spectral gap. In addition, for any bipartition of the grid into a rectangular region A and its complement, we show that the entanglement entropy is upper bounded as Õ(|∂ A|5/3) where ∂ A is the boundary of A. This represents a subvolume bound on entanglement in frustration-free 2D systems. In contrast with previous work, our bounds depend on the local (rather than global) spectral gap of the Hamiltonian. We prove our results using a known method which bounds the entanglement entropy of the ground state in terms of certain properties of an approximate ground state projector (AGSP). To this end, we construct a new AGSP which is based on a robust polynomial approximation of the AND function and we show that it achieves an improved trade-off between approximation error and entanglement.

ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•14 citations

Random translation-invariant Hamiltonians and their spectral gaps

Ian Jauslin, Marius Lemm

We consider random translation-invariant frustration-free quantum spin Hamiltonians on ZD in which the nearest-neighbor interaction in every direction is randomly sampled and then distributed across the lattice. Our main result is that, under a small rank constraint, the Hamiltonians are automatically frustration-free and they are gapped with a positive probability. This extends previous results on 1D spin chains to all dimensions. The argument additionally controls the local gap. As an application, we obtain a 2D area law for a cut-dependent ground state via recent AGSP methods of Anshu-Arad-Gosset.

arXiv:2111.06433•Quantum•Sep 1, 2022•7 citations
We show that in the setting of the subvolume law of [Anshu, Arad, Gosset '19] for 2D locally gapped frustration-free spin systems there exists a randomized classical algorithm which computes the ground states in sub-exponential time. The running time cannot be improved to polynomial unless SAT can be solved in randomized polynomial time, as even the special case of classical constraint satisfaction problems on the 2D grid is known to be NP-hard.
We give an improved analysis of approximate ground space projectors (AGSPs) to obtain a sharp error reduction bound in the setting a degenerate ground space. The improved tools imply that the recently proven 2D area law directly extends to sub-exponentially degenerate ground spaces and also yields a sub-exponential-time classical algorithm to compute the ground states. This time complexity cannot be improved beyond sub-exponential, even for the special case of classical unfrustrated systems in 2D.
Abstract Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is QMA1\hbox {QMA}_1QMA1​ QMA 1 -complete (for k≥3k\ge 3k≥3 k ≥ 3 , and where QMA1\hbox {QMA}_1QMA1​ QMA 1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But whereas k-SAT has been well-studied for special tractable cases, as well as from a “parameterized complexity” perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state. Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or clauses. (2) We give a “parameterized algorithm” for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry.
We give a new proof for the area law for general 1D gapped systems, which exponentially improves Hastings' famous result \cite{ref:Has07}. Specifically, we show that for a chain of d-dimensional spins, governed by a 1D local Hamiltonian with a spectral gap \eps>0, the entanglement entropy of the ground state with respect to any cut in the chain is upper bounded by $O{\frac{\log^3 d}{\eps}}$. Our approach uses the framework Arad et al to construct a Chebyshev-based AGSP (Approximate Ground Space Projection) with favorable factors. However, our construction uses the Hamiltonian directly, instead of using the Detectability lemma, which allows us to work with general (frustrated) Hamiltonians, as well as slightly improving the $1/\eps$ dependence of the bound in Arad et al. To achieve that, we establish a new, "random-walk like", bound on the entanglement rank of an arbitrary power of a 1D Hamiltonian, which might be of independent interest: \ER{H^\ell} \le (\ell d)^{O(\sqrt{\ell})}. Finally, treating d as a constant, our AGSP shows that the ground state is well approximated by a matrix product state with a sublinear bond dimension $B=e^{O(\log^{3/4}n/\eps^{1/4})}. Using this in conjunction with known dynamical programing algorithms, yields an algorithm for a 1/\poly(n) approximation of the ground energy with a subexponential running time T\le \exp(e^{O(\log^{3/4}n/\eps^{1/4})}).
A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously. In general, even deciding whether a Hamiltonian is frustration-free is a hard task, as it is closely related to the QMA1-complete quantum satisfiability problem (QSAT) - the quantum analogue of SAT, which is the archetypal NP-complete problem in classical computer science. This connection shows that the frustration-free property is not only relevant to physics but also to computer science. The Quantum Lovasz Local Lemma (QLLL) provides a sufficient condition for frustration-freeness. Is there an efficient way to prepare a frustration-free state under the conditions of the QLLL? Previous results showed that the answer is positive if all local terms commute. These works were based on Moser's “compression argument” which was the original analysis technique of the celebrated resampling algorithm. We generalise and simplify the “compression argument”, so that it provides a simplified version of the previous quantum results, and improves on some classical results as well. More importantly, we improve on the previous constructive results by designing an algorithm that works efficiently for non-commuting terms as well, assuming that the system is “uniformly” gapped, by which we mean that the system and all its subsystems have an inverse polynomial energy gap. Similarly to the previous results, our algorithm has the charming feature that it uses only local measurement operations corresponding to the local Hamiltonian terms.
Let H be a frustration-free Hamiltonian describing a 2D grid of qudits with local interactions, a unique ground state, and local spectral gap lower bounded by a positive constant. For any bipartition defined by a vertical cut of length L running from top to bottom of the grid, we prove that the corresponding entanglement entropy of the ground state of H is upper bounded by Õ(L 5/3). For the special case of a 1D chain, our result provides a new area law which improves upon prior work, in terms of the scaling with qudit dimension and spectral gap. In addition, for any bipartition of the grid into a rectangular region A and its complement, we show that the entanglement entropy is upper bounded as Õ(|∂ A|5/3) where ∂ A is the boundary of A. This represents a subvolume bound on entanglement in frustration-free 2D systems. In contrast with previous work, our bounds depend on the local (rather than global) spectral gap of the Hamiltonian. We prove our results using a known method which bounds the entanglement entropy of the ground state in terms of certain properties of an approximate ground state projector (AGSP). To this end, we construct a new AGSP which is based on a robust polynomial approximation of the AND function and we show that it achieves an improved trade-off between approximation error and entanglement.
We consider random translation-invariant frustration-free quantum spin Hamiltonians on ZD in which the nearest-neighbor interaction in every direction is randomly sampled and then distributed across the lattice. Our main result is that, under a small rank constraint, the Hamiltonians are automatically frustration-free and they are gapped with a positive probability. This extends previous results on 1D spin chains to all dimensions. The argument additionally controls the local gap. As an application, we obtain a 2D area law for a cut-dependent ground state via recent AGSP methods of Anshu-Arad-Gosset.