Quantum Approximate Optimization Algorithm using Qiskit Runtime primitives and sessions

Background

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid iterative method for solving combinatorial optimization problems. You can learn more about this algorithm here. In this tutorial we demonstrate how to implement the QAOA algorithm using Qiskit Runtime for solving a simple max-cut problem.

In a max-cut problem, we want to partition nodes of a graph in a way that maximizes the number of edges between nodes in differing groups. The desired max-cut partition for the graph below is clear: the 0th-node on the left should be separated from the rest of the nodes on the right by a cut. We will find this answer by applying QAOA by using Qiskit Runtime primitives and sessions.

Authenticate to run code cells Sign in

Reset Copy to clipboard

Output:

Setup

Initialize Runtime service and select backend

First, we need to instantiate the IBM Quantum Runtime service QiskitRuntimeService in order to choose a computational resource on which to execute our QAOA algorithm. In this tutorial, the ibmq_qasm_simlator is chosen.

'ibmq_qasm_simulator'

QAOA Hamiltonian and ansatz

To utilize QAOA algorithm for a max-cut problem we require a Pauli Hamiltonian that encodes the cost in a manner such that the minimum expectation value of the operator corresponds to the maximum number of edges between the nodes in two different groups.

For this simple example, the operator is a linear combination of terms with Z operators on nodes connected by an edge (recall that the 0th qubit is farthest right): $IIIZZ + IIZIZ + IZIIZ + ZIIIZ$. Once the operator is constructed, the ansatz for the QAOA algorithm can easily be built by using the QAOAAnsatz circuit from the Qiskit circuit library.

Authenticate to run code cells Sign in

Reset Copy to clipboard

Output:

The previous image illustrates the ansatz in basic gates for clarity. However, it can be expressed in multiple levels of decomposition by changing the reps argument or by drawing the circuit without the decompose method. For example, the following representation directly shows the QAOA structure with the default reps value, which is reps=1.

Authenticate to run code cells Sign in

Reset Copy to clipboard

Output:

Define the cost function by using Estimator

As with an iterative optimization procedure, we now need to define our cost function over which to minimize. We proceed in an identical manner to the VQE tutorial, computing the expectation value of our Hamiltonian with respect to the parameterized ansatz circuit using the Qiskit Runtime Estimator primitive:

Minimize the cost function

Any classical optimizer can be used to minimize the cost function. On a real quantum system, an optimizer designed for non-smooth cost function landscapes usually does better. Here we use the COBYLA routine from SciPy via the minimize function.

Because we are iteratively executing many calls to Runtime, we make use of a Session in order to execute all calls within a single block. Moreover, for QAOA, the solution is encoded in the output distribution of the ansatz circuit bound with the optimal parameters from the minimization. Therefore, we will need a Sampler primitive as well, and will instantiate it with the same Session.

We now set an initial set of random parameters:

and run our minimization routine:

In the end, we have a result in the standard SciPy OptimizeResult format.

 message: Optimization terminated successfully.
 success: True
  status: 1
     fun: -3.1462000000000003
       x: [ 2.072e+00  1.878e+00  5.420e+00  3.549e+00]
    nfev: 68
   maxcv: 0.0

Solution to max-cut

The solution vector of parameter angles (x), when plugged into the ansatz circuit, yields the graph partitioning that we were looking for.

For small problem instances, the solution can be visually obtained:

Authenticate to run code cells Sign in

Reset Copy to clipboard

Output:

The most probable bit-strings, up to finite-sampling deviations, encode the solution. Here we see that 00001 and 11110 are found, and are indeed correct. There are two solutions because the labeling of the two partitions with '0' or '1' is arbitrary.

'0.11.3'

'0.25.0'