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

Characterizing the ground-state properties of disordered systems, such as spin glasses and combinatorial optimization problems, is fundamental but computationally challenging. Finding exact ground states and counting their degeneracies are NP-hard and #P-hard, respectively, placing severe limits on exact algorithms. While tensor networks have emerged as a powerful paradigm for these tasks by leveraging massive hardware parallelization, their scalability is fundamentally bottlenecked by exponential memory growth. To overcome this, we introduce the branch-and-bound tensor network (BBTN) method. By integrating adaptive branch-and-bound search with efficient tropical tensor network contraction, BBTN sets new benchmarks for exact computation. It pushes the tractable frontier to previously unreachable scales, enabling exact ground-state counting for ± J spin glasses up to 65 × 65 and maximum independent set solving on King’s subgraphs up to 100 × 100 , reducing run times required by state-of-the-art solvers from millions of years to hours. Furthermore, it consistently outperforms leading open-source integer-programming solvers and runs up to an order of magnitude faster than commercial solvers in rugged landscapes, establishing a versatile and scalable framework for solving hard problems in statistical physics and combinatorial optimization.

Authors

Institutions

Publication Details

Journal
Physical Review Research
Published
2026-11-18
DOI
https://doi.org/10.1103/g76v-wxz7
Citations
1
Primary Topic
Quantum many-body systems
Type
article
Field-Weighted Citation Impact
0.87

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

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

高绚照, Pan Zhang, Jin-Guo Liu, Feng Pan et al.
1 citations
Physical Review Research
Quantum many-body systems
0.87
article

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

高绚照, Pan Zhang, Jin-Guo Liu, Feng Pan, Yi-Jia Wang
article en
1 citations

Abstract

Characterizing the ground-state properties of disordered systems, such as spin glasses and combinatorial optimization problems, is fundamental but computationally challenging. Finding exact ground states and counting their degeneracies are NP-hard and #P-hard, respectively, placing severe limits on exact algorithms. While tensor networks have emerged as a powerful paradigm for these tasks by leveraging massive hardware parallelization, their scalability is fundamentally bottlenecked by exponential memory growth. To overcome this, we introduce the branch-and-bound tensor network (BBTN) method. By integrating adaptive branch-and-bound search with efficient tropical tensor network contraction, BBTN sets new benchmarks for exact computation. It pushes the tractable frontier to previously unreachable scales, enabling exact ground-state counting for ± J spin glasses up to 65 × 65 and maximum independent set solving on King’s subgraphs up to 100 × 100 , reducing run times required by state-of-the-art solvers from millions of years to hours. Furthermore, it consistently outperforms leading open-source integer-programming solvers and runs up to an order of magnitude faster than commercial solvers in rugged landscapes, establishing a versatile and scalable framework for solving hard problems in statistical physics and combinatorial optimization.

Physical Review ResearchVol. 8(4)
Singapore University of Technology and Design (SG), Chinese Academy of Sciences (CN), Simons Foundation (US), Institute of Theoretical Physics (CN), Beijing Academy of Quantum Information Sciences (CN), University of Chinese Academy of Sciences (CN), Flatiron Institute (US), The Hong Kong University of Science and Technology (Guangzhou) (CN)
Nvidia, National Research Foundation Singapore, Ministry of Education - Singapore, National Natural Science Foundation of China, Guangzhou Municipal Science and Technology Project, National Key Research and Development Program of China
Openalex Percentile: Top 34%
Quantum many-body systems
0.87
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon