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
- 高绚照 (ORCID: https://orcid.org/0000-0002-1495-1531)
- Pan Zhang (ORCID: https://orcid.org/0000-0002-8415-567X)
- Jin-Guo Liu (ORCID: https://orcid.org/0000-0003-1635-2679)
- Feng Pan (ORCID: https://orcid.org/0000-0003-1850-6520)
- Yi-Jia Wang (ORCID: https://orcid.org/0009-0009-9219-8993)
Institutions
- 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)
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
- 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