Skip to content

Solving MaxCut with QAOA

This tutorial shows how to solve the maximum cut (MaxCut) combinatorial optimization problem on a graph using the Quantum Approximate Optimization Algorithm (QAOA), first introduced by Farhi et al. in 2014 1.

Given an arbitrary graph, the MaxCut problem consists in finding a graph cut which partitions the nodes into two disjoint sets, such that the number of edges in the cut is maximized. This is a very common combinatorial optimization problem known to be computationally hard (NP-hard).

The graph used for this tutorial is an unweighted graph randomly generated using the networkx library with a certain probability \(p\) of having an edge between two arbitrary nodes (known as Erdős–Rényi graph).

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import random

# ensure reproducibility
seed = 42
np.random.seed(seed)
random.seed(seed)

# Create random graph
n_nodes = 4
edge_prob = 0.8
graph = nx.gnp_random_graph(n_nodes, edge_prob)

nx.draw(graph)
2025-02-07T10:22:27.962143 image/svg+xml Matplotlib v3.10.0, https://matplotlib.org/

The goal of the MaxCut algorithm is to maximize the following cost function:

\[\mathcal{C}(p) = \sum_{\alpha}^m \mathcal{C}_{\alpha}(p)\]

where \(p\) is a given cut of the graph, \(\alpha\) is an index over the edges and \(\mathcal{C}_{\alpha}(p)\) is written such that if the nodes connected by the \(\alpha\) edge are in the same set, it returns \(0\), otherwise it returns \(1\). We will represent a cut \(p\) as a bitstring of length \(N\), where \(N\) is the number of nodes, and where the bit in position \(i\) shows to which partition node \(i\) belongs. We assign value 0 to one of the partitions defined by the cut and 1 to the other. Since this choice is arbitrary, every cut is represented by two bitstrings, e.g. "0011" and "1100" are equivalent.

Since in this tutorial we are only dealing with small graphs, we can find the maximum cut by brute force to make sure QAOA works as intended.

# Function to calculate the cost associated with a cut
def calculate_cost(cut: str, graph: nx.graph) -> float:
    """Returns the cost of a given cut (represented by a bitstring)"""
    cost = 0
    for edge in graph.edges():
        (i, j) = edge
        if cut[i] != cut[j]:
            cost += 1
    return cost


# Function to get a binary representation of an int
get_binary = lambda x, n: format(x, "b").zfill(n)

# List of all possible cuts
all_possible_cuts = [bin(k)[2:].rjust(n_nodes, "0") for k in range(2**n_nodes)]

# List with the costs associated to each cut
all_costs = [calculate_cost(cut, graph) for cut in all_possible_cuts]

# Get the maximum cost
maxcost = max(all_costs)

# Get all cuts that correspond to the maximum cost
maxcuts = [get_binary(i, n_nodes) for i, j in enumerate(all_costs) if j == maxcost]
print(f"The maximum cut is represented by the bitstrings {maxcuts}, with a cost of {maxcost}")
The maximum cut is represented by the bitstrings ['0011', '0101', '0110', '1001', '1010', '1100'], with a cost of 4

The QAOA quantum circuit

The Max-Cut problem can be solved by using the QAOA algorithm. QAOA belongs to the class of Variational Quantum Algorithms (VQAs), which means that its quantum circuit contains a certain number of parametrized quantum gates that need to be optimized with a classical optimizer. The QAOA circuit is composed of two operators:

  • The cost operator \(U_c\): a circuit generated by the cost Hamiltonian which encodes the cost function described above into a quantum circuit. The solution to the optimization problem is encoded in the ground state of the cost Hamiltonian \(H_c\). The cost operator is simply the evolution of the cost Hamiltonian parametrized by a variational parameter \(\gamma\) so that \(U_c = e^{i\gamma H_c}.\)
  • The mixing operator \(U_b\): a simple set of single-qubit rotations with adjustable angles which are tuned during the classical optimization loop to minimize the cost

The cost Hamiltonian of the MaxCut problem can be written as:

\[H_c = \frac12 \sum_{\langle i,j\rangle} (\mathbb{1} - Z_iZ_j)\]

where \(\langle i,j\rangle\) represents the edge between nodes \(i\) and \(j\). The solution of the MaxCut problem is encoded in the ground state of the above Hamiltonian.

The QAOA quantum circuit consists of a number of layers, each layer containing a cost and a mixing operator. Below, the QAOA quantum circuit is defined using qadence operations. First, a layer of Hadamard gates is applied to all qubits to prepare the initial state \(|+\rangle ^{\otimes n}\). The cost operator of each layer can be built "manually", implementing the \(e^{iZZ\gamma}\) terms with CNOTs and a \(\rm{RZ}(2\gamma)\) rotation, or it can also be automatically decomposed into digital single and two-qubits operations via the .digital_decomposition() method. The decomposition is exact since the Hamiltonian generator is diagonal.

from qadence import tag, kron, chain, RX, RZ, Z, H, CNOT, I, add
from qadence import HamEvo, QuantumCircuit, Parameter

n_qubits = graph.number_of_nodes()
n_edges = graph.number_of_edges()
n_layers = 6

# Generate the cost Hamiltonian
zz_ops = add(Z(edge[0]) @ Z(edge[1]) for edge in graph.edges)
cost_ham = 0.5 * (n_edges * kron(I(i) for i in range(n_qubits)) - zz_ops)


# QAOA circuit
def build_qaoa_circuit(n_qubits, n_layers, graph):
    layers = []
    # Layer of Hadamards
    initial_layer = kron(H(i) for i in range(n_qubits))
    layers.append(initial_layer)
    for layer in range(n_layers):

        # cost layer with digital decomposition
        # cost_layer = HamEvo(cost_ham, f"g{layer}").digital_decomposition(approximation="basic")
        cost_layer = []
        for edge in graph.edges():
            (q0, q1) = edge
            zz_term = chain(
                CNOT(q0, q1),
                RZ(q1, Parameter(f"g{layer}")),
                CNOT(q0, q1),
            )
            cost_layer.append(zz_term)
        cost_layer = chain(*cost_layer)
        cost_layer = tag(cost_layer, "cost")

        # mixing layer with single qubit rotations
        mixing_layer = kron(RX(i, f"b{layer}") for i in range(n_qubits))
        mixing_layer = tag(mixing_layer, "mixing")

        # putting all together in a single ChainBlock
        layers.append(chain(cost_layer, mixing_layer))

    final_b = chain(*layers)
    return QuantumCircuit(n_qubits, final_b)


circuit = build_qaoa_circuit(n_qubits, n_layers, graph)

