Quantum-Inspired Tensor Network Methods for Quadratic Unconstrained Binary Optimization

Conventional approaches for integer optimization show little benefit from GPU acceleration. On the other hand, the main computational problem in quantum many-body physics is the computation of eigenvectors of exponentially large, but structured, matrices. To address such problems, small dense matrix operations are employed, which are amenable to parallel computing. Thus, efficient meth- ods that run in parallel on both CPUs and GPUs have been devised, such as the Density Matrix Renormalization Group (DMRG) algorithm. Embedding binary optimization programs into quantum systems reformulates minimization as an eigenvalue problem for which scalable, parallelizable algorithms exist. Hence, we represent these systems using matrix product operators (MPO), a tensor net- work. MPOs exactly represent QUBO problems in $O(N^3)$ space, avoiding the exponential cost of a direct tensor representation. Our algorithm constructs the MPO for a QUBO problem and applies DMRG, which approximates the smallest eigenvalue within a certain truncation tolerance in polynomial time. We provide a methodological description of the algorithm and numerical results from our Julia library TenSolver.jl.