Learning Home Catalog Composer
Learning
Home Catalog Composer
Tutorials

Solve utility-scale quantum optimization problems

Estimated QPU usage: 8 minutes (tested on IBM Sherbrooke)

This tutorial demonstrates how to implement the Quantum Approximate Optimization Algorithm (QAOA) – a hybrid (quantum-classical) iterative method – within the context of Qiskit patterns. You will first solve the Maximum-Cut (or Max-Cut) problem for a small graph and then learn how to execute it at utility scale. All the hardware executions in the notebook should run within the time limit for the freely-accessible Open Plan.

The Max-Cut problem is an optimization problem that is hard to solve (more specifically, it is an NP-hard problem) with a number of different applications in clustering, network science, and statistical physics. This tutorial considers a graph of nodes connected by vertices, and aims to partition it into separate graphs such that they are both as large as possible. Put another way, the goal of this problem is to partition the nodes of a graph into two sets such that the number of edges traversed by this cut is maximized.

Illustration of a max-cut problem

Requirements

Before starting this tutorial, be sure you have the following installed:

  • Qiskit SDK v1.0 or later, with visualization support ( pip install 'qiskit[visualization]' )
  • Qiskit Runtime 0.22 or later (pip install qiskit-ibm-runtime)
  • Rustworkx graph library (pip install rustworkx)

Part 1: Small-scale QAOA

The first part of this tutorial uses a small-scale Max-Cut problem to illustrate the steps to solve an optimization problem using a quantum computer.

To give some context before mapping this problem to a quantum algorithm, you can better understand how the Max-Cut problem becomes a classical combinatorial optimization problem by first considering the minimization of a function f(x)f(x)

minx{0,1}nf(x),\min_{x\in \{0, 1\}^n}f(x),

where the input xx is a vector whose components correspond to each node of a graph. Then, constrain each of these components to be either 00 or 11 (which represent being included or not included in the cut). This small-scale example case uses a graph with n=5n=5 nodes.

You could write a function of a pair of nodes i,ji,j which indicates whether the corresponding edge (i,j)(i,j) is in the cut. For example, the function xi+xj2xixjx_i + x_j - 2 x_i x_j is 1 only if one of either xix_i or xjx_j are 1 (which means that the edge is in the cut) and zero otherwise. The problem of maximizing the edges in the cut can be formulated as

maxx{0,1}n(i,j)xi+xj2xixj,\max_{x\in \{0, 1\}^n} \sum_{(i,j)} x_i + x_j - 2 x_i x_j,

which can be rewritten as a minimization of the form

minx{0,1}n(i,j)2xixjxixj.\min_{x\in \{0, 1\}^n} \sum_{(i,j)} 2 x_i x_j - x_i - x_j.

The minimum of f(x)f(x) in this case is when the number of edges traversed by the cut is maximal. As you can see, there is nothing relating to quantum computing yet. You need to reformulate this problem into something that a quantum computer can understand.

Initialize your problem by creating a graph with n=5n=5 nodes.

Copy to clipboard

Output:

Step 1. Map classical inputs to a quantum problem

The first step of the pattern is to map the classical problem (graph) into quantum circuits and operators. To do this, there are three main steps to take:

  1. Utilize a series of mathematical reformulations, to represent this problem using the Quadratic Unconstrained Binary Optimization (QUBO) problems notation.
  2. Rewrite the optimization problem as a Hamiltonian for which the ground state corresponds to the solution which minimizes the cost function.
  3. Create a quantum circuit which will prepare the ground state of this Hamiltonian via a process similar to quantum annealing.

Note: In the QAOA methodology, you ultimately want to have an operator (Hamiltonian) that represents the cost function of our hybrid algorithm, as well as a parametrized circuit (Ansatz) that represents quantum states with candidate solutions to the problem. You can sample from these candidate states and then evaluate them using the cost function.

Graph → optimization problem

The first step of the mapping is a notation change, The following expresses the problem in QUBO notation:

