Quantum annealing for ICT system design automation

摘要

In this paper, we propose a novel architecture for a (quasi) optimization problem solver for system designing automation that combines a problem generator and general problem solver. It efficiently generates the number of constraints from a simple description about system requirements, and solves the optimization problem at high speed by utilizing a powerful problem solver. Our challenge is to apply quantum annealing for this purpose. However, we faced the following technical problems caused by the fundamental properties of a quantum annealer: P1) a quantum annealer does not accept a constraint with inequality, which is necessary to describe system design problems, and P2) digit overflow of the coefficient value in the constraints. In this paper, we illustrate the overall architecture of our problem solver and clarify the aforementioned issues. Then, we present solutions to each problem: S1) a conversion method from inequality to equation by the augmented Lagrange method, and S2) a problem conversion method that reduces the number of digits of the coefficient without changing the meaning of the problem. Through experiments with a number of example problems, we evaluated the performance and accuracy of our scheme in comparison with a traditional rigorous problem solver. We show that our scheme outperforms the solver at least in a number of situations, and discuss its future utility.