# Quantum approximate optimization algorithm

## Background

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid iterative method for solving combinatorial optimization problems. 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 following graph 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.

## Setup

Output:

Output:

```
'ibm_osaka'
```

## Step 1: Map classical inputs to a quantum problem

To demonstrate max-cut, we'll create a graph using the rustworkx library, and create 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.

Output:

For this simple example, the operator is a linear combination of terms with

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

Output:

## Step 2: Optimize problem for quantum execution.

We can schedule a series of qiskit.transpiler passes to optimize our circuit for a selected backend. This includes a few components:

optimization_level : The lowest optimization level does the bare minimum needed to get the circuit running on the device; it maps the circuit qubits to the device qubits and adds swap gates to allow all 2-qubit operations. The highest optimization level is much smarter and uses lots of tricks to reduce the overall gate count. Since multi-qubit gates have high error rates and qubits decohere over time, the shorter circuits should give better results.- Dynamical Decoupling: We can apply a sequence of gates to idling qubits. This cancels out some unwanted interactions with the environment.

Output:

Output:

We can also use

Output:

```
SparsePauliOp(['IIIIIIIIIIIIIIZIIIIZIIIIIII', 'IIIIIIIIIIIIIIZIZIIIIIIIIII', 'IIIIIIIIIIIZIIZIIIIIIIIIIII', 'IIIIIIIIIIIIIZZIIIIIIIIIIII'],
coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j])
```

## Step 3: Execute using Qiskit Primitives.

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 Variational Quantum Eigensolver tutorial, computing the expectation value of our Hamiltonian with respect to the parameterized ansatz circuit using the Qiskit Runtime

Output:

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 through the minimize function.

Because we are iteratively executing many calls to Runtime, we use a

Output:

We can set an initial set of random parameters:

Output:

We can run our minimization routine:

Output:

In the end, we have a result in the standard SciPy

Output:

```
message: Optimization terminated successfully.
success: True
status: 1
fun: -2.5309634084695976
x: [ 1.982e+00 6.601e+00 5.917e+00 2.669e+00]
nfev: 51
maxcv: 0.0
```

## Step 4: Post-process, return result in classical format.

The solution vector of parameter angles (

Output: