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:1811.06518 · Physical review. E

Approximate optimization, sampling, and spin-glass droplet discovery with tensor networks

Marek M. Rams, Masoud Mohseni, Daniel Eppens, Konrad Jałowiecki, Bartłomiej Gardas

Published Aug 23, 2021• 21 citations
arXivHTMLPDF

Abstract

We devise a deterministic algorithm to efficiently sample high-quality solutions of certain spin-glass systems that encode hard optimization problems. We employ tensor networks to represent the Gibbs distribution of all possible configurations. Using approximate tensor-network contractions, we are able to efficiently map the low-energy spectrum of some quasi-two-dimensional Hamiltonians. We exploit the local nature of the problems to compute spin-glass droplets geometries, which provides a new form of compression of the low-energy spectrum. It naturally extends to sampling, which otherwise, for exact contraction, is #P-complete. In particular, for one of the hardest known problem-classes devised on chimera graphs known as deceptive cluster loops and for up to 2048 spins, we find on the order of 10^{10} degenerate ground states in a single run of our algorithm, computing better solutions than have been reported on some hard instances. Our gradient-free approach could provide new insight into the structure of disordered spin-glass complexes, with ramifications both for machine learning and noisy intermediate-scale quantum devices.

DOI
10.1103/physreve.104.025308

Related papers

Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices

Adil A. Gangat, Johnnie Gray

Obtaining the low-energy configurations of spin glasses that have rugged energy landscapes is of direct relevance to combinatorial optimization and fundamental science. Search-based heuristics have difficulty with this task due to the existence of many local minima that are far from optimal. The work of M. M. Rams et al. [Phys. Rev. E 104, 025308 (2021)2470-004510.1103/PhysRevE.104.025308] demonstrates an alternative that can bypass this issue for spin glasses with planar or quasiplanar geometry: sampling the Boltzmann distribution via approximate contractions of tensor networks. The computational complexity of this approach is due only to the complexity of contracting the network and is therefore independent of landscape ruggedness. Here we initiate an investigation of how to take this approach beyond (quasi-)planar geometry by utilizing hyperoptimized approximate contraction of tensor networks [J. Gray and G. K.-L. Chan, Phys. Rev. X 14, 011009 (2024)2160-330810.1103/PhysRevX.14.011009]. We perform tests on the periodic square- and cubic-lattice, planted-solution Ising spin glasses generated with tile planting [F. Hamze et al., Phys. Rev. E 97, 043303 (2018)2470-004510.1103/PhysRevE.97.043303] for up to 2304 (square lattice) and 216 (cubic lattice) spins. For a fixed bond dimension, the time complexity is quadratic. With a bond dimension of only four, over the tested system sizes, the average relative energy error in the most rugged instance class remains ∼1% (square lattice) or ∼10% (cubic lattice) of optimal. In less rugged instances the solution is always optimal for the square lattice and either optimal or within ∼1% for the cubic lattice. These results suggest that further development of optimization methods based on tensor-network representations of spin glass partition functions may be fruitful, especially given that such methods are not limited to the Ising (i.e., binary) or two-body (i.e., quadratic) settings.

arXiv:2407.21287•Physical review. E•Dec 23, 2024•3 citations

Tropical Tensor Network for Ground States of Spin Glasses

Jin-Guo Liu, Lei Wang, Pan Zhang

We present a unified exact tensor network approach to compute the ground state energy, identify the optimal configuration, and count the number of solutions for spin glasses. The method is based on tensor networks with the tropical algebra defined on the semiring of (R∪{-∞},⊕,⊙). Contracting the tropical tensor network gives the ground state energy; differentiating through the tensor network contraction gives the ground state configuration; mixing the tropical algebra and the ordinary algebra counts the ground state degeneracy. The approach brings together the concepts from graphical models, tensor networks, differentiable programming, and quantum circuit simulation, and easily utilizes the computational power of graphical processing units (GPUs). For applications, we compute the exact ground state energy of Ising spin glasses on square lattice up to 1024 spins, on cubic lattice up to 216 spins, and on three regular random graphs up to 220 spins, on a single GPU; we obtain exact ground state energy of ±J Ising spin glass on the chimera graph of D-Wave quantum annealer of 512 qubits in less than 100 s and investigate the exact value of the residual entropy of ±J spin glasses on the chimera graph; finally, we investigate ground-state energy and entropy of three-state Potts glasses on square lattices up to size 18×18. Our approach provides baselines and benchmarks for exact algorithms for spin glasses and combinatorial optimization problems, and for evaluating heuristic algorithms and mean-field theories.

