A study of the performance of classical minimizers in the Quantum Approximate Optimization Algorithm

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) was proposed as a way of finding good, approximate solutions to hard combinatorial optimization problems. QAOA uses a hybrid approach. A parametrized quantum state is repeatedly prepared and measured on a quantum computer to estimate its average energy. Then, a classical optimizer, running in a classical computer, uses such information to decide on the new parameters that are then provided to the quantum computer. This process is iterated until some convergence criteria are met. Theoretically, almost all classical minimizers can be used in the hybrid scheme. However, their behaviour can vary greatly in both the quality of the final solution and the time they take to find it.

In this work, we study the performance of twelve different classical optimizers when used with QAOA to solve the maximum cut problem in graphs. We conduct a thorough set of tests on a quantum simulator both, with and without noise, and present results that show that some optimizers can be hundreds of times more efficient than others in some cases.

Introduction

Quantum computing [1] is a computational paradigm in which subatomic particle properties such as superposition, entanglement and interference are exploited to obtain algorithms which offer speed-ups over classical algorithms. For instance, Shor’s algorithm [2] is a quantum method that can factor an integer in time which is polynomial in the number of bits of the input while the best classical algorithm that we currently have is superpolynomial, and Grover’s algorithm [3] and some quantum walks [4], [5] attain a quadratic speed-up in the black-box model over any possible classical algorithm for searching an element in an unsorted list.

A fruitful topic of research has been the use of quantum computing for solving combinatorial optimization problems. One of the most popular approaches has been that of quantum adiabatic computing [6], [7]. In this model, a quantum system is initialized to a certain, well-known state and then it is made to evolve following a slowly changing Hamiltonian until it reaches the ground state of another Hamiltonian that codes the solution to our problem. Although this model is equivalent to the paradigm of quantum circuits and it is, thus, universal, its most popular incarnation has been through the use of the restricted version called quantum annealing [8], for instance in D-Wave’s quantum computers [9].

The Quantum Approximate Optimization Algorithm (QAOA) [10] can be seen as a discretization of quantum adiabatic computing in which a target Hamiltonian and a mixer Hamiltonian are used in alternate steps to drive the evolution of the system to a (ground) state that encodes a solution to the optimization problem under study. Since its introduction, the properties of QAOA have been (and still are) the subject of intense study [11], [12], [13], [14], [15], [16], [17] and it has been applied to several different optimization problems [18], [19], [20], [21].

QAOA follows a hybrid classical-quantum scheme. The classical computer is used to determine the optimal values in a parametrized quantum state that has a high overlap with (a good approximation to) the solution of our optimization problem. Then, a quantum computer is used to prepare that quantum state with the optimal parameters found by the classical algorithm. When that state is measured, a good solution is found with high probability.

Theoretically, the optimal parameters for the quantum state can be obtained efficiently with a classical algorithm for some problems [10]. However, although the exact method has asymptotical polynomial complexity, in practice its running time can be rather large. Thus, an iterative approach is usually adopted instead. The classical computer starts with a guess of the optimal parameters and uses the quantum computer to evaluate the expected value of the quantum state for those parameters. Then, a classical minimizer or maximizer is used to obtain the optimal values. Throughout this process, the quantum computer is used as a black-box capable of providing (estimations of) the expected values of the quantum state for different values of the parameters.

Although QAOA has been the subject of many research papers, not so much attention has been paid to the influence of the choice of classical optimizer in the efficacy and efficiency of the method and, to a prospective user of the algorithm it can be difficult to select the most appropriate minimizer among the many existing ones. In this work, we focus exactly on that problem and we study the performance of twelve different classical optimizers when used together with QAOA to solve the maximum cut problem in graphs, with the aim of providing a guide to help in choosing the best minimizer to use with QAOA. We conduct a series of numerical experiments in a quantum simulator, both with and without noise, and analyse the results in terms of quality of the solution and of the computation time needed to achieve it. This shows that some optimizers can be hundreds of times faster than others while attaining approximations to the solution of similar quality, so the choice of the classical optimizer should be a key factor when using QAOA. Partial studies of the performance of optimizers for QAOA have been conducted before, but only with a fraction of the twelve methods that we examine in this work (for instance, in [22] and [23] three optimizers are studied, while five are considered in [24]).

The rest of the paper is organized as follows. In Section 2 we present the mathematical formulation of QAOA and we show how approximate solutions to NP-hard problems such as Max-Cut can be found with it and in Section 3 we derive the analytical expression of the expected energy for some of the cases we study in this paper. In Section 4, we introduce the classical optimizers that we have used in under study and present some of their main properties. In Section 5 we describe the settings of our experiments and present and analyse the results we have obtained. Finally, in Section 6 we raise some conclusions and propose ideas for future work.