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

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

Adil A. Gangat, Johnnie Gray

Published Dec 23, 2024• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreve.110.065306

Related papers

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

Marek M. Rams, Masoud Mohseni, Daniel Eppens +2 more

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.

arXiv:1811.06518•Physical review. E•Aug 23, 2021•21 citations

Tensor-Network Markov-Chain Monte Carlo: Efficient Sampling of Three-Dimensional Spin Glasses

Tao Chen, Jing Liu, Youjin Deng +1 more

Sampling equilibrium configurations of three-dimensional (3D) spin glasses with quenched disorder remains a fundamental challenge in statistical physics. The rugged energy landscape, pronounced critical slowing down, and intrinsic ergodicity breaking render standard Monte Carlo methods severely inefficient, particularly for large systems at low temperatures. In this Letter, we introduce the tensor-network Markov-chain Monte Carlo (TNMCMC) approach to address the issue. By formulating large-scale collective updates via tensor-network contractions on 2D lattice slices, TNMCMC yields unbiased samples of the Boltzmann distribution while substantially reducing autocorrelation times relative to conventional MCMC approaches. Numerical benchmarks on 3D spin glasses demonstrate that the method systematically mitigates critical slowing down. Furthermore, application to three- and four-state 3D Potts models shows that TNMCMC can traverse the exponential free-energy barriers of first-order phase transitions that typically hinder local MC updates. These results establish TNMCMC as a promising numerical framework capable of addressing important 3D problems in statistical physics and beyond, such as the precise computation of low-temperature thermodynamic properties of three-dimensional spin glasses and the decoding of quantum error-correcting codes with a three-dimensional topology.

arXiv:2509.23945•Physical Review Letters•Aug 12, 2026•0 citations

Hyperoptimized Approximate Contraction of Tensor Networks with Arbitrary Geometry

Johnnie Gray, Garnet Kin‐Lic Chan

Tensor network contraction is central to problems ranging from many-body physics to computer science. We describe how to approximate tensor network contraction through bond compression on arbitrary graphs. In particular, we introduce a hyperoptimization over the compression and contraction strategy itself to minimize error and cost. We demonstrate that our protocol outperforms both handcrafted contraction strategies in the literature as well as recently proposed general contraction algorithms on a variety of synthetic and physical problems on regular lattices and random regular graphs. We further showcase the power of the approach by demonstrating approximate contraction of tensor networks for frustrated three-dimensional lattice partition functions, dimer counting on random regular graphs, and to access the hardness transition of random tensor network models, in graphs with many thousands of tensors. Published by the American Physical Society 2024

arXiv:2206.07044•Physical Review X•Jan 26, 2024•29 citations

Tensor network surrogate models for variational quantum computation

Ryo Watanabe, Dries Sels, Joseph Tindall

We adopt a two-dimensional tensor-network (TN) ansatz to simulate variational quantum algorithms on two-dimensional qubit architectures, demonstrating its capability to accurately simulate deep circuits through the Quantum Approximate Optimization Algorithm (QAOA) applied to Ising spin-glass problems on heavy-hexagonal and square lattices. For heavy-hexagonal problems with up to three-body interactions, parameters trained on small instances and transferred to systems an order of magnitude larger improve the sampled energy distribution only up to intermediate depths, indicating a fundamental limit of parameter concentration as a transfer strategy. By extending the training itself with TN simulations on larger system sizes, we avoid local minima and obtain lower-energy samples. Analyses of entanglement growth and importance sampling show that the simulation remains classically feasible with moderate bond dimension. We find that parameter concentration also persists on square lattices, albeit at substantially higher computational cost to perform reliable sampling. Overall, our TN framework not only provides an efficient and controlled framework for benchmarking variational quantum algorithms on two-dimensional lattices, but also serves as an effective surrogate model for training variational algorithms.

quant-pharXiv:2604.20180•Apr 23, 2026•0 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

Linear-time classical approximate optimization of cubic-lattice classical spin glasses

Adil A. Gangat

Demonstrating quantum speedup for approximate optimization of classical spin glasses is of current interest. Such a demonstration must be done with respect to the best-known scaling of classical heuristics at a given optimality gap of a given problem. For cubic-lattice classical Ising spin glasses, recent theoretical and experimental developments open the possibility of showing quantum speedup for approximate optimization with quantum annealing. It is therefore desirable to understand the optimality-gap range over which such a speedup should be searched for. Here we show that on cubic-lattice tile-planting models, classical meta-heuristics that are linear-time by construction can reach optimality gaps at which simulated annealing and parallel tempering exhibit super-linear scaling. This implies that the optimality gaps achieved by linear-time classical meta-heuristics can serve as useful upper bounds for the optimality-gap range over which quantum speedups in approximate optimization should be searched for. We also explain how classical heuristics with fixed scaling that is beyond-cubic can provide upper bounds to optimality-gap ranges for beyond-quadratic quantum speedups in approximate optimization. These results encourage the development of classical heuristics with fixed scaling that achieve optimality gaps as small as possible.

