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

The spectrum of the Heisenberg ferromagnet and graph theory

Yingkai Ouyang

Published Jul 8, 2017• 2 citations
OpenAlex

Abstract

We give a polynomial-time algorithm for computing upper bounds on some of the smaller energy eigenvalues in a spin-1/2 ferromagnetic Heisenberg model with any graph $G$ for the underlying interactions. An important ingredient is the connection between Heisenberg models and the symmetric products of $G$. Our algorithms for computing upper bounds are based on generalized diameters of graphs. Computing the upper bounds amounts to solving the minimum assignment problem on $G$, which has well-known polynomial-time algorithms from the field of combinatorial optimization. We also study the possibility of computing the lower bounds on some of the smaller energy eigenvalues of Heisenberg models. This amounts to estimating the isoperimetric inequalities of the symmetric product of graphs. By using connections with discrete Sobolev inequalities, we show that this can be performed by considering just the vertex-induced subgraphs of $G$. If our conjecture for a polynomial time approximation algorithm to solve the edge-isoperimetric problem holds, then our proposed method of estimating the energy eigenvalues via approximating the edge-isoperimetric properties of vertex-induced subgraphs will yield a polynomial time algorithm for estimating the smaller energy eigenvalues of the Heisenberg ferromagnet.

Related papers

The spectrum of the Heisenberg ferromagnet from geometric considerations

Yingkai Ouyang

We give a polynomial-time algorithm for computing upper bounds on some of the smaller energy eigenvalues in a spin-1/2 ferromagnetic Heisenberg model with any graph $G$ for the underlying interactions. An important ingredient is the connection between Heisenberg models and the symmetric products of $G$. Our algorithms for computing upper bounds are based on generalized diameters of graphs. Computing the upper bounds amounts to solving the minimum assignment problem on $G$, which has well-known polynomial-time algorithms from the field of combinatorial optimization. We also study the possibility of computing the lower bounds on some of the smaller energy eigenvalues of Heisenberg models. This amounts to estimating the isoperimetric inequalities of the symmetric product of graphs. By using connections with discrete Sobolev inequalities, we show that this can be performed by considering just the vertex-induced subgraphs of $G$. If our conjecture for a polynomial time approximation algorithm to solve the edge-isoperimetric problem holds, then our proposed method of estimating the energy eigenvalues via approximating the edge-isoperimetric properties of vertex-induced subgraphs will yield a polynomial time algorithm for estimating the smaller energy eigenvalues of the Heisenberg ferromagnet.

•Jul 8, 2017•0 citations

A spin-energy operator inequality for Heisenberg-coupled qubits

Daniel Ranard, Charles Jess Riedel

We slightly strengthen an operator inequality identified by Correggi et al. that lower bounds the energy of a Heisenberg-coupled graph of $s=1/2$ spins using the total spin. In particular, $ΔH \ge C Δ\vec{S}^2$ for a graph-dependent constant $C$, where $ΔH$ is the energy above the ground state and $Δ\vec{S}^2$ is the amount by which the square of the total spin $\vec{S} = \sum_i \vecσ_i/2$ falls below its maximum possible value. We obtain explicit constants in the special case of a cubic lattice. We briefly discuss the interpretation of this bound in terms of low-energy, approximately non-interacting magnons in spin wave theory and contrast it with another inequality found by Bärwinkel et al.

arXiv:2302.11267•Feb 22, 2023•0 citations

Efficient quantum algorithm for Heisenberg spin systems

Sergey Bravyi, David Gosset, Yinchen Liu +1 more

We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by $2μ$, where $μ$ is the magnetic field along the $Z$ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.

quant-pharXiv:2607.14401•Jul 17, 2026•5 citations

Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

Sevag Gharibian, Ojas Parekh

Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.

arXiv:1909.08846•Leibniz international proceedings in informatics•Jan 1, 2019•50 citations

New upper and lower bounds for randomized and quantum local search

Shengyu Zhang

Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models.The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube (0, 1)n and the constant dimensional grids [n]d, two particular product graphs that recently drew much attention, we get the following tight results: RLS((0, 1)n) = Θ(2n/2n1/2), QLS((0, 1)n) = Θ(2n/3n1/6); RLS([n]d) = Θ(nd/2), ∀ d ≥ 4, QLS([n]d) = Θ(nd/3), ∀ d ≥ 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [2], Ambainis (unpublished) and Santha and Szegedy [20].Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2, a new quantum algorithm using O(☂n(log log n)1.5) queries is given. This improves the previous best known upper bound of O(n2/3) (Aaronson, [2]), and implies that Local Search on grids exhibits different properties in low dimensions.

arXiv:quant-ph/0603034•ACM Symposium on Theory of Computing (STOC)•May 21, 2006•20 citations

Bounding and approximating parabolas for the spectrum of Heisenberg spin systems

Heinz-Juergen Schmidt, J Schnack, Marshall Luban

