Quick design of feasible tensor networks for constrained combinatorial optimization
arXiv:2409.01699 · doi:10.22331/q-2025-07-21-1799
Abstract
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.
24 pages, 13 figures
References in corpus (27)
- Quantum Computing in the NISQ era and beyond
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- A Quantum Approximate Optimization Algorithm
- The ITensor Software Library for Tensor Network Calculations
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Tensor networks for complex quantum systems
- Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
- Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
- -mixers: analytical and numerical results for QAOA
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Developments in the Tensor Network -- from Statistical Mechanics to Quantum Entanglement
- Domain wall encoding of discrete variables for quantum annealing and QAOA
- A cross-disciplinary introduction to quantum annealing-based algorithms
- Tropical Tensor Network for Ground States of Spin Glasses
- Tensor Network Contractions for #SAT
- Fast counting with tensor networks
- Computing solution space properties of combinatorial optimization problems via generic tensor networks
- A quantum-inspired tensor network method for constrained combinatorial optimization problems
- Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
- Enhancing VQE Convergence for Optimization Problems with Problem-specific Parameterized Quantum Circuits
- Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
- Tensor Network Based HOBO Solver
- Polynomial-time Solver of Tridiagonal QUBO, QUDO and Tensor QUDO problems with Tensor Networks
- Tensor-Network Formulation of the Traveling Salesman Problem and Variants
- HOBOTAN: Efficient Higher Order Binary Optimization Solver with Tensor Networks and PyTorch