arXiv:2501.17267•Physical Review Applied•Jan 9, 2026•1 citation
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 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.
Sampling equilibrium configurations of three-dimensional (3D) spin glasses with quenched disorder remains a fundamental challenge in statistical physics. The rugged energy landscape, pronounced critical slowing down, and intrinsic ergodicity breaking render standard Monte Carlo methods severely inefficient, particularly for large systems at low temperatures. In this Letter, we introduce the tensor-network Markov-chain Monte Carlo (TNMCMC) approach to address the issue. By formulating large-scale collective updates via tensor-network contractions on 2D lattice slices, TNMCMC yields unbiased samples of the Boltzmann distribution while substantially reducing autocorrelation times relative to conventional MCMC approaches. Numerical benchmarks on 3D spin glasses demonstrate that the method systematically mitigates critical slowing down. Furthermore, application to three- and four-state 3D Potts models shows that TNMCMC can traverse the exponential free-energy barriers of first-order phase transitions that typically hinder local MC updates. These results establish TNMCMC as a promising numerical framework capable of addressing important 3D problems in statistical physics and beyond, such as the precise computation of low-temperature thermodynamic properties of three-dimensional spin glasses and the decoding of quantum error-correcting codes with a three-dimensional topology.
Tensor network contraction is central to problems ranging from many-body physics to computer science. We describe how to approximate tensor network contraction through bond compression on arbitrary graphs. In particular, we introduce a hyperoptimization over the compression and contraction strategy itself to minimize error and cost. We demonstrate that our protocol outperforms both handcrafted contraction strategies in the literature as well as recently proposed general contraction algorithms on a variety of synthetic and physical problems on regular lattices and random regular graphs. We further showcase the power of the approach by demonstrating approximate contraction of tensor networks for frustrated three-dimensional lattice partition functions, dimer counting on random regular graphs, and to access the hardness transition of random tensor network models, in graphs with many thousands of tensors. Published by the American Physical Society 2024
We adopt a two-dimensional tensor-network (TN) ansatz to simulate variational quantum algorithms on two-dimensional qubit architectures, demonstrating its capability to accurately simulate deep circuits through the Quantum Approximate Optimization Algorithm (QAOA) applied to Ising spin-glass problems on heavy-hexagonal and square lattices. For heavy-hexagonal problems with up to three-body interactions, parameters trained on small instances and transferred to systems an order of magnitude larger improve the sampled energy distribution only up to intermediate depths, indicating a fundamental limit of parameter concentration as a transfer strategy. By extending the training itself with TN simulations on larger system sizes, we avoid local minima and obtain lower-energy samples. Analyses of entanglement growth and importance sampling show that the simulation remains classically feasible with moderate bond dimension. We find that parameter concentration also persists on square lattices, albeit at substantially higher computational cost to perform reliable sampling. Overall, our TN framework not only provides an efficient and controlled framework for benchmarking variational quantum algorithms on two-dimensional lattices, but also serves as an effective surrogate model for training variational algorithms.
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.
Demonstrating quantum speedup for approximate optimization of classical spin glasses is of current interest. Such a demonstration must be done with respect to the best-known scaling of classical heuristics at a given optimality gap of a given problem. For cubic-lattice classical Ising spin glasses, recent theoretical and experimental developments open the possibility of showing quantum speedup for approximate optimization with quantum annealing. It is therefore desirable to understand the optimality-gap range over which such a speedup should be searched for. Here we show that on cubic-lattice tile-planting models, classical meta-heuristics that are linear-time by construction can reach optimality gaps at which simulated annealing and parallel tempering exhibit super-linear scaling. This implies that the optimality gaps achieved by linear-time classical meta-heuristics can serve as useful upper bounds for the optimality-gap range over which quantum speedups in approximate optimization should be searched for. We also explain how classical heuristics with fixed scaling that is beyond-cubic can provide upper bounds to optimality-gap ranges for beyond-quadratic quantum speedups in approximate optimization. These results encourage the development of classical heuristics with fixed scaling that achieve optimality gaps as small as possible.