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.
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.
Quantum computers are expected to enable fast solving of large-scale combinatorial optimization problems. However, their limitations in fidelity and the number of qubits prevent them from handling real-world problems. Recently, a quantum-inspired solver using tensor networks has been proposed, which works on classical computers. Particularly, tensor networks have been applied to constrained combinatorial optimization problems for practical applications. By preparing a specific tensor network to sample states that satisfy constraints, feasible solutions can be searched for without the method of penalty functions. Previous studies have been based on profound physics, such as U(1) gauge schemes and high-dimensional lattice models. In this study, we devise to design feasible tensor networks using elementary mathematics without such a specific knowledge. One approach is to construct tensor networks with nilpotent-matrix manipulation. The second is to algebraically determine tensor parameters. We showed mathematically that such feasible tensor networks can be constructed to accommodate various types of constraints. For the principle verification, we numerically constructed a feasible tensor network for facility location problem, to find much faster construction than conventional methods. Then, by performing imaginary time evolution, feasible solutions were always obtained, ultimately leading to the optimal solution.
Abstract Constrained combinatorial optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In some heuristic solvers, these are typically addressed by introducing certain Lagrange multipliers in the cost function, by relaxing them in some way, or worse yet, by generating many samples and only keeping valid ones, which leads to very expensive and inefficient searches. In this work, we encode arbitrary integer-valued equality constraints of the form A x ⃗ = b ⃗ , directly into U(1) symmetric tensor networks (TNs) and leverage their applicability as quantum-inspired generative models to assist in the search of solutions to combinatorial optimization problems within the generator-enhanced optimization framework of Alcazar et al (2021 arXiv: 2101.06250 ). This allows us to exploit the generalization capabilities of TN generative models while constraining them so that they only output valid samples. Our constrained TN generative model efficiently captures the constraints by reducing number of parameters and computational costs. We find that at tasks with constraints given by arbitrary equalities, symmetric matrix product states outperform their standard unconstrained counterparts at finding novel and better solutions to combinatorial optimization problems.
In this paper, we present two tensor network quantum-inspired algorithms to solve the knapsack and the shortest path problems, and enables to solve some of its variations. These methods provide an exact equation which returns the optimal solution of the problems. As in other tensor network algorithms for combinatorial optimization problems, the method is based on imaginary time evolution and the implementation of restrictions in the tensor network. In addition, we introduce the use of symmetries and the reutilization of intermediate calculations, reducing the computational complexity for both problems. To show the efficiency of our implementations, we carry out some performance experiments and compare the results with those obtained by other classical algorithms.
Constrained combinatorial optimization (CCO) problems are prevalent across various fields and represent key challenges in computational science and engineering. Although numerous classical and quantum algorithms have been proposed to tackle these problems, substantial limitations still persist. Classical algorithms exhibit exponential computational complexity growth with scale and persistent vulnerability to local minima traps. Quantum computing, while offering theoretical advantages through global superposition, faces practical barriers such as short decoherence times and current hardware limitations. To address these challenges, we propose a quantum-inspired fast algorithm for solving CCO problems. Our approach enhances global search capability with superposition encoding and avoids constraint-induced local minima via a project-feedback strategy. Particularly, our method aligns with mature electronics manufacturing and demonstrates a proof-of-concept implementation in classical systems, indicating high-efficiency potential for solving constrained optimization problems.
This study explores quantum-inspired optimization algorithms (QIOAs) as practical tools for solving constrained combinatorial problems on classical machines. We analyze tasks that can be formulated in Ising or QUBO forms and benchmark three representative approaches: Simulated Bifurcation (SB), Quantum-Inspired Particle Swarm Optimization (QPSO), and a tensor-network (TN) method. A unified evaluation protocol is introduced that captures solution quality, feasibility, runtime, energy consumption, parameter sensitivity, and scalability. To ensure reliable performance, we develop automated penalty-adjustment and schedule-calibration strategies. Experimental results across diverse benchmarks show that SB and TN together yield the best trade-offs between accuracy and runtime: SB is efficient on dense instances with moderate penalties and low energy use, while TN is advantageous for sparse or modular networks, especially on GPUs. QPSO is competitive in smoother landscapes but more sensitive to hyperparameters. By linking performance to structural properties such as spectral gaps and constraint activity, we provide guidance for selecting suitable algorithms. Overall, QIOAs emerge as effective intermediaries between existing classical heuristics and emerging quantum devices, supported by a reproducible, energy-aware evaluation framework.
Simulation of physics problems is one of the most important use cases of quantum computing. For this class of problems, the goal is typically to find the minimum energy state, or the ground state, of a physical system’s Hamiltonian. These problems frequently have constraints, such as symmetry conditions, which must also be satisfied. To solve such problems, researchers in computational physics use quantum-inspired algorithms that execute on classical computers. In particular, tensor network-based eigensolvers such as DMRG have become popular. However, to use these eigensolvers, the constrained optimization problem must first be encoded as a tensor network that implements a low-rank decomposition of the system’s Hamiltonian and state vector. These tensor network encodings are highly flexible, allowing for variables with ≥2 quantum states and supporting efficient constraint encodings that directly constrain the state vector. A critical challenge to developing tensor networkbased encodings is that, currently, the encoding process is manual; significant effort is required to identify an efficient encoding for a new physics problem. In this work, we introduce a quantum constrained optimization problem (QCOP), a general abstraction for describing minimization problems over quantum variables that are subject to hard constraints. We present Masq , the first constraint programming language for QCOPs implementable with tensor networks, and CoTenN , a compiler that automatically maps QCOPs specified with Masq programs to tensor networks. To demonstrate the utility of Masq and CoTenN , we formulate two physics problems in Masq and then use CoTenN to find their ground states. We find the CoTenN -generated tensor networks generally outperform SOTA problem formulations, providing between 2.05 × − 53.32 × total speedups across runs for QCOPs and yielding up to 2.49 ⋅ 10 7 × lower truncation errors for otherwise unconstrained problems.