Learning Home Catalog Composer
Learning
Home Catalog Composer Return to tutorial
Learning
Quantum approximate optimization algorithm
BackgroundRequirementsSetupStep 1: Map classical inputs to a quantum problemStep 2: Optimize problem for quantum execution.ISA CircuitISA ObservablesStep 3: Execute using Qiskit Primitives.Step 4: Post-process, return result in classical format.

Quantum approximate optimization algorithm

Category

Workflow example

Topics

Scheduling
Download notebook Download notebook

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.

Requirements

Before starting this tutorial, ensure that you have the following installed:

  • Qiskit SDK 1.0 or later, with visualization support (pip install 'qiskit[visualization]')
  • Qiskit Runtime (pip install qiskit-ibm-runtime) 0.22 or later
  • SciPy (python -m pip install scipy)
  • rustworkx (pip install rustworkx)

Setup

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

'ibm_cairo'

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.

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

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+ZIIIZIIIZZ + 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.

Run
The ability to run code cells is currently disabled.
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.

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

Step 2: Optimize problem for quantum execution.

To reduce the total job execution time, V2 primitives only accept circuits (ansatz) and observables (Hamiltonian) that conforms to the instructions and connectivity supported by the target system (referred to as instruction set architecture (ISA) circuits and observables).

ISA Circuit

We can schedule a series of qiskit.transpiler passes to optimize our circuit for a selected backend and make it compatible with the instruction set architecture (ISA) of the backend. This can be easily done using a preset pass manager from qiskit.transpiler and its optimization_level parameter.

  • optimization_level: The lowest optimization level just 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.
Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

ISA Observables

Similarly, we need to transform the Hamiltonian to make it backend compatible before running jobs with Runtime Estimator V2. We can perform the transformation using the apply_layout the method of SparsePauliOp object.

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

SparsePauliOp(['IZIIIIIZIIIIIIIIIIIIIIIIIII', 'ZZIIIIIIIIIIIIIIIIIIIIIIIII', 'IZIIZIIIIIIIIIIIIIIIIIIIIII', 'IZZIIIIIIIIIIIIIIIIIIIIIIII'],
              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 Estimator primitive:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

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 Session 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.

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

We can set an initial set of random parameters:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

We can run our minimization routine:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

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

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

 message: Optimization terminated successfully.
 success: True
  status: 1
     fun: -2.3267393689475724
       x: [ 1.199e+00  4.359e-01  3.994e+00  1.558e+00]
    nfev: 51
   maxcv: 0.0

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

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

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

No output produced

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

Run
The ability to run code cells is currently disabled.
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.

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

'0.23.0'
Run
The ability to run code cells is currently disabled.
Copy to clipboard

Output:

'1.0.2'