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:2602.05470 · Physical Review Research

Branch-and-bound tensor networks for exact characterization of classical ground states

Yi-Jia Wang, 高绚照, Pan Zhang, Feng Pan, Jin-Guo Liu

Published Sep 22, 2026• 1 citation
arXivHTMLPDF

Abstract

Characterizing the ground-state properties of disordered systems, such as spin glasses and combinatorial optimization problems, is fundamental to science and engineering. However, computing exact ground states and counting their degeneracies are generally NP-hard and #P-hard problems, respectively, posing a formidable challenge for exact algorithms. Recently, Tensor Networks methods, which utilize high-dimensional linear algebra and achieve massive hardware parallelization, have emerged as a rapidly developing paradigm for efficiently solving these tasks. Despite their success, these methods are fundamentally constrained by the exponential growth of space complexity, which severely limits their scalability. To address this bottleneck, we introduce the Branch-and-Bound Tensor Network (BBTN) method, which seamlessly integrates the adaptive search framework of branch-and-bound with the efficient contraction of tropical tensor networks, significantly extending the reach of exact algorithms. We show that BBTN significantly surpasses existing state-of-the-art solvers, setting new benchmarks for exact computation. It pushes the boundaries of tractability to previously unreachable scales, enabling exact ground-state counting for $\pm J$ spin glasses up to $64 \times 64$ and solving Maximum Independent Set problems on King's subgraphs up to $100 \times 100$. For hard instances, BBTN dramatically reduces the computational cost of standard Tropical Tensor Networks, compressing years of runtime into minutes. Furthermore, it outperforms leading integer-programming solvers by over 30$\times$, establishing a versatile and scalable framework for solving hard problems in statistical physics and combinatorial optimization.

DOI
10.1103/g76v-wxz7

Related papers

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•52 citations

Tensor Network Message Passing

Yijia Wang, Y. Zhang, Feng Ping Pan +1 more

When studying interacting systems, computing their statistical properties is a fundamental problem in various fields such as physics, applied mathematics, and machine learning. However, this task can be quite challenging due to the exponential growth of the state space as the system size increases. Many standard methods have significant weaknesses. For instance, message-passing algorithms can be inaccurate and even fail to converge due to short loops, while tensor network methods can have exponential computational complexity in large graphs due to long loops. In this Letter, we propose a new method called "tensor network message passing." This approach allows us to compute local observables like marginal probabilities and correlations by combining the strengths of tensor networks in contracting small subgraphs with many short loops and the strengths of message-passing methods in globally sparse graphs, thus addressing the crucial weaknesses of both approaches. Our algorithm is exact for systems that are globally treelike and locally dense-connected when the dense local graphs have a limited tree width. We have conducted numerical experiments on synthetic and real-world graphs to compute magnetizations of Ising models and spin glasses, and have demonstrated the superiority of our approach over standard belief propagation and the recently proposed loopy message-passing algorithm. In addition, we discuss the potential applications of our method in inference problems in networks, combinatorial optimization problems, and decoding problems in quantum error correction.

arXiv:2305.01874•Physical Review Letters•Mar 15, 2024•19 citations

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•29 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•1 citation

Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN

Alejandro Mata Ali

In this paper we show that every combinatorial problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any combinatorial problem, both inversion, constraint satisfaction and optimization, by obtaining its equivalent tensor network. This formulation only requires a basic knowledge of classical logical operators, at a first year level of any computer science degree. These equations are not necessarily computable in a reasonable time, nor do they allow to surpass the state of the art in computational complexity, but they allow to have a new perspective for the mathematical analysis of these problems. These equations computation can be approximated by different methods such as Matrix Product State compression. We also present the equations for numerous combinatorial problems. This work proves that, if there is a physical system capable of contracting in polynomial time the tensor networks presented, every NP-Hard problem can be solved in polynomial time.

arXiv:2502.05981•Feb 9, 2025•7 citations

A Block Belief-Propagation Algorithm for the Contraction of Tensor-Networks

Nir Gutman

Simulating many-body quantum systems on a classical computer is difficult due to the large number of degrees of freedom, causing the computational complexity to grow exponentially with system size. Tensor Networks (TN) is a framework that breaks down large tensors into a network of smaller tensors, enabling efficient simulation of certain many-body quantum systems. To calculate expectation values of local observables or simulate nearest-neighbor interactions, a contraction of the entire network is needed. This is a known hard problem, which cannot be done exactly for systems with spatial dimension D>1 and is the major bottleneck in all tensor-network based algorithms. Various approximate-contraction algorithms have been suggested, all with their strengths and weaknesses. Nevertheless, contracting a 2D TN remains a major numerical challenge, limiting the use of TN techniques for many interesting systems. Recently, a close connection between TN and Probabilistic Graphical Models (PGM) has been shown. In the PGM framework, marginals of complicated probability distributions can be approximated using iterative message passing algorithms such as Belief Propagation (BP). The BP algorithm can be adapted to the TN framework as an efficient contraction algorithm. While BP is extremely efficient and easy to parallelize, it often yields inaccurate results for highly correlated quantum states or frustrated systems. To overcome this, we suggest the BlockBP algorithm, which coarse-grains the system into blocks and performs BP between them. This thesis focuses on: (i) development and implementation of the BlockBP algorithm for infinite lattices; (ii) using this algorithm to study the anti-ferromagnetic Heisenberg model on the Kagome lattice in the thermodynamic limit - a frustrated 2D model that is difficult to simulate using existing numerical methods.

