A new hybrid classical-quantum algorithm for continuous global optimization problems

Abstract

Grover’s algorithm can be employed in global optimization methods providing, in some cases, a quadratic speedup over classical algorithms. This paper describes a new method for continuous global optimization problems that uses a classical algorithm for finding a local minimum and Grover’s algorithm to escape from this local minimum. Such algorithms will be useful when quantum computers of reasonable size are available. Simulations with testbed functions and comparisons with algorithms from the literature are presented.

Appendices

Appendix A: Test functions

Neumaier

$$\begin{aligned} f(x_0,\ldots ,x_{n-1})=\sum \limits _{i=0}^{n-1} (x_i - 1)^2 - \sum \limits _{i=1}^{n-1} x_i x_{i-1}, \quad 0 \le x_i\le 4 \end{aligned}$$

Griewank

$$\begin{aligned} f(x_0,\ldots ,x_{n-1})=\frac{1}{4000} \sum \limits _{i = 0} ^ {n-1} x_i^2 - \prod \limits _{i=0}^{n-1} \cos \left( \frac{x_i}{\sqrt{i+1}} \right) + 1, \quad -40 \le x_i\le 40 \end{aligned}$$

Shekel

$$\begin{aligned} f(x_0,\ldots ,x_{n-1}) = \sum \limits _{i = 0}^{m-1} \frac{1}{c_{i} + \sum \limits _{j = 0}^{n-1} (x_{j} - a_{ji})^2 }, \quad -1 \le x_i\le 1 \end{aligned}$$

Rosenbrock

$$\begin{aligned} f(x_0,\ldots ,x_{n-1}) = \sum \limits _{i=0}^{n-2} (1-x_i)^2+ 100 (x_{i+1} - x_i^2 )^2, \quad -30 \le x_i\le 30 \end{aligned}$$

Michalewicz

$$\begin{aligned} f(x_0,\ldots ,x_{n-1}) =-\sum \limits _{i=0}^{n-1} \sin (x_i) \sin ^{2m}\left( \frac{ i x_i^2}{\pi }\right) , \quad 0 \le x_i\le 10 \end{aligned}$$

Dejong

$$\begin{aligned} f(x_0,\ldots ,x_{n-1}) =\sum \limits _{i=0}^{n-1}x_i^2, \quad -5.12 \le x_i\le 5.12 \end{aligned}$$

Ackley

$$\begin{aligned} f(x_0,\ldots ,x_{n-1})&= -20 \exp \left( -\frac{1}{5} \sqrt{\frac{1}{n} \sum \limits _{i=0}^{n-1} x_i^2} \; \right) -\exp \left( \frac{1}{n} \sum \limits _{i=0}^{n-1} \cos ( 2 \pi x_i) \right) \\&\quad + 20 +\exp (1), \quad -15 \le x_i\le 20 \end{aligned}$$

Schwefel

$$\begin{aligned} f(x_0,\ldots ,x_{n-1}) = -\sum \limits _{i=0}^{n-1} x_i \sin \left( \sqrt{|x_i|}\right) \!, \quad -20 \le x_i\le 20 \end{aligned}$$

Rastrigin

$$\begin{aligned} f(x_0,\ldots ,x_{n-1}) = \sum \limits _{i=0}^{n-1} \left( x_i^2 - 10\cos (2 \pi x_i) + 10 \right) , \quad -5.12 \le x_i\le 5.12 \end{aligned}$$

Raydan

$$\begin{aligned} f(x_0,\ldots ,x_{n-1}) = -\sum \limits _{i=0}^{n-1} \frac{(i+1)}{10}\left( \exp (x_i) - x_i\right) , \quad -5.12 \le x_i\le 5.12 \end{aligned}$$

Appendix B: Standard deviation

This Appendix shows the tables of the standard deviation of the number of evaluations for one, two, and three-variable test functions associated with Tables 1, 2, and 3, respectively. In all tables, the smallest standard deviations are depicted in bold and largest in italic (Tables 6, 7, 8).

Table 6 Standard deviation for one-variable test functions

Table 7 Standard deviation for two-variable test functions

Table 8 Standard deviation for three-variable test functions

Appendix C: Success probability

This Appendix shows the tables of success probability of Algorithm 3 with the termination condition given by Eq. (2) for one, two, and three-variable test functions using the classical optimization routines. In all tables, the largest probability are depicted in bold and lowest in italic. We have performed an average over 100 rounds for each table (Tables 9, 10, 11).

Table 9 Success probability for one-variable test functions

Table 10 Success probability for two-variable test functions

Table 11 Success probability for three-variable test functions