Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization

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. As a result, feasible solutions were obtained with 100%, and the probability of obtaining optimal solutions was over 22 times higher than that of conventional VQEs. Nevertheless, the cost of the obtained circuit was comparable to that of conventional circuits.