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:1112.0762 · Journal of Mathematical Physics

Ground-state spaces of frustration-free Hamiltonians

Jianxin Chen, Zhengfeng Ji, David W. Kribs, Zhaohui Wei, Bei Zeng

Published Sep 18, 2012• 16 citations
arXivHTMLPDF

Abstract

We study the ground-state space properties for frustration-free Hamiltonians. We introduce a concept of “reduced spaces” to characterize local structures of ground-state spaces. For a many-body system, we characterize mathematical structures for the set Θk of all the k-particle reduced spaces, which with a binary operation called join forms a semilattice that can be interpreted as an abstract convex structure. The smallest nonzero elements in Θk, called atoms, are analogs of extreme points. We study the properties of atoms in Θk and discuss its relationship with ground states of k-local frustration-free Hamiltonians. For spin-1/2 systems, we show that all the atoms in Θ2 are unique ground states of some 2-local frustration-free Hamiltonians. Moreover, we show that the elements in Θk may not be the join of atoms, indicating a richer structure for Θk beyond the convex structure. Our study of Θk deepens the understanding of ground-state space properties for frustration-free Hamiltonians, from the new perspective of reduced spaces.

DOI
10.1063/1.4748527

Related papers

Complete characterization of the ground-space structure of two-body frustration-free Hamiltonians for qubits

Zhengfeng Ji, Zhaohui Wei, Bei Zeng

The problem of finding the ground state of a frustration-free Hamiltonian carrying only two-body interactions between qubits is known to be solvable in polynomial time. It is also shown recently that, for any such Hamiltonian, there is always a ground state that is a product of single- or two-qubit states. However, it remains unclear whether the whole ground space is of any succinct structure. Here, we give a complete characterization of the ground space of any two-body frustration-free Hamiltonian of qubits. Namely, it is a span of tree tensor network states of the same tree structure. This characterization allows us to show that the problem of determining the ground-state degeneracy is as hard as, but no harder than, its classical analog.

arXiv:1010.2480•Physical Review A•Oct 27, 2011•16 citations

From ground states to local Hamiltonians

Jianxin Chen, Zhengfeng Ji, Bei Zeng +1 more

Traditional quantum physics solves ground states for a given Hamiltonian, while quantum information science asks for the existence and construction of certain Hamiltonians for given ground states. In practical situations, one would be mainly interested in local Hamiltonians with certain interaction patterns, such as nearest-neighbor interactions on some types of lattices. A necessary condition for a space $V$ to be the ground-state space of some local Hamiltonian with a given interaction pattern is that the maximally mixed state supported on $V$ is uniquely determined by its reduced density matrices associated with the given pattern, based on the principle of maximum entropy. However, it is unclear whether this condition is in general also sufficient. We examine the situations for the existence of such a local Hamiltonian to have $V$ satisfying the necessary condition mentioned above as its ground-state space by linking to faces of the convex body of the local reduced states. We further discuss some methods for constructing the corresponding local Hamiltonians with given interaction patterns, mainly from physical points of view, including constructions related to perturbation methods, local frustration-free Hamiltonians, as well as thermodynamical ensembles.

arXiv:1110.6583•Physical Review A•Aug 30, 2012•31 citations

"Characterizing and quantifying quantum frustration: exact bounds to entanglement and correlations, and local and global observables"

Fabrizio Illuminati

We discuss a general scheme for the study of frustration in quantum systems. We introduce a universal measure of frustration for arbitrary quantum systems with Hamiltonians made of sums of local two-body contributions in terms of the overlap between the unfrustrated ground state of the pair Hamiltonians and the frustrated ground state of the total Hamiltonian. We derive an exact lower bound this overlap measure of frutration in degenerate ground states of quantum many-body systems. The bound results in the sum of two contributions: entanglement and classical correlations arising from local measurements. We show that average frustration properties are completely determined by the behavior of the maximally mixed ground state. We identify sufficient conditions for a quantum spin system to saturate the bound, and for models with twofold degeneracy we prove that average and local frustration coincide. If all the (pure) ground states of a given Hamiltonian saturate the inequality, then the system is said to be inequality saturating. These conditions provide a generalization to the quantum domain of the Toulouse criteria for classical frustration-free systems. The models satisfying these conditions can be reasonably identified as geometrically unfrustrated and subject to frustration of purely quantum origin. Our results therefore establish a unified framework for studying the intertwining of geometric and quantum contributions to frustration. The mathematical scheme can be put to test by relating the overlap measure and the inequalities it obeys to global and local observables in terms of the static structure factor and transverse n-point correlation functions.

•Jan 1, 2013•0 citations

Graph states as ground states of two-body frustration-free Hamiltonians

Andrew S Darmawan, Stephen D. Bartlett

The framework of measurement-based quantum computation (MBQC) allows us to view the ground states of local Hamiltonians as potential resources for universal quantum computation. A central goal in this field is to find models with ground states that are universal for MBQC and that are also natural in the sense that they involve only two-body interactions and have a small local Hilbert space dimension. Graph states are the original resource states for MBQC, and while it is not possible to obtain graph states as exact ground states of two-body Hamiltonians here we construct two-body frustration-free Hamiltonians that have arbitrarily good approximations of graph states as unique ground states. The construction involves taking a two-body frustration-free model that has a ground state convertible to a graph state with stochastic local operations, then deforming the model such that its ground state is close to a graph state. Each graph state qubit resides in a subspace of a higher dimensional particle. This deformation can be applied to two-body frustration-free Affleck-Kennedy-Lieb-Tasaki (AKLT) models, yielding Hamiltonians that are exactly solvable with exact tensor network expressions for ground states. For the star-lattice AKLT model, the ground state of which is not expected to be a universal resource for MBQC, applying such a deformation appears to enhance the computational power of the ground state, promoting it to a universal resource for MBQC. Transitions in computational power, similar to percolation phase transitions, can be observed when Hamiltonians are deformed in this way. Improving the fidelity of the ground state comes at the cost of a shrinking gap. While analytically proving gap properties for these types of models is difficult in general, we provide a detailed analysis of the deformation of a spin-1 AKLT state to a linear graph state.

arXiv:1403.2402•New Journal of Physics•Jul 9, 2014•21 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

On Frustration-Free Quantum Spin Models

Danilo Polo Ojito, Emil V. Prodan, Tom Stoiber

The goal of our work is to characterize the landscape of the frustration-free quantum spin models over the Cayley graph of a finitely generated group G. This is achieved by establishing $G$-equivariant morphisms from the partially ordered space of frustration-free models to the partially ordered spaces 1) of hereditary C*-algebras of the underlying UHF algebra of quasi-local observables, 2) of open projections in its double dual, and 3) of subsets of pure state space. Our main result consists of an intrinsic characterization of the images of these morphisms, which captures the essence of frustration-freeness and enables us to extend the concept to generic AF-C*-algebras. Additionally, using well established facts about AF-C*-algebras, we prove density theorems and provide intrinsic and optimal characterizations of frustration-free ground states.

arXiv:2507.03201•Jul 3, 2025•0 citations
We study the ground-state space properties for frustration-free Hamiltonians. We introduce a concept of “reduced spaces” to characterize local structures of ground-state spaces. For a many-body system, we characterize mathematical structures for the set Θk of all the k-particle reduced spaces, which with a binary operation called join forms a semilattice that can be interpreted as an abstract convex structure. The smallest nonzero elements in Θk, called atoms, are analogs of extreme points. We study the properties of atoms in Θk and discuss its relationship with ground states of k-local frustration-free Hamiltonians. For spin-1/2 systems, we show that all the atoms in Θ2 are unique ground states of some 2-local frustration-free Hamiltonians. Moreover, we show that the elements in Θk may not be the join of atoms, indicating a richer structure for Θk beyond the convex structure. Our study of Θk deepens the understanding of ground-state space properties for frustration-free Hamiltonians, from the new perspective of reduced spaces.
The problem of finding the ground state of a frustration-free Hamiltonian carrying only two-body interactions between qubits is known to be solvable in polynomial time. It is also shown recently that, for any such Hamiltonian, there is always a ground state that is a product of single- or two-qubit states. However, it remains unclear whether the whole ground space is of any succinct structure. Here, we give a complete characterization of the ground space of any two-body frustration-free Hamiltonian of qubits. Namely, it is a span of tree tensor network states of the same tree structure. This characterization allows us to show that the problem of determining the ground-state degeneracy is as hard as, but no harder than, its classical analog.
Traditional quantum physics solves ground states for a given Hamiltonian, while quantum information science asks for the existence and construction of certain Hamiltonians for given ground states. In practical situations, one would be mainly interested in local Hamiltonians with certain interaction patterns, such as nearest-neighbor interactions on some types of lattices. A necessary condition for a space VVV to be the ground-state space of some local Hamiltonian with a given interaction pattern is that the maximally mixed state supported on VVV is uniquely determined by its reduced density matrices associated with the given pattern, based on the principle of maximum entropy. However, it is unclear whether this condition is in general also sufficient. We examine the situations for the existence of such a local Hamiltonian to have VVV satisfying the necessary condition mentioned above as its ground-state space by linking to faces of the convex body of the local reduced states. We further discuss some methods for constructing the corresponding local Hamiltonians with given interaction patterns, mainly from physical points of view, including constructions related to perturbation methods, local frustration-free Hamiltonians, as well as thermodynamical ensembles.
We discuss a general scheme for the study of frustration in quantum systems. We introduce a universal measure of frustration for arbitrary quantum systems with Hamiltonians made of sums of local two-body contributions in terms of the overlap between the unfrustrated ground state of the pair Hamiltonians and the frustrated ground state of the total Hamiltonian. We derive an exact lower bound this overlap measure of frutration in degenerate ground states of quantum many-body systems. The bound results in the sum of two contributions: entanglement and classical correlations arising from local measurements. We show that average frustration properties are completely determined by the behavior of the maximally mixed ground state. We identify sufficient conditions for a quantum spin system to saturate the bound, and for models with twofold degeneracy we prove that average and local frustration coincide. If all the (pure) ground states of a given Hamiltonian saturate the inequality, then the system is said to be inequality saturating. These conditions provide a generalization to the quantum domain of the Toulouse criteria for classical frustration-free systems. The models satisfying these conditions can be reasonably identified as geometrically unfrustrated and subject to frustration of purely quantum origin. Our results therefore establish a unified framework for studying the intertwining of geometric and quantum contributions to frustration. The mathematical scheme can be put to test by relating the overlap measure and the inequalities it obeys to global and local observables in terms of the static structure factor and transverse n-point correlation functions.
The framework of measurement-based quantum computation (MBQC) allows us to view the ground states of local Hamiltonians as potential resources for universal quantum computation. A central goal in this field is to find models with ground states that are universal for MBQC and that are also natural in the sense that they involve only two-body interactions and have a small local Hilbert space dimension. Graph states are the original resource states for MBQC, and while it is not possible to obtain graph states as exact ground states of two-body Hamiltonians here we construct two-body frustration-free Hamiltonians that have arbitrarily good approximations of graph states as unique ground states. The construction involves taking a two-body frustration-free model that has a ground state convertible to a graph state with stochastic local operations, then deforming the model such that its ground state is close to a graph state. Each graph state qubit resides in a subspace of a higher dimensional particle. This deformation can be applied to two-body frustration-free Affleck-Kennedy-Lieb-Tasaki (AKLT) models, yielding Hamiltonians that are exactly solvable with exact tensor network expressions for ground states. For the star-lattice AKLT model, the ground state of which is not expected to be a universal resource for MBQC, applying such a deformation appears to enhance the computational power of the ground state, promoting it to a universal resource for MBQC. Transitions in computational power, similar to percolation phase transitions, can be observed when Hamiltonians are deformed in this way. Improving the fidelity of the ground state comes at the cost of a shrinking gap. While analytically proving gap properties for these types of models is difficult in general, we provide a detailed analysis of the deformation of a spin-1 AKLT state to a linear graph state.
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.
The goal of our work is to characterize the landscape of the frustration-free quantum spin models over the Cayley graph of a finitely generated group G. This is achieved by establishing GGG-equivariant morphisms from the partially ordered space of frustration-free models to the partially ordered spaces 1) of hereditary C*-algebras of the underlying UHF algebra of quasi-local observables, 2) of open projections in its double dual, and 3) of subsets of pure state space. Our main result consists of an intrinsic characterization of the images of these morphisms, which captures the essence of frustration-freeness and enables us to extend the concept to generic AF-C*-algebras. Additionally, using well established facts about AF-C*-algebras, we prove density theorems and provide intrinsic and optimal characterizations of frustration-free ground states.