Branch-and-Bound Tensor Network for Combinatorial Optimization

Combinatorial optimization problems are central to science and engineering but are fundamentally intractable, with exact solutions typically requiring exponential complexity. While methods such as branch-and-bound have significantly mitigated the exponential growth in time complexity, and the introduction of tensor network methods has leveraged GPU parallelism, no existing exact solver simultaneously achieves low time and space complexity with high hardware efficiency. Here we address this challenge by introducing the branch-and-bound tensor network (BBTN) method. Through pruning of infeasible or suboptimal configurations and a layer-wise, online branching strategy, BBTN systematically decomposes large-scale instances into manageable subproblems, and then solves each exactly via tropical tensor network contraction under prescribed memory constraints. This hybrid framework integrates the strengths of branch-and-bound for flexible exploitation and partitioning of the solution space, with those of tensor networks, which capturing global problem structures and leveraging modern parallel computing hardware. We demonstrate BBTN's superior performance on the maximum independent set problem for King's subgraphs, which is a key benchmark for Rydberg atom array quantum processors, achieving up to a 30×speedup over state-of-the-art solvers on randomly sampled instances, and enabling exact solutions for high-density instances embedded in 100 ×100 King's graphs, which were previously intractable for all existing solvers. Our method establishes new classical benchmarks for evaluating quantum computing and provides a versatile, scalable framework for tackling diverse combinatorial optimization challenges.