Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization

HYAKKA NAKADA 1,2, KOTARO TANAHASHI 1 , AND SHU TANAKA 2,3,4,5 · 2025

Read Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization by HYAKKA NAKADA 1,2, KOTARO TANAHASHI 1 , AND SHU TANAKA 2,3,4,5 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-03521.txt.

Introduction

Hyakka Nakada and co-authors present a 2025 method for building quantum circuits that respect problem constraints. Variational quantum methods hunt for best answers on noisy near-term machines. Constraints are a snag: the search often wanders into forbidden answers. Past fixes design circuits that output only allowed states, but few constraint types fit.

Their inductive construction grows circuits step by step. Each added part keeps the allowed set intact. That widens the range of constraints the trick can serve. The work targets combinatorial problems with hard rules, like scheduling and routing. Cleaner circuits waste fewer runs on invalid answers.

Catalog record

CREATORHYAKKA NAKADA 1,2, KOTARO TANAHASHI 1 , AND SHU TANAKA 2,3,4,5
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-03521

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization HYAKKA NAKADA 1,2, KOTARO TANAHASHI 1 , AND SHU TANAKA 2,3,4,5 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. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. † † history: Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000. † † doi: 10.1109/ACCESS.2017.DOI † † address: Recruit Co., Ltd., Tokyo 100-6640, Japan † † address: Graduate School of Science and Technology, Keio University, Kanagawa 223-8522, Japan † † address: Department of Applied Physics and Physico-Informatics, Keio University, Kanagawa 223-8522, Japan † † address: Keio University Sustainable Quantum Artificial Intelligence Center (KSQAIC), Keio University, Tokyo 108-8345, Japan † † address: Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q), Keio University, Tokyo 108-8345, Japan † † titlenote: This work was partially supported by JSPS KAKENHI (Grant Number JP23H05447), the Council for Science, Technology, and Innovation (CSTI) through the Cross-ministerial Strategic Innovation Promotion Program (SIP), “Promoting the application of advanced quantum technology platforms to social issues” (Funding agency: QST), JST (Grant Number JPMJPF2221). † † corresponding: Corresponding author: Hyakka Nakada (e-mail: [email protected]). I Introduction t!](topskip=0pt, botskip=0pt, midskip=0pt)[width=16.5cm]nakada1.pdf Schematic picture of proposed method. The intermediate anstaz \left|\psi_{k-1}\right\rangle outputs the states superposintioned by feasible solutions of (k-1) th subproblem. Forwarding operation U_{k} is designed to map from the feasible states for the subproblems to that for the larger subproblems. Repeating this operation can construct variational circuits outputting feasible states in original problems. Combinatorial optimization problems have many real-world applications. In recent years, the size of these problems has increased with the volume of data traffic, which leads to the difficulty of solving them in a realistic time. To address this situation, not only heuristics for approximate solutions but also quantum computing technology have been actively developed. Unlike classical computers, quantum computers have the property of simultaneously possessing the states of 0 and 1 . Adding appropriate quantum operations to such a superpositioned state can increase the amplitude of the states for good solutions. Thus, quantum algorithms are expected to solve large combinatorial optimization problems at high speed. Quantum Annealing (QA) [ 1 , 2 ] is known as an optimization method to find the global minimum of an objective function, by a process using quantum fluctuations. In addition, there are several quantum-gate based methods. For example, optimization using Grover adaptive search [ 3 ] or quantum phase estimation [ 4 ] has been proposed. These methods essentially require fault-tolerant quantum computing. Quantum-classical hybrid algorithms using Variational Quantum Circuit (VQC) [ 5 ] have been proposed. This method is expected to work with current Noisy Intermediate-Scale Quantum devices (NISQ) [ 6 ] and has been actively investigated. This method parameterizes a quantum circuit with variational parameters. Based on the expected energy of cost Hamiltonian corresponding to an objective function, the variational parameters are optimized so as to minimize this value. When the variational parameters are well learned, the variational circuit outputs the states for good solutions. Variational Quantum Eigensolver (VQE) [ 7 , 8 , 9 , 10 , 11 ] and Quantum Approximate Optimization Algorithm (QAOA) [ 12 , 13 ] are typical examples of such methods. Many combinatorial optimization problems are constrained so that optimal solutions are strictly selected from feasible solution space. In conventional methods using quantum gates, feasible solutions are preferentially searched for by minimizing the customized objective function with a penalty term for the constraints [ 14 , 15 ] . That is, penalty function methods are usually utilized [ 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 ] . However, these methods raise several challenges. An increase in the number of interactions in a Hamiltonian may disable performing computation in NISQ devices. In addition, the penalty coefficients are not straightforward to adjust appropriately, and emergence of infeasible solutions is principally inevitable. Therefore, without penalty function methods, noble approaches have been developed to search for feasible solutions by designing specific VQCs. For example, several studies on QAOA have reported that mixer gates are modified so that transitions occur only between the states of feasible solutions [ 25 , 26 , 27 , 28 ] . In addition, whereas conventional VQE utilizes simple VQCs multilayered by rotating gates and controlled-NOT (CNOT) gates [ 29 ] , several studies tried to establish specific VQCs so that their output states are exactly feasible [ 30 , 31 ] . By restricting the space of output states to that of the feasible solution space, the region to be searched can be reduced exponentially, which enables efficient optimization. Hereinafter, we focus on VQE algorithms without penalty function methods. Previous studies have derived VQCs that output only feasible states for one-hot constraints [ 30 ] , comparison inequality constraints [ 31 ] , and constraints specialized for traveling salesman problems [ 30 ] . However, few efforts have been made to systematically design appropriate VQCs for more general types of constraints in the field of VQE. This may be due to the following reasons. It is not trivial to construct ansatzes that handle even a single constraint. Although, in principle, Grover’s algorithm can prepare the states that satisfy the constraints by introducing desirable oracles, the circuit becomes too complex and expensive to be employed as a VQC. Therefore, a hardware-efficient ansatz must be derived from scratch and through trial and error. In addition, constructing ansatzes is much more difficult in the case of multiple constraints. Supposing that appropriate ansatzes are obtained for each single constraint, VQCs for all constraints cannot be constructed by combining their circuits in series. This is because the ansatz for each constraint is originally designed to act on the initialized state \left|0\right\rangle . To construct VQCs systematically, we propose a method to generate a quantum circuit inductively by adding a sequential gate operation to the

Read the complete text