minx{0,1}nxTQx,\min_{x\in \{0, 1\}^n}x^T Q x,

where QQ is a n×nn\times n matrix of real numbers, nn corresponds to the number of nodes in your graph, xx is the vector of binary variables introduced above, and xTx^T indicates the transpose of the vector xx.

Maximize -2*x_0*x_1 - 2*x_0*x_2 - 2*x_0*x_4 - 2*x_1*x_2 - 2*x_2*x_3 - 2*x_3*x_4 + 3*x_0 + 2*x_1 + 3*x_2 + 2*x_3 + 2*x_4 Subject to No constraints Binary variables (5) x_0 x_1 x_2 x_3 x_4

Optimization problem → Hamiltonian

You can then reformulate the QUBO problem as a Hamiltonian (here, a matrix that represents the energy of a system):

HC=ijQijZiZj+ibiZi.H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_iZ_i.

Reformulation steps from the QAOA problem to the Hamiltonian

To demonstrate how the QAOA problem can be rewritten in this way, first replace the binary variables xix_i to a new set of variables zi{1,1}z_i\in\{-1, 1\} via

xi=1zi2.x_i = \frac{1-z_i}{2}.

Here you can see that if xix_i is 00, then ziz_i must be 11. When the xix_i's are substituted for the ziz_i's in the optimization problem (xTQxx^TQx), an equivalent formulation can be obtained.

xTQx=ijQijxixj=14ijQij(1zi)(1zj)=14ijQijzizj14ij(Qij+Qji)zi+n24.x^TQx=\sum_{ij}Q_{ij}x_ix_j \\ =\frac{1}{4}\sum_{ij}Q_{ij}(1-z_i)(1-z_j) \\=\frac{1}{4}\sum_{ij}Q_{ij}z_iz_j-\frac{1}{4}\sum_{ij}(Q_{ij}+Q_{ji})z_i + \frac{n^2}{4}.

Now if we define bi=j(Qij+Qji)b_i=-\sum_{j}(Q_{ij}+Q_{ji}), remove the prefactor, and the constant n2n^2 term, we arrive at the two equivalent formulations of the same optimization problem.

minx{0,1}nxTQxminz{1,1}nzTQz+bTz\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz

Here, bb depends on QQ. Note that to obtain zTQz+bTzz^TQz + b^Tz we dropped the factor of 1/4 and a constant offset of n2n^2 which do not play a role in the optimization.

Now, to obtain a quantum formulation of the problem, promote the ziz_i variables to a Pauli ZZ matrix, such as a 2×22\times 2 matrix of the form

Zi=(1001).Z_i = \begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix}.

When you substitute these matrices in the optimization problem above, you obtain the following Hamiltonian

HC=ijQijZiZj+ibiZi.H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_iZ_i.

Also recall that the ZZ matrices are embedded in the quantum computer's computational space, i.e., a Hilbert space of size 2n×2n2^n\times 2^n. Therefore, you should understand terms such as ZiZjZ_iZ_j as the tensor product ZiZjZ_i\otimes Z_j embedded in the 2n×2n2^n\times 2^n Hilbert space. For example, in a problem with five decision variables the term Z1Z3Z_1Z_3 is understood to mean IZ3IZ1II\otimes Z_3\otimes I\otimes Z_1\otimes I where II is the 2×22\times 2 identity matrix.

This Hamiltonian is called the cost function Hamiltonian. It has the property that its ground state corresponds to the solution that minimizes the cost function f(x)f(x). Therefore, to solve your optimization problem you now need to prepare the ground state of HCH_C (or a state with a high overlap with it) on the quantum computer. Then, sampling from this state will, with a high probability, yield the solution to min f(x)min~f(x).

Copy to clipboard

Output:

Cost Function Hamiltonian: SparsePauliOp(['IIIZZ', 'IIZIZ', 'ZIIIZ', 'IIZZI', 'IZZII', 'ZZIII'],
              coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j])

Hamiltonian → quantum circuit