We prove that for a wide class of quantum spin systems with isotropic Heisenberg coupling the energy eigenvalues which belong to a total spin quantum number S have upper and lower bounds depending at most quadratically on S . The only assumption adopted is that the mean coupling strength of any spin with respect to its neighbours is constant for all N spins. The coefficients of the bounding parabolas are given in terms of special eigenvalues of the N × N coupling matrix which are usually easily evaluated. In addition, we show that the bounding parabolas, if properly shifted, provide very good approximations of the true boundaries of the spectrum. We present numerical examples of frustrated rings, a cube, and an icosahedron.

arXiv:cond-mat/0101228•Europhysics Letters (EPL)•Jul 1, 2001•12 citations
We give a polynomial-time algorithm for computing upper bounds on some of the smaller energy eigenvalues in a spin-1/2 ferromagnetic Heisenberg model with any graph GGG for the underlying interactions. An important ingredient is the connection between Heisenberg models and the symmetric products of GGG. Our algorithms for computing upper bounds are based on generalized diameters of graphs. Computing the upper bounds amounts to solving the minimum assignment problem on GGG, which has well-known polynomial-time algorithms from the field of combinatorial optimization. We also study the possibility of computing the lower bounds on some of the smaller energy eigenvalues of Heisenberg models. This amounts to estimating the isoperimetric inequalities of the symmetric product of graphs. By using connections with discrete Sobolev inequalities, we show that this can be performed by considering just the vertex-induced subgraphs of GGG. If our conjecture for a polynomial time approximation algorithm to solve the edge-isoperimetric problem holds, then our proposed method of estimating the energy eigenvalues via approximating the edge-isoperimetric properties of vertex-induced subgraphs will yield a polynomial time algorithm for estimating the smaller energy eigenvalues of the Heisenberg ferromagnet.
We give a polynomial-time algorithm for computing upper bounds on some of the smaller energy eigenvalues in a spin-1/2 ferromagnetic Heisenberg model with any graph GGG for the underlying interactions. An important ingredient is the connection between Heisenberg models and the symmetric products of GGG. Our algorithms for computing upper bounds are based on generalized diameters of graphs. Computing the upper bounds amounts to solving the minimum assignment problem on GGG, which has well-known polynomial-time algorithms from the field of combinatorial optimization. We also study the possibility of computing the lower bounds on some of the smaller energy eigenvalues of Heisenberg models. This amounts to estimating the isoperimetric inequalities of the symmetric product of graphs. By using connections with discrete Sobolev inequalities, we show that this can be performed by considering just the vertex-induced subgraphs of GGG. If our conjecture for a polynomial time approximation algorithm to solve the edge-isoperimetric problem holds, then our proposed method of estimating the energy eigenvalues via approximating the edge-isoperimetric properties of vertex-induced subgraphs will yield a polynomial time algorithm for estimating the smaller energy eigenvalues of the Heisenberg ferromagnet.
We slightly strengthen an operator inequality identified by Correggi et al. that lower bounds the energy of a Heisenberg-coupled graph of s=1/2s=1/2s=1/2 spins using the total spin. In particular, ΔH≥CΔS⃗2ΔH \ge C Δ\vec{S}^2ΔH≥CΔS2 for a graph-dependent constant CCC, where ΔHΔHΔH is the energy above the ground state and ΔS⃗2Δ\vec{S}^2ΔS2 is the amount by which the square of the total spin S⃗=∑iσ⃗i/2\vec{S} = \sum_i \vecσ_i/2S=∑i​σi​/2 falls below its maximum possible value. We obtain explicit constants in the special case of a cubic lattice. We briefly discuss the interpretation of this bound in terms of low-energy, approximately non-interacting magnons in spin wave theory and contrast it with another inequality found by Bärwinkel et al.
We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by 2μ2μ2μ, where μμμ is the magnetic field along the ZZZ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.
Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.
Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models.The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube (0, 1)n and the constant dimensional grids [n]d, two particular product graphs that recently drew much attention, we get the following tight results: RLS((0, 1)n) = Θ(2n/2n1/2), QLS((0, 1)n) = Θ(2n/3n1/6); RLS([n]d) = Θ(nd/2), ∀ d ≥ 4, QLS([n]d) = Θ(nd/3), ∀ d ≥ 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [2], Ambainis (unpublished) and Santha and Szegedy [20].Our new algorithms work well when the underlying graph expands slowly. As an application to [n]2, a new quantum algorithm using O(☂n(log log n)1.5) queries is given. This improves the previous best known upper bound of O(n2/3) (Aaronson, [2]), and implies that Local Search on grids exhibits different properties in low dimensions.
We prove that for a wide class of quantum spin systems with isotropic Heisenberg coupling the energy eigenvalues which belong to a total spin quantum number S have upper and lower bounds depending at most quadratically on S . The only assumption adopted is that the mean coupling strength of any spin with respect to its neighbours is constant for all N spins. The coefficients of the bounding parabolas are given in terms of special eigenvalues of the N × N coupling matrix which are usually easily evaluated. In addition, we show that the bounding parabolas, if properly shifted, provide very good approximations of the true boundaries of the spectrum. We present numerical examples of frustrated rings, a cube, and an icosahedron.