# Print a single layer of the circuit
%3 cluster_6640f9c973cc4e9886a1d81a71eea50a mixing cluster_c5c0d3c20953417e9963178210134adb cost 06ca380186aa41a0b78b8dad9131ab72 0 30bf0a421a4d426eab3577e2f3c3b34d H 06ca380186aa41a0b78b8dad9131ab72--30bf0a421a4d426eab3577e2f3c3b34d 29b782df7c41461e8ae841ea94389b7e 1 49b9c4197e064847b0fb66b42b9e5131 30bf0a421a4d426eab3577e2f3c3b34d--49b9c4197e064847b0fb66b42b9e5131 1e0d4f80fd4c4838850be060773bb807 49b9c4197e064847b0fb66b42b9e5131--1e0d4f80fd4c4838850be060773bb807 1dd1f0c803454fd79b790231aef25b08 1e0d4f80fd4c4838850be060773bb807--1dd1f0c803454fd79b790231aef25b08 86227fcd81cc4db7b97055495a3480b6 1dd1f0c803454fd79b790231aef25b08--86227fcd81cc4db7b97055495a3480b6 401ddb69f4f74400a6cb0ba928d667e9 86227fcd81cc4db7b97055495a3480b6--401ddb69f4f74400a6cb0ba928d667e9 38e9778d34014599a2b7a9fbd2d8926a 401ddb69f4f74400a6cb0ba928d667e9--38e9778d34014599a2b7a9fbd2d8926a eb3f189773fb4a15ab9ad7f447f6ef48 38e9778d34014599a2b7a9fbd2d8926a--eb3f189773fb4a15ab9ad7f447f6ef48 59b57c5f6fc845a98eca671d2db549a2 eb3f189773fb4a15ab9ad7f447f6ef48--59b57c5f6fc845a98eca671d2db549a2 a232a757eb0b4f919c55d65fda3875fa 59b57c5f6fc845a98eca671d2db549a2--a232a757eb0b4f919c55d65fda3875fa 4ca16117f4a64f6c931dc670c15a74bb a232a757eb0b4f919c55d65fda3875fa--4ca16117f4a64f6c931dc670c15a74bb c1ac6ffa4f0b4a85b89390b25c75f5b4 4ca16117f4a64f6c931dc670c15a74bb--c1ac6ffa4f0b4a85b89390b25c75f5b4 6d3c9a6e713f4a83bd75c63fea6e0b41 c1ac6ffa4f0b4a85b89390b25c75f5b4--6d3c9a6e713f4a83bd75c63fea6e0b41 16cb8dd8fe2f49579913f339032e0ca4 6d3c9a6e713f4a83bd75c63fea6e0b41--16cb8dd8fe2f49579913f339032e0ca4 e5ad213d76c947009a828ee30edfa443 16cb8dd8fe2f49579913f339032e0ca4--e5ad213d76c947009a828ee30edfa443 5df66392743b4b31bc83cf4e26f3e3cd e5ad213d76c947009a828ee30edfa443--5df66392743b4b31bc83cf4e26f3e3cd 32ea710289824718b87c92a1d5fa28c4 5df66392743b4b31bc83cf4e26f3e3cd--32ea710289824718b87c92a1d5fa28c4 6b662d14153c42dfb35f9ca945e396fd 32ea710289824718b87c92a1d5fa28c4--6b662d14153c42dfb35f9ca945e396fd d1c5b58e08dc49efb7b346f56ede96fc 6b662d14153c42dfb35f9ca945e396fd--d1c5b58e08dc49efb7b346f56ede96fc c34d5d7683264db3a0f45c99ac572d0c RX(b0) d1c5b58e08dc49efb7b346f56ede96fc--c34d5d7683264db3a0f45c99ac572d0c 1b8b9f8564174602ad0deebfffffbf8f c34d5d7683264db3a0f45c99ac572d0c--1b8b9f8564174602ad0deebfffffbf8f 2f9fda1034b34e14819d50671ecbc497 7cfb233f963c4b8f8dd6a5e637d93221 H 29b782df7c41461e8ae841ea94389b7e--7cfb233f963c4b8f8dd6a5e637d93221 6ae54e3f68d342f18e946bac613e1c0c 2 d10e62e11eef4aea8d2035ad74a256fe X 7cfb233f963c4b8f8dd6a5e637d93221--d10e62e11eef4aea8d2035ad74a256fe d10e62e11eef4aea8d2035ad74a256fe--49b9c4197e064847b0fb66b42b9e5131 e3e13918a82e40bf871d9a02b31a8767 RZ(g0) d10e62e11eef4aea8d2035ad74a256fe--e3e13918a82e40bf871d9a02b31a8767 25a8aeb5dbb8480ca9a5261694f2583b X e3e13918a82e40bf871d9a02b31a8767--25a8aeb5dbb8480ca9a5261694f2583b 25a8aeb5dbb8480ca9a5261694f2583b--1dd1f0c803454fd79b790231aef25b08 84f42b5d363b43b884265ebdd14c2ff3 25a8aeb5dbb8480ca9a5261694f2583b--84f42b5d363b43b884265ebdd14c2ff3 bb52bd44c2724834baef7e04746fa104 84f42b5d363b43b884265ebdd14c2ff3--bb52bd44c2724834baef7e04746fa104 87b3cd81ed0c4921a1b04023c77a1def bb52bd44c2724834baef7e04746fa104--87b3cd81ed0c4921a1b04023c77a1def 848925a062de448388597390b664b0f4 87b3cd81ed0c4921a1b04023c77a1def--848925a062de448388597390b664b0f4 dea1d94c998c475bb65af285d97bfc9d 848925a062de448388597390b664b0f4--dea1d94c998c475bb65af285d97bfc9d d837e28a42154ed7b4d8f11ae56cd759 dea1d94c998c475bb65af285d97bfc9d--d837e28a42154ed7b4d8f11ae56cd759 c9b3c97d17bd428c96131b417540d430 d837e28a42154ed7b4d8f11ae56cd759--c9b3c97d17bd428c96131b417540d430 1c8775c2cd6947daaa8822190612a8d5 c9b3c97d17bd428c96131b417540d430--1c8775c2cd6947daaa8822190612a8d5 94e3d9be7ba545c48e2919dab4180168 1c8775c2cd6947daaa8822190612a8d5--94e3d9be7ba545c48e2919dab4180168 209150390a19433cb2a6e4b5d363e766 94e3d9be7ba545c48e2919dab4180168--209150390a19433cb2a6e4b5d363e766 109e7c32d6424e48b15f4ac17a5c9024 209150390a19433cb2a6e4b5d363e766--109e7c32d6424e48b15f4ac17a5c9024 222f72492d94483dbd51266a2dc5590f 109e7c32d6424e48b15f4ac17a5c9024--222f72492d94483dbd51266a2dc5590f be7b29b6703a44b38543226face24360 222f72492d94483dbd51266a2dc5590f--be7b29b6703a44b38543226face24360 ef6e1ae7505f420e90f279c72388daf6 be7b29b6703a44b38543226face24360--ef6e1ae7505f420e90f279c72388daf6 f708d0c1a8cb47938304b6446d45adfd ef6e1ae7505f420e90f279c72388daf6--f708d0c1a8cb47938304b6446d45adfd cb30ed0d350f4ff58ad6a7e356a1b0bb RX(b0) f708d0c1a8cb47938304b6446d45adfd--cb30ed0d350f4ff58ad6a7e356a1b0bb cb30ed0d350f4ff58ad6a7e356a1b0bb--2f9fda1034b34e14819d50671ecbc497 0819ee88fc154dafbe3254be8140cbe6 ff95bd6082e14b5789daadbe18c0ee3e H 6ae54e3f68d342f18e946bac613e1c0c--ff95bd6082e14b5789daadbe18c0ee3e 5aa875b232bd4181bf3cb4f41eb05282 3 fc07a5d3eb9a418db2ca91ee89ced6e3 ff95bd6082e14b5789daadbe18c0ee3e--fc07a5d3eb9a418db2ca91ee89ced6e3 df085a2594104a5da96dc0e4782af089 fc07a5d3eb9a418db2ca91ee89ced6e3--df085a2594104a5da96dc0e4782af089 73378e99f33b4f1491847437ef97baed df085a2594104a5da96dc0e4782af089--73378e99f33b4f1491847437ef97baed fd2e7a7f06234855be55b77bd9d96817 X 73378e99f33b4f1491847437ef97baed--fd2e7a7f06234855be55b77bd9d96817 fd2e7a7f06234855be55b77bd9d96817--86227fcd81cc4db7b97055495a3480b6 ae483fe14efd47e386caa8fdc99b8d0e RZ(g0) fd2e7a7f06234855be55b77bd9d96817--ae483fe14efd47e386caa8fdc99b8d0e b3b037b0aa1044c6950452f769e238f0 X ae483fe14efd47e386caa8fdc99b8d0e--b3b037b0aa1044c6950452f769e238f0 b3b037b0aa1044c6950452f769e238f0--38e9778d34014599a2b7a9fbd2d8926a 64476c77abc548c88e1d7e4a44dbcff4 b3b037b0aa1044c6950452f769e238f0--64476c77abc548c88e1d7e4a44dbcff4 9b0a78a35aa1405ba530484c6a300b9a 64476c77abc548c88e1d7e4a44dbcff4--9b0a78a35aa1405ba530484c6a300b9a f4be395efbc24bf389ecde56d340f68c 9b0a78a35aa1405ba530484c6a300b9a--f4be395efbc24bf389ecde56d340f68c dac0651af95e42eeb9cbe6817794ff31 X f4be395efbc24bf389ecde56d340f68c--dac0651af95e42eeb9cbe6817794ff31 dac0651af95e42eeb9cbe6817794ff31--c9b3c97d17bd428c96131b417540d430 5615028799b0439bb78f1d4b20959ff2 RZ(g0) dac0651af95e42eeb9cbe6817794ff31--5615028799b0439bb78f1d4b20959ff2 eddb98aac90049c6b2350435b0228eec X 5615028799b0439bb78f1d4b20959ff2--eddb98aac90049c6b2350435b0228eec eddb98aac90049c6b2350435b0228eec--94e3d9be7ba545c48e2919dab4180168 6c4b68deefab43f785d374898fb80899 eddb98aac90049c6b2350435b0228eec--6c4b68deefab43f785d374898fb80899 166a0d6eaa494f8f889e8d430c6595e7 6c4b68deefab43f785d374898fb80899--166a0d6eaa494f8f889e8d430c6595e7 e3e9eb3265044930aba746e688b4c2c4 166a0d6eaa494f8f889e8d430c6595e7--e3e9eb3265044930aba746e688b4c2c4 6acf1667ad2f4d48869ba091cf060bf9 e3e9eb3265044930aba746e688b4c2c4--6acf1667ad2f4d48869ba091cf060bf9 c6df65fb2b134db0a59317504d40da70 6acf1667ad2f4d48869ba091cf060bf9--c6df65fb2b134db0a59317504d40da70 fde005a7e80843a78218acb6ae050a02 c6df65fb2b134db0a59317504d40da70--fde005a7e80843a78218acb6ae050a02 2f13341f64c446fca47653cd46ec02e6 RX(b0) fde005a7e80843a78218acb6ae050a02--2f13341f64c446fca47653cd46ec02e6 2f13341f64c446fca47653cd46ec02e6--0819ee88fc154dafbe3254be8140cbe6 c37b4c1ddfb141e888acb9034f428092 f14ef74f20aa48edb08de8cefb63e5a4 H 5aa875b232bd4181bf3cb4f41eb05282--f14ef74f20aa48edb08de8cefb63e5a4 186e209646864f4c82df9876922eb3ed f14ef74f20aa48edb08de8cefb63e5a4--186e209646864f4c82df9876922eb3ed e68e4e70c9ee4563925266f0435667d3 186e209646864f4c82df9876922eb3ed--e68e4e70c9ee4563925266f0435667d3 c7901ef598c444cf9bd3a2f43b816c2d e68e4e70c9ee4563925266f0435667d3--c7901ef598c444cf9bd3a2f43b816c2d 00c952d07a884d53b15c157591a54ad1 c7901ef598c444cf9bd3a2f43b816c2d--00c952d07a884d53b15c157591a54ad1 d87b41712f014dbda1ba0ea4b87c2ada 00c952d07a884d53b15c157591a54ad1--d87b41712f014dbda1ba0ea4b87c2ada e526cc8167fa4da4968e27e85a265b50 d87b41712f014dbda1ba0ea4b87c2ada--e526cc8167fa4da4968e27e85a265b50 08ccccd0ca8d4030953c5794b4364898 X e526cc8167fa4da4968e27e85a265b50--08ccccd0ca8d4030953c5794b4364898 08ccccd0ca8d4030953c5794b4364898--eb3f189773fb4a15ab9ad7f447f6ef48 c0a5aa6984d544e399ffc9e8e598d5d5 RZ(g0) 08ccccd0ca8d4030953c5794b4364898--c0a5aa6984d544e399ffc9e8e598d5d5 233a8e0a99b545cdbf4cbb8798c24a0d X c0a5aa6984d544e399ffc9e8e598d5d5--233a8e0a99b545cdbf4cbb8798c24a0d 233a8e0a99b545cdbf4cbb8798c24a0d--a232a757eb0b4f919c55d65fda3875fa 3b66a24f9b854ef6a45cc199d2ac5615 233a8e0a99b545cdbf4cbb8798c24a0d--3b66a24f9b854ef6a45cc199d2ac5615 9ab6823f7eba4a599d9b63692516d2a5 3b66a24f9b854ef6a45cc199d2ac5615--9ab6823f7eba4a599d9b63692516d2a5 159469473a0940a7b606c775bce6a5c6 9ab6823f7eba4a599d9b63692516d2a5--159469473a0940a7b606c775bce6a5c6 6d8a8af8bd014910a055e8ad42de3c43 X 159469473a0940a7b606c775bce6a5c6--6d8a8af8bd014910a055e8ad42de3c43 6d8a8af8bd014910a055e8ad42de3c43--209150390a19433cb2a6e4b5d363e766 42c920ab39b14be5ae05db78216f42cf RZ(g0) 6d8a8af8bd014910a055e8ad42de3c43--42c920ab39b14be5ae05db78216f42cf e9e1ab07d723419684365061fa7dedd2 X 42c920ab39b14be5ae05db78216f42cf--e9e1ab07d723419684365061fa7dedd2 e9e1ab07d723419684365061fa7dedd2--222f72492d94483dbd51266a2dc5590f 191edacb832246dfa7ebb77079b62dfc X e9e1ab07d723419684365061fa7dedd2--191edacb832246dfa7ebb77079b62dfc 191edacb832246dfa7ebb77079b62dfc--6acf1667ad2f4d48869ba091cf060bf9 a787b37689594e3493c9a7a71ab6d998 RZ(g0) 191edacb832246dfa7ebb77079b62dfc--a787b37689594e3493c9a7a71ab6d998 f25b91c7b69840529a4b510141c61fbb X a787b37689594e3493c9a7a71ab6d998--f25b91c7b69840529a4b510141c61fbb f25b91c7b69840529a4b510141c61fbb--fde005a7e80843a78218acb6ae050a02 08f7aed5decc42a3ac0afccf38576daa RX(b0) f25b91c7b69840529a4b510141c61fbb--08f7aed5decc42a3ac0afccf38576daa 08f7aed5decc42a3ac0afccf38576daa--c37b4c1ddfb141e888acb9034f428092

Train the QAOA circuit to solve MaxCut

Given the QAOA circuit above, one can construct the associated Qadence QuantumModel and train it using standard gradient based optimization.

The loss function to be minimized reads:

\[\mathcal{L} =-\langle \psi | H_c| \psi \rangle= -\frac12 \sum_{\langle i,j\rangle} \left(1 - \langle \psi | Z_i Z_j | \psi \rangle \right)\]

where \(|\psi\rangle(\beta, \gamma)\) is the wavefunction obtained by running the QAQA quantum circuit and the sum runs over the edges of the graph \(\langle i,j\rangle\).

import torch
from qadence import QuantumModel

torch.manual_seed(seed)


def loss_function(model: QuantumModel):
    # The loss corresponds to the expectation
    # value of the cost Hamiltonian
    return -1.0 * model.expectation().squeeze()


# initialize the parameters to random values
model = QuantumModel(circuit, observable=cost_ham)
model.reset_vparams(torch.rand(model.num_vparams))
initial_loss = loss_function(model)
print(f"Initial loss: {initial_loss}")

# train the model
n_epochs = 100
lr = 0.1

optimizer = torch.optim.Adam(model.parameters(), lr=lr)

for i in range(n_epochs):
    optimizer.zero_grad()
    loss = loss_function(model)
    loss.backward()
    optimizer.step()
    if (i + 1) % (n_epochs // 10) == 0:
        print(f"MaxCut cost at iteration {i+1}: {-loss.item()}")
Initial loss: -2.1782381363858794
MaxCut cost at iteration 10: 3.7470706807026417
MaxCut cost at iteration 20: 3.8378810288930216
MaxCut cost at iteration 30: 3.9424197899236133
MaxCut cost at iteration 40: 3.9981256255766002
MaxCut cost at iteration 50: 3.996470528508214
MaxCut cost at iteration 60: 3.9991374608876606
MaxCut cost at iteration 70: 3.9994678542919555
MaxCut cost at iteration 80: 3.999872558672829
MaxCut cost at iteration 90: 3.9999475834121063
MaxCut cost at iteration 100: 3.9999793311641003

Qadence offers some convenience functions to implement this training loop with advanced logging and metrics track features. You can refer to this tutorial for more details.

Results

Given the trained quantum model, one needs to sample the resulting quantum state to recover the bitstring with the highest probability which corresponds to the maximum cut of the graph.

samples = model.sample(n_shots=100)[0]
most_frequent = max(samples, key=samples.get)

print(f"Most frequently sampled bitstring corresponding to the maximum cut: {most_frequent}")

# let's now draw the cut obtained with the QAOA procedure
colors = []
labels = {}
for node, b in zip(graph.nodes(), most_frequent):
    colors.append("green") if int(b) == 0 else colors.append("red")
    labels[node] = "A" if int(b) == 0 else "B"

nx.draw_networkx(graph, node_color=colors, with_labels=True, labels=labels)
Most frequently sampled bitstring corresponding to the maximum cut: 1001 2025-02-07T10:22:31.935439 image/svg+xml Matplotlib v3.10.0, https://matplotlib.org/

References


  1. Farhi et al. - A Quantum Approximate Optimization Algorithm