The Hamiltonian HcH_c contains the quantum definition of your problem. Now you can create a quantum circuit that will help sample good solutions from the quantum computer. The QAOA is inspired by quantum annealing and applies alternating layers of operators in the quantum circuit.

The general idea is to start in the ground state of a known system, Hn0H^{\otimes n}|0\rangle above, and then steer the system into the ground state of the cost operator that you are interested in. This is done by applying the operators exp{iγkHC}\exp\{-i\gamma_k H_C\} and exp{iβkHm}\exp\{-i\beta_k H_m\} with angles γ1,...,γp\gamma_1,...,\gamma_p and β1,...,βp \beta_1,...,\beta_p~.

The quantum circuit that you generate is parametrized by γi\gamma_i and βi\beta_i, so you can try out different values of γi\gamma_i and βi\beta_i and sample from the resulting state.

Circuit diagram with QAOA layers

In this case, you will try an example with one QAOA layer that contains two parameters: γ1\gamma_1 and β1\beta_1.

Copy to clipboard

Output:

Copy to clipboard

Output:

ParameterView([ParameterVectorElement(β[0]), ParameterVectorElement(β[1]), ParameterVectorElement(γ[0]), ParameterVectorElement(γ[1])])

Step 2. Optimize circuits for quantum hardware execution

The circuit above contains a series of abstractions useful to think about quantum algorithms, but not possible to run on the hardware. To be able to run on a QPU, the circuit needs to undergo a series of operations that make up the transpilation or circuit optimization step of the pattern.

The Qiskit library offers a series of transpilation passes that cater to a wide range of circuit transformations. You need to make sure that your circuit is optimized for your purpose.

Transpilation may involves several steps, such as:

  • Initial mapping of the qubits in the circuit (such as decision variables) to physical qubits on the device.
  • Unrolling of the instructions in the quantum circuit to the hardware-native instructions that the backend understands.
  • Routing of any qubits in the circuit that interact to physical qubits that are adjacent with one another.
  • Error suppression by adding single-qubit gates to suppress noise with dynamical decoupling.

More information about transpilation is available in our documentation.

The following code transforms and optimizes the abstract circuit into a format that is ready for execution on one of devices accessible through the cloud using the Qiskit IBM Runtime service.

Copy to clipboard

Output:

<IBMBackend('ibm_kyiv')>

Step 3. Execute using Qiskit primitives

In the QAOA workflow, the optimal QAOA parameters are found in an iterative optimization loop, which runs a series of circuit evaluations and uses a classical optimizer to find the optimal βk\beta_k and γk\gamma_k parameters. This execution loop is executed via the following steps:

  1. Define the initial parameters
  2. Instantiate a new Session containing the optimization loop and the primitive used to sample the circuit
  3. Once an optimal set of parameters is found, execute the circuit a final time to obtain a final distribution which will be used in the post-process step.

Define circuit with initial parameters

We start with arbitrary chosen parameters.

Copy to clipboard

No output produced

Define backend and execution primitive

Use the Qiskit Runtime primitives to interact with IBM® backends. The two primitives are Sampler and Estimator, and the choice of primitive depends on what type of measurement you want to run on the quantum computer. For the minimization of HcH_c, use the Estimator since the measurement of the cost function is simply the expectation value of Hc\langle H_c \rangle.

Run

The primitives offer a variety of execution modes to schedule workloads on quantum devices, and a QAOA workflow runs iteratively in a session.

Illustration showing the behavior of Single job, Batch, and Session runtime modes.

You can plug the sampler-based cost function into the SciPy minimizing routine to find the optimal parameters.

Copy to clipboard

No output produced

Copy to clipboard

Output:

 message: Optimization terminated successfully.
 success: True
  status: 1
     fun: -1.9252549900345741
       x: [ 3.271e+00  2.874e+00  2.641e+00  9.339e-01]
    nfev: 35
   maxcv: 0.0

The optimizer was able to reduce the cost and find better parameters for the circuit.

Copy to clipboard

Output: