A New Hybrid Classical-quantum Algorithm For Continuous Global Optimization Problems

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.602317331Floudas, C., Gounaris, C., A review of recent advances in global optimization (2009) J. Glob. Opt, 45, pp. 3-38Baritompa, W.P., Bulger, D.W., Wood, G.R., Grover’s quantum algorithm applied to global optimization (2005) SIAM J. Opt, 15, pp. 1170-1184Bulger, D.W., Combining a local search and Grover’s algorithm in black-box global optimisation (2007) J. Opt. Theory Appl, 133, pp. 289-301Liu, Y., Koehler, G.J., Using modifications to Grover’s search algorithm for quantum global optimization (2010) Eur. J. Oper. Res, 207, pp. 620-632Liu, Y., Koehler, G.J., A hybrid method for quantum global optimization (2011) J. Glob. Opt, 52, pp. 607-626Protopopescu, V., Barhen, J., Solving a class of continuous global optimization problems using quantum algorithms (2002) Phys. Lett. A, 296, pp. 9-14Protopopescu, V., Barhen, J., Quantum algorithm for continuous global optimization (2005) Optimization and Control with Applications, , Qi L, (ed), Springer, New York:(1999) A quantum algorithm for finding the minimum, , http://lanl.arxiv.org/-abs/quant-ph/9607014, Dürr, C., Høyer, P.:Boyer, M., Brassard, G., Høyer, P., Tapp, A., Tight bounds on quantum searching (1998) Fortschritte der Physik, 46, pp. 493-506Bulger, D.W., Quantum basin hopping with gradient-based local optimisation (2005) arXiv:quant-ph/0507193Jordan, S.P., Fast quantum algorithm for numerical gradient estimation (2005) Phys. Rev. Lett, 95, p. 050501Grover, L.K., Quantum mechanics helps in searching for a needle in a haystack (1997) Phys. Rev. Lett, 79, pp. 325-328Kowada, L.A.B., Lavor, C., Portugal, R., Figueiredo, C.H., A new quantum algorithm to solve the minimum searching problem (2008) Int. J. Quantum Inf, 6, pp. 427-436Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.V., Strengths and weaknesses of quantum computing (1997) SIAM J. Comput, 26 (5), pp. 1510-1523Zalka, C., Grover’s quantum searching algorithm is optimal (1999) Phys. Rev. A, 60 (4), pp. 2746-2751Hendrix, E.M.T., Klepper, O., On uniform covering, adaptive random search and raspberries (2000) J. Glob. Opt, 18 (2), pp. 143-163(2009) The BOBYQA algorithm for bound constrained optimization without derivatives, , Powell, M.J.DThe NLopt nonlinear-optimization package, , http://ab-initio.mit.edu/nlopt, Johnson, S.G.:Nocedal, J., Updating quasi-Newton matrices with limited storage (1980) Math. Comput, 35 (151), pp. 773-782Liu, D.C., Nocedal, J., On the limited memory bfgs method for large scale optimization (1989) Math. Program, 45 (3), pp. 503-528Dembo, R.S., Steihaug, T., Truncated-newtono algorithms for large-scale unconstrained optimization (1983) Math. Program, 26, pp. 190-212Svanberg, K., A class of globally convergent optimization methods based on conservative convex separable approximations (2002) SIAM J. Opt, 12 (2), pp. 555-573Powell, M.J.D., Direct search algorithms for optimization calculations (1998) Acta Numerica, 7, pp. 287-336Nelder, J.A., Mead, R., A simplex method for function minimization (1965) Comput. J, 7, pp. 308-313Richardson, J.A., Kuester, J.L., Algorithm 454: the complex method for constrained optimization [e4] (1973) Commun. ACM, 16 (8), pp. 487-489Conn, A.R., Gould, N.I.M., Toint, P.L., A globally convergent augmented lagrangian algorithm for optimization with general constraints and simple bounds (1991) SIAM J. Numer. Anal, 28 (2), pp. 545-572Birgin, E.G., Martínez, J.M., Improving ultimate convergence of an augmented Lagrangian method (2008) Opt. Methods Softw, 23 (2), pp. 177-195Thomas Harvey, R., Functional stability analysis of numerical algorithms. Ph.D. Thesis, Austin. UMI Order No (1990) GAX90-3170