# 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:

## 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: