The spectrum of the Heisenberg ferromagnet from geometric considerations

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 and graph theory

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, 20171 citation

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

Bounding and approximating parabolas for the spectrum of Heisenberg spin systems

H.-J Schmidt, J Schnack, M 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.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/0101228Europhysics Letters (EPL)Jul 1, 200112 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

Fast clique minor generation in Chimera qubit connectivity graphs

Kelly Boothby, Andrew D. King, Aidan Roy

The current generation of D-Wave quantum annealing processor is designed to minimize the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a {\em Chimera} graph $\mathcal C_{M,N,L}$ . In order to solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor-embedded into a Chimera graph. We define a combinatorial class of {\em native clique minors} in Chimera graphs with vertex images of uniform, near minimal size, and provide a polynomial-time algorithm that finds a maximum native clique minor in a given induced subgraph of a Chimera graph. These minors allow improvement over recent work and have immediate practical applications in the field of quantum annealing.The current generation of D-Wave quantum annealing processor is designed to minimize the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a {\em Chimera} graph $\mathcal C_{M,N,L}$. In order to solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor-embedded into a Chimera graph. We define a combinatorial class of {\em native clique minors} in Chimera graphs with vertex images of uniform, near minimal size, and provide a polynomial-time algorithm that finds a maximum native clique minor in a given induced subgraph of a Chimera graph. These minors allow improvement over recent work and have immediate practical applications in the field of quantum annealing.

arXiv:1507.04774Jul 16, 201512 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

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

The current generation of D-Wave quantum annealing processor is designed to minimize the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a {\em Chimera} graph

\mathcal C_{M,N,L}

. In order to solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor-embedded into a Chimera graph. We define a combinatorial class of {\em native clique minors} in Chimera graphs with vertex images of uniform, near minimal size, and provide a polynomial-time algorithm that finds a maximum native clique minor in a given induced subgraph of a Chimera graph. These minors allow improvement over recent work and have immediate practical applications in the field of quantum annealing.

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.