Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
arXiv:2501.03521 · doi:10.1109/ACCESS.2025.3563960
Abstract
In this study, we propose a new method for constrained combinatorial optimization using variational quantum circuits. Quantum computers are considered to have the potential to solve large combinatorial optimization problems faster than classical computers. Variational quantum algorithms, such as Variational Quantum Eigensolver (VQE), have been studied extensively because they are expected to work on noisy intermediate scale devices. Unfortunately, many optimization problems have constraints, which induces infeasible solutions during VQE process. Recently, several methods for efficiently solving constrained combinatorial optimization problems have been proposed by designing a quantum circuit so as to output only the states that satisfy the constraints. However, the types of available constraints are still limited. Therefore, we have started to develop variational quantum circuits that can handle a wider range of constraints. The proposed method utilizes a forwarding operation that maps from feasible states for subproblems to those for larger subproblems. As long as appropriate forwarding operations can be defined, iteration of this process can inductively construct variational circuits outputting feasible states even in the case of multiple and complex constraints. In this paper, the proposed method was applied to facility location problem and was found to increase the probability for measuring feasible solutions or optimal solutions. In addition, the cost of the obtained circuit was comparable to that of conventional variational circuits.
13 pages, 8 figures
References in corpus (26)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Quantum Computing in the NISQ era and beyond
- A variational eigenvalue solver on a quantum processor
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- The theory of variational hybrid quantum-classical algorithms
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum optimization using variational algorithms on near-term quantum devices
- Quantum Computation of Electronic Transitions using a Variational Quantum Eigensolver
- Warm-starting quantum optimization
- Is there evidence for exponential quantum advantage in quantum chemistry?
- Accelerated Variational Quantum Eigensolver
- -mixers: analytical and numerical results for QAOA
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Benchmarking the performance of portfolio optimization with QAOA
- Holographic quantum algorithms for simulating correlated spin systems
- A case study of variational quantum algorithms for a job shop scheduling problem
- A cross-disciplinary introduction to quantum annealing-based algorithms
- Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
- Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
- Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
- Natural orbitals and sparsity of quantum mutual information
- Enhancing VQE Convergence for Optimization Problems with Problem-specific Parameterized Quantum Circuits
- Quantum-Classical Computational Molecular Design of Deuterated High-Efficiency OLED Emitters