QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM (QAOA)

In this tutorial we show how to (approximately) solve binary combinatorial optimization problems, using the Quantum Approximate Optimization Algorithm (QAOA), as introduced in Ref.[1]. The QAOA algorithm belongs to the class of hybrid quantum algorithms (leveraging both classical as well as quantum compute), that are widely believed to be the working horse for the current NISQ (noisy intermediate-scale quantum) era. In this NISQ era QAOA is also an emerging approach for benchmarking quantum devices and is a prime candidate for demonstrating a practical quantum speed-up on near-term NISQ device [1,4]. To validate our approach we benchmark our results with exact results as obtained from classical QUBO solvers.

We provide a step-by-step walkthrough explaining the QAOA quantum algorithm and show how to build the corresponding parametrized quantum circuit ansatz using the Braket SDK, with simple modular building blocks (that can be re-used for other purposes). We use open-source off-the-shelf scipy optimizers for classical numerical optimization. While we demonstrate our proof-of-concept approach using classical simulators for circuit execution, our code could in principle be run on actual quantum hardware by simply changing the definition of the device object (provided that the gate set used in the ansatz is supported by the device, as is the case here for IonQ; for Rigetti we need to apply one more extra trick as shown below).

BACKGROUND: HYBRID QUANTUM ALGORITHMS

Quantum computers hold the promise to outperform even the most-powerful classical computers on a range of computational problems in (for example) optimization, chemistry, material science and cryptography. The canonical set of quantum algorithms (such as Shor's or Grover's quantum algorithms), however, comes with hardware requirements (such as a large number of quantum gates) that are currently not available with state-of-the-art technology. Specifically, these algorithms are typically believed to be feasible only with fault-tolerance as provided by quantum error correction. In the current noisy intermediate-scale (NISQ) era, near-term quantum computers do not have a large enough number of physical qubits for the implementation of error correction protocols, making this canonical set of quantum algorithms unsuitable for near-term devices. Against this background, the near-term focus has widely shifted to the class of hybrid quantum algorithms that do not require quantum error correction. In these hybrid quantum algorithms, the noisy near-term quantum computers are used as co-processors only, within a larger classical optimization loop, as sketched in the schematic figure below. Here, the undesired effects of noise are suppressed by deliberately limiting the quantum circuits on the quantum processing unit (QPU) to short bursts of the calculation, and the need for long coherence times (as required for the standard set of quantum algorithms) is traded for a classical overhead due to (possibly many) measurement repetitions and (essentially error-free) classical processing.

Variational Quantum Algorithms: Specifically, variational quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) [1] belong to this emerging class of hybrid quantum algorithms. These are widely believed to be promising candidates for the demonstration of a quantum advantage, already with near-term (NISQ) devices in areas such as quantum chemistry [2], condensed matter simulations [3], and discrete optimization tasks [4].

Variational Quantum Computing vs. Deep Learning: The working principle of variational quantum computing is very much reminiscent of training deep neural networks: when you train a neural network, you have an objective function that you want to minimize, typically characterized by the error on your training set. To minimize that error, typically you start out with an initial guess for the weights in your network. The coprocessor, in that case a GPU, takes these weights which define the exact operation to execute and the output of the neural network is computed. This output is then used to calculate the value of your objective function, which in turn is used by the CPU to make an educated guess to update the weights and the cycle continues. Variational quantum algorithms, a specific form of hybrid algorithms, work in the very same way, using parametrized quantum circuits rather than parametrized neural networks and replacing the GPU with a QPU. Here, you start with an initial guess for the parameters that define your circuit, have the QPU execute that circuit, perform measurements to calculate an objective function, pass this value (together with the current values of the parameters) back to the CPU and have this classical CPU update the parameters based on that information.

Of course, coordinating that workflow for quantum computers is much more challenging than in the previous case. Quantum computers are located in specialized laboratory facilities, are typically single threaded, and have special latency requirements. This is exactly the undifferentiated heavy-lifting that Amazon Braket handles for us, such that we can focus on our scientific problem. For the sake of this introductory tutorial, we simply use a classical circuit simulator (that mimic the behavior of a quantum machine) as the device to execute our quantum circuits. Within Amazon Braket, the workflow, however, is exactly the same.

BACKGROUND: QUADRATIC BINARY OPTIMIZATION PROBLEMS

Combinatorial optimization: Combinatorial optimization problems are ubiquitous across many areas of science and application areas. Applications can be found (for example) in logistics, scheduling, planning, and portfolio optimization. In a nutshell combinatorial optimization problems are problems involving a large number of yes/no decisions with each set of decisions yielding a corresponding objective function value, like a cost or profit value. Because of the combinatorial explosion of the solution space with the number of variables, finding good solutions is a daunting task and extremely difficult.

QUBO problems: The QUBO (Quadratic Unconstrained Binary Optimization) model unifies a rich variety of NP-hard combinatorial optimization problems: Famous examples include Quadratic Assignment Problems, Capital Budgeting Problems, Task Allocation Problems and Maximum-Cut Problems. For more details we refer to the excellent review and tutorial on QUBO problems presented in Ref.[5].

Maximum Cut: Among the class of QUBO problems, Maximum Cut (MaxCut) is paradigm combinatorial optimization problem. Given a graph with vertex set and edge set , we seek partition of into two subsets with maximum cut. In short, we have to color every node either blue or red and we score a point whenever an edge connects two nodes with different colors. We then would like to find the solution with the highest score. Applications thereof can be found in, for example, (i) clustering for marketing purposes (segment your customer base into different clusters for targeted marketing) or (ii) portfolio optimization in finance (vertex corresponds to asset, with color referring to sell or buy decisions. Again, the problem in this specific graph coloring problem is that there are possible solutions for nodes (an exponential explosion in possibilities), making it impossible to enumerate all possible candidates for relevant system sizes.

Ising Hamiltonian: Importantly, there is a fundamental correspondence between QUBO problems and Ising problems in physics. Specifically, we can encode the Maximum Cut problem as a minimization problem of an Ising Hamiltonian, where the (classical) cost function reads

with Ising variables and the Ising matrix encoding the weights of the edges. For the sake of this discussion, we ignore potential linear terms and constant offsets (that do not affect the optimal solution anyway). In short, the cost Hamiltonian assigns a number to every bitstring , and we would like to find the lowest number possible. This will be the optimal assignment and solution to our problem.

BACKGROUND: THE QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM

In this tutorial we will try to solve for the optimal classical bitstring using the Quantum Approximate Optimization Algorithm (QAOA). To this end, we first promote the classical spin variables to quantum-mechanical variables (with the Pauli matrix representing the observable corresponding to spin along the coordinate axis in three-dimensional Euclidean space ). This leads to the following quantum mechanical cost Hamiltonian encoding the optimization problem

which can be written as a matrix of size with diagonal elements only corresponding to all possible classical values for the cost function . The ground state of corresponds to the optimal solution of the classical combinatorial problem.

QAOA ansatz: Finding this ground state is generically hard. To approximate this groundstate, QAOA prepares a parametrized ansatz state (corresponding to a parameterized gate sequence), whose parameters are iteratively updated by a classical optimizer in a closed loop. Specifically, QAOA involves a specific ansatz wavefunction parametrized by a parameter family , embedded into a larger classical optimization loop to find the optimal values for these parameters. As shown in Ref.[1], good approximate solutions to the problem class considered here can be found by preparing the variational state

with single qubit rotations induced by , and interactions described by , starting initially from a product of eigenstates, i.e., , with . The family of states is prepared by alternating single-qubit operations with targeted spin-spin interactions generated by the cost Hamiltonian . The depth can be interpreted as a hyperparameter. For layers of QAOA blocks, there are classical parameters to optimize over, since each layer is characterized by just two variational parameters, and . The preparation step outlined above is followed by a measurement in the computational basis, giving a classical string , with which one can evaluate the objective function of the underlying combinatorial problem at hand. Taking several measurements shots one can build the expectation value that we report as the objective function to the classical minimizer (while other choices could be possible as well). Repeating this procedure will provide an optimized string , with the quality of the result improving as the depth of the quantum circuit is increased [1]. In fact, in principle (in the absence of noise and other imperfections), QAOA can reach the global optimum of any cost function in the limit [1], approaching the adiabatic protocol. Thus, in theory the computational power of QAOA increases with , but in practice the number of layers that can be executed without errors on NISQ devices is limited due noise and imperfections.

Optimization: Since we are primarily interested in solving the classical optimization problem, within this routine it is sufficient to keep track of the best classical bitstring. This means that the wavefunction prepared by the quantum circuit has to have some overlap with the optimal solution that we can read out as bitstring in the measurement shots. To this end, in principle (i.e., without any training), we could just sample from a completely uniform state that is prepared in a superposition of all computational basis states, as prepared by applying Hadamard gates to all qubits: . In that case (assuming a single optimal solution) the success probability per shot amounts to . We can then amplify our success chances by just taking many measurement shots. For large systems, however, this approach is not scalable as we would need to take an exponentially increasing number of measurements. That is why we train our circuits, update the parameters, with the goal to increase our success chances to find the optimal bitstring. We can quantify our success chances as follows [6]. For a given wavefunction the probability to find the optimal solution in a single shot is given by

where denotes the optimal bitstring. If we perform repeated measurements, the overall probability for observing this solution at least once is given by

since the term gives the probability of not obtaining in repeated trials. Therefore, to have an overall success chance up to close to 100%, i.e., , the number of required shots has to be

Let us illustrate this results as follows: If we do not know anything and just resort to a uniform superposition , for a small system with qubits we can find the optimal solutions with 80% success probability by taking at least shots. For just qubits, however, this number amounts to , making this naive approach unfeasible. Conversely, if we can train the quantum circuit to obtain , we only need shots to have . Below we will track and illustrate the best classical optimum as our algorithm proceeds towards a local or (ideally) global optimum.

Objective function: Finally, some more details on the definition of the cost function are in order. Following the standard approach [1, 4], QAOA tries to minimize the expectation value , but does not explicitly maximize the success probability [6]. However, a low expectation value for does not necessarily translate to a high success probability , as can be understood from the following example: Consider (for example) a variational state that is a linear combination of low energy excited eigenstates of the cost Hamiltonian other than the ground state . By definition, this state will have a relatively low expectation value while the success probability is zero (as this low energy state does not have any overlap with the ground state). Similarly, a variational state that is a linear combination of the ground state with very high energy eigenstates could have a high success probability , while (at the same time) reporting a high cost value to the classical optimizer. To address this issue, alternative methods for the optimization of the variational parameters have recently been proposed. While for simplicity we follow the majority of the literature and take as cost value that we report to the classical optimizer, here we do mention a potential alternative for future research: One approach is to use the Gibbs objective function, defined as , with the hyperparameter [7]. As compared to the simple expectation value , this definition of the cost value shows stronger rewards for low energy states, thereby increasing the success probability.

IMPORTS and SETUP

For classical benchmarking we will be using the python library pyqubo, as used in our helper script utils_classical. If not already present in your virtual environment, you can install this library simply with pip install pyqubo. Similarly, as seaborn are not expected to be present in the virtual environment by default, we will install them via pip install seaborn. Note the -q to suppress install updates from pip.

PROBLEM SETUP

We consider a graph coloring problem. Given a graph , made of a set vertices (also called nodes) and edges , our goal is to color each node red or blue, then score a point for each node that is next to a node of different color. We strive to find the optimal coloring that scores the largest number of points. To this end, we will address the dual problem of finding the minimum energy of the corresponding Ising Hamiltonian. To get started, we first use the open-source networkx library to visualize the problem graph. Feel free to play with the parameters (for the number of nodes) and (for the number of edges) below to consider other graphs of your choice.

IMPLEMENTATION OF QAOA WITH BRAKET

In this section we load a set of useful helper functions that we will explain in detail below. Specifically in utils_qaoa.py we provide simple building blocks for the core modules of our QAOA algorithm, that is (i) a function called circuit that defines the parametrized ansatz, (ii) a function called objective_function that takes a list of variational parameters as input, and returns the cost associated with those parameters and finally (iii) a function train to run the entire QAOA algorithm for given ansatz. This way we can solve the problem in a clean and modular approach. Here, we show in markdown the definition of the parametrized QAOA circuit. For more details, see the corresponding file utils_qaoa.py.

# function to implement evolution with driver Hamiltonian
def driver(beta, n_qubits):
    """
    Returns circuit for driver Hamiltonian U(Hb, beta)
    """
    # instantiate circuit object
    circ = Circuit()
    
    for qubit in range(n_qubits):
        gate = Circuit().rx(qubit, 2*beta)
        circ.add(gate)
    
    return circ


# helper function for evolution with cost Hamiltonian
def cost_circuit(gamma, n_qubits, ising):
    """
    returns circuit for evolution with cost Hamiltonian
    """
    # instantiate circuit object
    circ = Circuit()

    # get all non-zero entries (edges) from Ising matrix 
    idx = ising.nonzero()
    edges = list(zip(idx[0], idx[1]))
    
    for qubit_pair in edges:
        # get interaction strength
        int_strength = ising[qubit_pair[0], qubit_pair[1]]
        gate = Circuit().zz(qubit_pair[0], qubit_pair[1], angle=2*gamma*int_strength)
        circ.add(gate)

    return circ


# function to build the QAOA circuit with depth p
def circuit(params, n_qubits, ising):
    """
    function to return full QAOA circuit
    """

    # initialize qaoa circuit with first Hadamard layer: for minimization start in |->
    circ = Circuit()
    X_on_all = Circuit().x(range(0, n_qubits))
    circ.add(X_on_all)
    H_on_all = Circuit().h(range(0, n_qubits))
    circ.add(H_on_all)

    # setup two parameter families
    circuit_length = int(len(params) / 2)
    gammas = params[:circuit_length]
    betas = params[circuit_length:]

    # add circuit layers
    for mm in range(circuit_length):
        circ.add(cost_circuit(gammas[mm], n_qubits, ising))
        circ.add(driver(betas[mm], n_qubits))

    return circ

VISUALIZATION OF THE QAOA ANSATZ

Let us first visualize our parametrized QAOA ansatz for a small number of qubits and fixed (i.e., not optimized) parameters. For convenience, the parameters are displayed in the circuit (up to a factor of we have added in our ansatz definition). First we prepare the state , with the superposition state . Following the discussion above, we choose to start out with this state as it is the minimal energy state of the simple driver Hamiltonian . This state preparation is followed by one layer of the QAOA ansatz, consisting of evolution with the cost Hamiltonian by , followed by the single-qubit driving term, . Note that the circuit definition depends on the device object, as the implementation of the ZZ gate depends on the specific gate set supported by the device.

We see that our ansatz produces the expected result for shallow QAOA with . We run one more sanity check for below.

QAOA SIMULATION ON LOCAL SCHROEDINGER SIMULATOR

We are now all set to run some QAOA simulation experiments. First of all, you can play and experiment yourself with the number of qubits . Secondly, you may also experiment with the classical optimizer. Since we are using an off-the-shelf, black-box scipy minimizer (as described in more detail here), you can simply swap between different optimizers by setting the OPT_METHOD parameter below. Some popular options readily available within this library include Nelder-Mead, BFGS and COBYLA. As a precautionary warning, note that the classical optimization step may get stuck in a local optimum, rather than finding the global minimum for our parametrized QAOA ansatz wavefunction. To address this issue, we may run several optimization loops, starting from different random parameter seeds. While this brute-force approach does not provide any guarantee to find the global optimum, from a pragmatic point of view at least it does increase the odds of finding an acceptable solution, at the expense of potentially having to run many more circuits on the simulator or QPU, respectively. Finally, the optimization loop may require the execution of many individual quantum tasks (i.e., single circuit executions for fixed parameters). For example, when choosing the classical Powell optimizer for the graph considered here, we find cycles in the for loop. For the local simulator device chosen here by default this is not an issue, but if you run this algorithm on any QPU you may want to adjust the maxfev parameter to control the maximum allowed number function evaluations (compare comment in the next code block below).

POSTPROCESSING AND COMPARISON OF OUR QAOA RESULTS WITH CLASSICAL RESULTS

In this section we visualize the results we have found with QAOA. Specifically, we display the results found for the variational parameters and for every layer in our QAOA ansatz. Moreover, we show the solution to our graph coloring problem with every node colored either red or blue (recall that there are just two colors since we solve a binary optimization problem). Finally, we compare these results to results found classically using the open-source pyqubo package. Ideally, the two results should agree with each other but this is not necessarily the case for several reasons: First of all, for the original small toy problem we have set up there are several degenerate classical solutions with the same optimal quality. The classical and the QAOA approach may find solutions with different coloring configurations but the same quality (that is energy). Secondly, with QAOA we are not guaranteed to find the optimal solutions. Specifically, the deeper the circuit, the harder the classical optimization problem, and we may get stuck in a local rather than global optimum. One brute-force approach is then to just re-run QAOA with different random initial seeds for the parameters .

Note that QAOA may arrive at a different solution than our classical benchmark code. First of all, the classical optimization routine may get stuck in a local rather than global optimum. To avoid this, more sophisticated optimization strategies may be employed (as proposed for example in Ref.[4]), going beyond the scope of this introductory notebook tutorial. Secondly, even if QAOA arrives at the same classical energy as our classical approach, the coloring may differ since the solution space may be degenerate for the specific example shown here (this means, two different classical bitstrings have the same energy). At minimum, you may find an inverted coloring (by swapping red and blue colors), because of the underlying symmetry.

SUMMARY

In this notebook we have gone through an end-to-end demo on QAOA and its implementation on Amazon Braket. We have built modular core building blocks that may easily adapted to other problems. The QAOA routine is tailored towards solving combinatorial optimization problems such as Maximum Cut [4] and arguably one of the most prominent examples of the emerging class of hybrid, variational algorithms and still very much a field of active research today. For example, as we increase the circuit depth of QAOA, the classical optimization step becomes increasingly difficult (because of the curse of dimensionality as well known in classical machine learning) and may easily get stuck in local sub-optimal solutions. To address this issue some heuristics have already been developed, for example in Ref.[4], but further improvements will arguably be necessary to fully unlock the potential of this approach.

---

REFERENCES

[1] E. Farhi, J. Goldstone, and S. Gutmann, "A Quantum Approximate Optimization Algorithm", arXiv: 1411.4028 (2014).

[2] Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferova, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. Sawaya, et al., "Quantum Chemistry in the Age of Quantum Computing", Chemical reviews 119, 10856 (2019).

[3] A. Smith, M. Kim, F. Pollmann, and J. Knolle, "Simulating quantum many-body dynamics on a current digital quantum computer", npj Quantum Information 5, 1 (2019).

[4] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, "Quantum Approximate Optimization Algorithm: Performance, Mechanism,and Implementation on Near-Term Devices", arXiv: 1812.01041 (2018).

[5] F. Glover, G. Kochenberger, "A Tutorial on Formulating and Using QUBO Models", arXiv:1811.11538 (2018).

[6] P. Vikstal, M. Groenkvist, M. Svensson, M. Andersson, G. Johansson, and G. Ferrini, "Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem", arXiv:1912.10499 (2019).

[7] L. Li, M. Fan, M. Coram, P. Riley, and S. Leichenauer, "Quantum optimization with a novel gibbs objective function and ansatz architecture search", arXiv:1909.07621 (2019).

---

APPENDIX

APPENDIX: Example for Ising Matrix Syntax

In this appendix we provide a small code example to showcase how we obtain all edges with corresponding weights.