quant-pharXiv:2603.13304•Mar 4, 2026•1 citation
Characterizing the ground-state properties of disordered systems, such as spin glasses and combinatorial optimization problems, is fundamental to science and engineering. However, computing exact ground states and counting their degeneracies are generally NP-hard and #P-hard problems, respectively, posing a formidable challenge for exact algorithms. Recently, Tensor Networks methods, which utilize high-dimensional linear algebra and achieve massive hardware parallelization, have emerged as a rapidly developing paradigm for efficiently solving these tasks. Despite their success, these methods are fundamentally constrained by the exponential growth of space complexity, which severely limits their scalability. To address this bottleneck, we introduce the Branch-and-Bound Tensor Network (BBTN) method, which seamlessly integrates the adaptive search framework of branch-and-bound with the efficient contraction of tropical tensor networks, significantly extending the reach of exact algorithms. We show that BBTN significantly surpasses existing state-of-the-art solvers, setting new benchmarks for exact computation. It pushes the boundaries of tractability to previously unreachable scales, enabling exact ground-state counting for ±J\pm J±J spin glasses up to 64×6464 \times 6464×64 and solving Maximum Independent Set problems on King's subgraphs up to 100×100100 \times 100100×100. For hard instances, BBTN dramatically reduces the computational cost of standard Tropical Tensor Networks, compressing years of runtime into minutes. Furthermore, it outperforms leading integer-programming solvers by over 30×\times×, establishing a versatile and scalable framework for solving hard problems in statistical physics and combinatorial optimization.
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.
When studying interacting systems, computing their statistical properties is a fundamental problem in various fields such as physics, applied mathematics, and machine learning. However, this task can be quite challenging due to the exponential growth of the state space as the system size increases. Many standard methods have significant weaknesses. For instance, message-passing algorithms can be inaccurate and even fail to converge due to short loops, while tensor network methods can have exponential computational complexity in large graphs due to long loops. In this Letter, we propose a new method called "tensor network message passing." This approach allows us to compute local observables like marginal probabilities and correlations by combining the strengths of tensor networks in contracting small subgraphs with many short loops and the strengths of message-passing methods in globally sparse graphs, thus addressing the crucial weaknesses of both approaches. Our algorithm is exact for systems that are globally treelike and locally dense-connected when the dense local graphs have a limited tree width. We have conducted numerical experiments on synthetic and real-world graphs to compute magnetizations of Ising models and spin glasses, and have demonstrated the superiority of our approach over standard belief propagation and the recently proposed loopy message-passing algorithm. In addition, we discuss the potential applications of our method in inference problems in networks, combinatorial optimization problems, and decoding problems in quantum error correction.
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.
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.
In this paper we show that every combinatorial problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any combinatorial problem, both inversion, constraint satisfaction and optimization, by obtaining its equivalent tensor network. This formulation only requires a basic knowledge of classical logical operators, at a first year level of any computer science degree. These equations are not necessarily computable in a reasonable time, nor do they allow to surpass the state of the art in computational complexity, but they allow to have a new perspective for the mathematical analysis of these problems. These equations computation can be approximated by different methods such as Matrix Product State compression. We also present the equations for numerous combinatorial problems. This work proves that, if there is a physical system capable of contracting in polynomial time the tensor networks presented, every NP-Hard problem can be solved in polynomial time.
Simulating many-body quantum systems on a classical computer is difficult due to the large number of degrees of freedom, causing the computational complexity to grow exponentially with system size. Tensor Networks (TN) is a framework that breaks down large tensors into a network of smaller tensors, enabling efficient simulation of certain many-body quantum systems. To calculate expectation values of local observables or simulate nearest-neighbor interactions, a contraction of the entire network is needed. This is a known hard problem, which cannot be done exactly for systems with spatial dimension D>1 and is the major bottleneck in all tensor-network based algorithms. Various approximate-contraction algorithms have been suggested, all with their strengths and weaknesses. Nevertheless, contracting a 2D TN remains a major numerical challenge, limiting the use of TN techniques for many interesting systems. Recently, a close connection between TN and Probabilistic Graphical Models (PGM) has been shown. In the PGM framework, marginals of complicated probability distributions can be approximated using iterative message passing algorithms such as Belief Propagation (BP). The BP algorithm can be adapted to the TN framework as an efficient contraction algorithm. While BP is extremely efficient and easy to parallelize, it often yields inaccurate results for highly correlated quantum states or frustrated systems. To overcome this, we suggest the BlockBP algorithm, which coarse-grains the system into blocks and performs BP between them. This thesis focuses on: (i) development and implementation of the BlockBP algorithm for infinite lattices; (ii) using this algorithm to study the anti-ferromagnetic Heisenberg model on the Kagome lattice in the thermodynamic limit - a frustrated 2D model that is difficult to simulate using existing numerical methods.