arXiv:2008.06888•Physical Review Letters•Mar 5, 2021•46 citations

SpinGlassPEPS.jl: Tensor-network package for Ising-like optimization on quasi-two-dimensional graphs

Tomasz Śmierzchalski, Anna M. Dziubyna, Konrad Jałowiecki +4 more

This work introduces SpinGlassPEPS$.$jl, a software package implemented in Julia, designed to find low-energy configurations of generalized Potts models, including Ising and QUBO problems, utilizing heuristic tensor network contraction algorithms on quasi-2D geometries. In particular, the package employs the Projected Entangled-Pairs States to approximate the Boltzmann distribution corresponding to the model's cost function. This enables an efficient branch-and-bound search (within the probability space) that exploits the locality of the underlying problem's topology. As a result, our software enables the discovery of low-energy configurations for problems on quasi-2D graphs, particularly those relevant to modern quantum annealing devices. The modular architecture of SpinGlassPEPS$.$jl supports various contraction schemes and hardware acceleration.

arXiv:2502.02317•Feb 4, 2025•0 citations

Solving Classical and Quantum Spin Glasses with Deep Boltzmann Quantum States

Luca Leone, Arka Dutta, Markus Heyl +2 more

Variational neural network models have achieved remarkable success in solving ground-state problems of quantum many-body systems. However, addressing classical and quantum spin glasses remains challenging, as disorder and energy frustration give rise to an exponentially large number of local energy minima separated by high-energy barriers, hindering the efficiency of conventional Metropolis-based Monte Carlo methods. To bridge this gap, we introduce Deep Boltzmann Quantum States, a class of neural quantum states inspired by deep Boltzmann machines that inherit efficient block Gibbs sampling. We also propose two key advances in the training algorithm. Firstly, we combine natural-gradient updates with state-of-the-art stochastic optimizers. Secondly, we gradually tune the hardness of the problem Hamiltonian by interpolating from an easy to a hard regime, without the need to closely approximate the instantaneous adiabatic state at intermediate times. We match the exact solution or the best available estimate for several instances of classical and quantum Ising spin-glass models with infinite-range interactions and hundreds of spins. We also solve instances of the NP-hard Job Shop Scheduling Problem exceeding the current limitations of quantum annealing hardware. To summarize, deep neural architectures with efficient global update rules and trained within an annealing-like scheme, provide a powerful framework for solving real-world hard combinatorial optimization and for investigating disordered quantum many-body systems.

cond-mat.dis-nnCross-listedarXiv:2605.15899•May 18, 2026•0 citations

Learning Generalized Statistical Mechanics with Matrix Product States

Pablo Díez-Valle, Fernando Martínez-García, Juan José García‐Ripoll +1 more

We introduce a variational algorithm based on Matrix Product States that is trained by minimizing a generalized free energy defined using Tsallis entropy instead of the standard Gibbs entropy. As a result, our model can generate the probability distributions associated with generalized statistical mechanics. The resulting model can be efficiently trained, since the resulting free energy and its gradient can be calculated exactly through tensor network contractions, as opposed to standard methods which require estimating the Gibbs entropy by sampling. We devise a variational annealing scheme by ramping up the inverse temperature, which allows us to train the model while avoiding getting trapped in local minima. We show the validity of our approach in Ising spin-glass problems by comparing it to exact numerical results and quasi-exact analytical approximations. Our work opens up new possibilities for studying generalized statistical physics and solving combinatorial optimization problems with tensor networks.

arXiv:2409.08352•Sep 12, 2024•0 citations

BatchTNMC: Efficient sampling of two-dimensional spin glasses using tensor network Monte Carlo

Tao Chen, Jingtong Zhang, Liu, Jing +2 more

