A quantum-inspired tensor network method for constrained combinatorial optimization problems

Abstract

Combinatorial optimization is of general interest for both theoretical study and real-world applications. Fast-developing quantum algorithms provide a different perspective on solving combinatorial optimization problems. In this paper, we propose a quantum-inspired tensor-network-based algorithm for general locally constrained combinatorial optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem, then encodes the constraints directly into a tensor network state and solves the optimal solution by evolving the system to the ground state of the Hamiltonian. We demonstrate our algorithm with the open-pit mining problem, which results in a quadratic asymptotic time complexity. Our numerical results show the effectiveness of this construction and potential applications in further studies for general combinatorial optimization problems.

References in corpus (4)

• A Quantum Approximate Optimization Algorithm
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Valence Bond Solids for Quantum Computation
• A quantum computational approach to the open-pit mining problem

Cited by in corpus (7)

• Tensor networks for interpretable and efficient quantum-inspired machine learning
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Variational matrix product states for combinatorial optimization
• Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems
• Variational Quantum Algorithm Landscape Reconstruction by Low-Rank Tensor Completion