The spectrum of the Heisenberg ferromagnet and graph theory

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.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, 20170 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.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.11267Feb 22, 20230 citations

VALIDITY OF THE SPIN-WAVE APPROXIMATION FOR THE FREE ENERGY OF THE HEISENBERG FERROMAGNET

Michele Correggi, Alessandro Giuliani, Robert Seiringer

Abstract. We consider the quantum ferromagnetic Heisenberg model in three di-mensions, for all spins S ≥ 1/2. We rigorously prove the validity of the spin-wave approximation for the excitation spectrum, at the level of the first non-trivial con-tribution to the free energy at low temperatures. Our proof comes with explicit, constructive upper and lower bounds on the error term. It uses in an essential way the bosonic formulation of the model in terms of the Holstein–Primakoff representa-tion. In this language, the model describes interacting bosons with a hard-core on-site repulsion and a nearest-neighbor attraction. This attractive interaction makes the lower bound on the free energy particularly tricky: the key idea there is to prove a differential inequality for the two-particle density, which is thereby shown to be smaller than the probability density of a suitably weighted two-particle random process on the lattice. 1.Abstract. We consider the quantum ferromagnetic Heisenberg model in three di-mensions, for all spins S ≥ 1/2. We rigorously prove the validity of the spin-wave approximation for the excitation spectrum, at the level of the first non-trivial con-tribution to the free energy at low temperatures. Our proof comes with explicit, constructive upper and lower bounds on the error term. It uses in an essential way the bosonic formulation of the model in terms of the Holstein–Primakoff representa-tion. In this language, the model describes interacting bosons with a hard-core on-site repulsion and a nearest-neighbor attraction. This attractive interaction makes the lower bound on the free energy particularly tricky: the key idea there is to prove a differential inequality for the two-particle density, which is thereby shown to be smaller than the probability density of a suitably weighted two-particle random process on the lattice. 1.

Jan 8, 201611 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.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.14401Jul 17, 20260 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.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.08846Leibniz international proceedings in informaticsJan 1, 201916 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.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/0603034ACM Symposium on Theory of Computing (STOC)May 21, 200621 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

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

G

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

G

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.

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.