Efficient sampling of two-dimensional statistical physics systems remains a central challenge in computational statistical physics. Traditional Markov chain Monte Carlo (MCMC) methods, including cluster algorithms, provide only partial solutions, as their efficiency collapses for large systems in the presence of frustration and quenched disorder. The recently proposed Tensor Network Monte Carlo (TNMC) method offers a promising alternative, yet its original implementation suffers from inefficiencies due to the lack of scalable parallel sampling. In this work, we introduce BatchTNMC, a GPU-optimized and parallelized implementation of TNMC tailored for large-scale simulations of two-dimensional spin glasses. By leveraging batch processing and parallel sampling across multiple disorder realizations, our implementation achieves speedups of up to five orders of magnitude compared with the original serial scheme. Benchmarking on two-dimensional spin glasses demonstrates dramatic gains in efficiency: for instance, on a single GPU, BatchTNMC concurrently produces 1000 uncorrelated and unbiased samples across 1000 disorder realizations on $1024\times 1024$ lattices in just 3.3 hours, with an acceptance probability of 37%. These results establish BatchTNMC as a scalable and powerful computational framework for the study of two-dimensional disordered spin glass systems.

arXiv:2509.19006•Sep 23, 2025•0 citations
We devise a deterministic algorithm to efficiently sample high-quality solutions of certain spin-glass systems that encode hard optimization problems. We employ tensor networks to represent the Gibbs distribution of all possible configurations. Using approximate tensor-network contractions, we are able to efficiently map the low-energy spectrum of some quasi-two-dimensional Hamiltonians. We exploit the local nature of the problems to compute spin-glass droplets geometries, which provides a new form of compression of the low-energy spectrum. It naturally extends to sampling, which otherwise, for exact contraction, is #P-complete. In particular, for one of the hardest known problem-classes devised on chimera graphs known as deceptive cluster loops and for up to 2048 spins, we find on the order of 10^{10} degenerate ground states in a single run of our algorithm, computing better solutions than have been reported on some hard instances. Our gradient-free approach could provide new insight into the structure of disordered spin-glass complexes, with ramifications both for machine learning and noisy intermediate-scale quantum devices.
Obtaining the low-energy configurations of spin glasses that have rugged energy landscapes is of direct relevance to combinatorial optimization and fundamental science. Search-based heuristics have difficulty with this task due to the existence of many local minima that are far from optimal. The work of M. M. Rams et al. [Phys. Rev. E 104, 025308 (2021)2470-004510.1103/PhysRevE.104.025308] demonstrates an alternative that can bypass this issue for spin glasses with planar or quasiplanar geometry: sampling the Boltzmann distribution via approximate contractions of tensor networks. The computational complexity of this approach is due only to the complexity of contracting the network and is therefore independent of landscape ruggedness. Here we initiate an investigation of how to take this approach beyond (quasi-)planar geometry by utilizing hyperoptimized approximate contraction of tensor networks [J. Gray and G. K.-L. Chan, Phys. Rev. X 14, 011009 (2024)2160-330810.1103/PhysRevX.14.011009]. We perform tests on the periodic square- and cubic-lattice, planted-solution Ising spin glasses generated with tile planting [F. Hamze et al., Phys. Rev. E 97, 043303 (2018)2470-004510.1103/PhysRevE.97.043303] for up to 2304 (square lattice) and 216 (cubic lattice) spins. For a fixed bond dimension, the time complexity is quadratic. With a bond dimension of only four, over the tested system sizes, the average relative energy error in the most rugged instance class remains ∼1% (square lattice) or ∼10% (cubic lattice) of optimal. In less rugged instances the solution is always optimal for the square lattice and either optimal or within ∼1% for the cubic lattice. These results suggest that further development of optimization methods based on tensor-network representations of spin glass partition functions may be fruitful, especially given that such methods are not limited to the Ising (i.e., binary) or two-body (i.e., quadratic) settings.
We present a unified exact tensor network approach to compute the ground state energy, identify the optimal configuration, and count the number of solutions for spin glasses. The method is based on tensor networks with the tropical algebra defined on the semiring of (R∪{-∞},⊕,⊙). Contracting the tropical tensor network gives the ground state energy; differentiating through the tensor network contraction gives the ground state configuration; mixing the tropical algebra and the ordinary algebra counts the ground state degeneracy. The approach brings together the concepts from graphical models, tensor networks, differentiable programming, and quantum circuit simulation, and easily utilizes the computational power of graphical processing units (GPUs). For applications, we compute the exact ground state energy of Ising spin glasses on square lattice up to 1024 spins, on cubic lattice up to 216 spins, and on three regular random graphs up to 220 spins, on a single GPU; we obtain exact ground state energy of ±J Ising spin glass on the chimera graph of D-Wave quantum annealer of 512 qubits in less than 100 s and investigate the exact value of the residual entropy of ±J spin glasses on the chimera graph; finally, we investigate ground-state energy and entropy of three-state Potts glasses on square lattices up to size 18×18. Our approach provides baselines and benchmarks for exact algorithms for spin glasses and combinatorial optimization problems, and for evaluating heuristic algorithms and mean-field theories.
This work introduces SpinGlassPEPS...jl, a software package implemented in Julia, designed to find low-energy configurations of generalized Potts models, including Ising and QUBO problems, utilizing heuristic tensor network contraction algorithms on quasi-2D geometries. In particular, the package employs the Projected Entangled-Pairs States to approximate the Boltzmann distribution corresponding to the model's cost function. This enables an efficient branch-and-bound search (within the probability space) that exploits the locality of the underlying problem's topology. As a result, our software enables the discovery of low-energy configurations for problems on quasi-2D graphs, particularly those relevant to modern quantum annealing devices. The modular architecture of SpinGlassPEPS...jl supports various contraction schemes and hardware acceleration.
Variational neural network models have achieved remarkable success in solving ground-state problems of quantum many-body systems. However, addressing classical and quantum spin glasses remains challenging, as disorder and energy frustration give rise to an exponentially large number of local energy minima separated by high-energy barriers, hindering the efficiency of conventional Metropolis-based Monte Carlo methods. To bridge this gap, we introduce Deep Boltzmann Quantum States, a class of neural quantum states inspired by deep Boltzmann machines that inherit efficient block Gibbs sampling. We also propose two key advances in the training algorithm. Firstly, we combine natural-gradient updates with state-of-the-art stochastic optimizers. Secondly, we gradually tune the hardness of the problem Hamiltonian by interpolating from an easy to a hard regime, without the need to closely approximate the instantaneous adiabatic state at intermediate times. We match the exact solution or the best available estimate for several instances of classical and quantum Ising spin-glass models with infinite-range interactions and hundreds of spins. We also solve instances of the NP-hard Job Shop Scheduling Problem exceeding the current limitations of quantum annealing hardware. To summarize, deep neural architectures with efficient global update rules and trained within an annealing-like scheme, provide a powerful framework for solving real-world hard combinatorial optimization and for investigating disordered quantum many-body systems.
We introduce a variational algorithm based on Matrix Product States that is trained by minimizing a generalized free energy defined using Tsallis entropy instead of the standard Gibbs entropy. As a result, our model can generate the probability distributions associated with generalized statistical mechanics. The resulting model can be efficiently trained, since the resulting free energy and its gradient can be calculated exactly through tensor network contractions, as opposed to standard methods which require estimating the Gibbs entropy by sampling. We devise a variational annealing scheme by ramping up the inverse temperature, which allows us to train the model while avoiding getting trapped in local minima. We show the validity of our approach in Ising spin-glass problems by comparing it to exact numerical results and quasi-exact analytical approximations. Our work opens up new possibilities for studying generalized statistical physics and solving combinatorial optimization problems with tensor networks.
Efficient sampling of two-dimensional statistical physics systems remains a central challenge in computational statistical physics. Traditional Markov chain Monte Carlo (MCMC) methods, including cluster algorithms, provide only partial solutions, as their efficiency collapses for large systems in the presence of frustration and quenched disorder. The recently proposed Tensor Network Monte Carlo (TNMC) method offers a promising alternative, yet its original implementation suffers from inefficiencies due to the lack of scalable parallel sampling. In this work, we introduce BatchTNMC, a GPU-optimized and parallelized implementation of TNMC tailored for large-scale simulations of two-dimensional spin glasses. By leveraging batch processing and parallel sampling across multiple disorder realizations, our implementation achieves speedups of up to five orders of magnitude compared with the original serial scheme. Benchmarking on two-dimensional spin glasses demonstrates dramatic gains in efficiency: for instance, on a single GPU, BatchTNMC concurrently produces 1000 uncorrelated and unbiased samples across 1000 disorder realizations on 1024×10241024\times 10241024×1024 lattices in just 3.3 hours, with an acceptance probability of 37%. These results establish BatchTNMC as a scalable and powerful computational framework for the study of two-dimensional disordered spin glass systems.