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

Given an arbitrary graph, the MaxCut problem consists in finding a graph cut (external) 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 (external) 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)

<?xml version="1.0" encoding="utf-8" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
  "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">





    2025-06-04T09:58:33.680175
    image/svg+xml


      Matplotlib v3.10.3, https://matplotlib.org/






  *{stroke-linejoin: round; stroke-linecap: butt}

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}")

<span></span><code><a id="__codelineno-1-1" name="__codelineno-1-1" href="#__codelineno-1-1"></a><span class="err">The</span><span class="w"> </span><span class="err">maximum</span><span class="w"> </span><span class="err">cu</span><span class="kc">t</span><span class="w"> </span><span class="err">is</span><span class="w"> </span><span class="err">represe</span><span class="kc">nte</span><span class="err">d</span><span class="w"> </span><span class="err">by</span><span class="w"> </span><span class="kc">t</span><span class="err">he</span><span class="w"> </span><span class="err">bi</span><span class="kc">tstr</span><span class="err">i</span><span class="kc">n</span><span class="err">gs</span><span class="w"> </span><span class="p">[</span><span class="err">'</span><span class="mi">0011</span><span class="err">'</span><span class="p">,</span><span class="w"> </span><span class="err">'</span><span class="mi">0101</span><span class="err">'</span><span class="p">,</span><span class="w"> </span><span class="err">'</span><span class="mi">0110</span><span class="err">'</span><span class="p">,</span><span class="w"> </span><span class="err">'</span><span class="mi">1001</span><span class="err">'</span><span class="p">,</span><span class="w"> </span><span class="err">'</span><span class="mi">1010</span><span class="err">'</span><span class="p">,</span><span class="w"> </span><span class="err">'</span><span class="mi">1100</span><span class="err">'</span><span class="p">],</span><span class="w"> </span><span class="err">wi</span><span class="kc">t</span><span class="err">h</span><span class="w"> </span><span class="err">a</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">o</span><span class="kc">f</span><span class="w"> </span><span class="mi">4</span>
</code>

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

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
 "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">




%3


cluster_48a9feca2d8c4b02a587005e321ac870

mixing


cluster_e60a60975a134f77a63c184ab8e6e80c

cost



d3ad6f223c474b5db8760d76dbef8dac
0



644ef42dcdc045b4bfea639dc5bfcb37

H



d3ad6f223c474b5db8760d76dbef8dac--644ef42dcdc045b4bfea639dc5bfcb37




b14f4a4cac1f464a8882236570214a54
1




04045ac4c4e148c6a3bdb34480df4c08




644ef42dcdc045b4bfea639dc5bfcb37--04045ac4c4e148c6a3bdb34480df4c08




b122b3a4a607427fb16c0a5f6ecb2518




04045ac4c4e148c6a3bdb34480df4c08--b122b3a4a607427fb16c0a5f6ecb2518




c7acbea3d06346be9c7bc9c4adf2163c




b122b3a4a607427fb16c0a5f6ecb2518--c7acbea3d06346be9c7bc9c4adf2163c




5dee34cff76a42b1a5e4a4c3bd074ef5




c7acbea3d06346be9c7bc9c4adf2163c--5dee34cff76a42b1a5e4a4c3bd074ef5




2167644d52de4365ba07ca313f3b612b




5dee34cff76a42b1a5e4a4c3bd074ef5--2167644d52de4365ba07ca313f3b612b




6ff20fe178434192ad37972020adb139




2167644d52de4365ba07ca313f3b612b--6ff20fe178434192ad37972020adb139




6fab782198754555aa65da74834de6e0




6ff20fe178434192ad37972020adb139--6fab782198754555aa65da74834de6e0




11dd7c92479942769400d6e9d21e3250




6fab782198754555aa65da74834de6e0--11dd7c92479942769400d6e9d21e3250




44603d02896140ddb54f1752b5a9dd47




11dd7c92479942769400d6e9d21e3250--44603d02896140ddb54f1752b5a9dd47




d9e1a256b9024d08a9b39c644725299f




44603d02896140ddb54f1752b5a9dd47--d9e1a256b9024d08a9b39c644725299f




3ab4dc21f2164e9da3aa7b08a0182e5b




d9e1a256b9024d08a9b39c644725299f--3ab4dc21f2164e9da3aa7b08a0182e5b




76d6ad51f6d841e0b034e83343511204




3ab4dc21f2164e9da3aa7b08a0182e5b--76d6ad51f6d841e0b034e83343511204




a0ae64b8932549cd9ccdd9f42f32d1da




76d6ad51f6d841e0b034e83343511204--a0ae64b8932549cd9ccdd9f42f32d1da




f23305a2d51c447baf315d1cb5eea765




a0ae64b8932549cd9ccdd9f42f32d1da--f23305a2d51c447baf315d1cb5eea765




753f25494c164404833d45ba70e5654e




f23305a2d51c447baf315d1cb5eea765--753f25494c164404833d45ba70e5654e




4c5fce294c074df3ae358a9d5f4a6022




753f25494c164404833d45ba70e5654e--4c5fce294c074df3ae358a9d5f4a6022




b23f7548dd53474babc44fe89be0dde6




4c5fce294c074df3ae358a9d5f4a6022--b23f7548dd53474babc44fe89be0dde6




538e3e85c8ce4b8789cee3f1dcd9f2f7




b23f7548dd53474babc44fe89be0dde6--538e3e85c8ce4b8789cee3f1dcd9f2f7




f5ce651e3f01424c9988c9e225e52105

RX(b0)



538e3e85c8ce4b8789cee3f1dcd9f2f7--f5ce651e3f01424c9988c9e225e52105




ce9f9c026f42463a94abcbe43b74a0ce



f5ce651e3f01424c9988c9e225e52105--ce9f9c026f42463a94abcbe43b74a0ce




2c3113c86c0d4a3ca7eab65502025685




2a3b147af87d4f1cbcdd4b5957230082

H



b14f4a4cac1f464a8882236570214a54--2a3b147af87d4f1cbcdd4b5957230082




32e31599c5b14c0ab16a588b69d7b75a
2




7d78dae0154148d48ea1fd5ed111994f

X



2a3b147af87d4f1cbcdd4b5957230082--7d78dae0154148d48ea1fd5ed111994f




7d78dae0154148d48ea1fd5ed111994f--04045ac4c4e148c6a3bdb34480df4c08




c0f8916c7e464bd481537b735d3ced54

RZ(g0)



7d78dae0154148d48ea1fd5ed111994f--c0f8916c7e464bd481537b735d3ced54




b7e4b8af3ba74c559e5e8a6a1c1d0add

X



c0f8916c7e464bd481537b735d3ced54--b7e4b8af3ba74c559e5e8a6a1c1d0add




b7e4b8af3ba74c559e5e8a6a1c1d0add--c7acbea3d06346be9c7bc9c4adf2163c




a88f3d0ba6b142dc9b8654049c8f4819




b7e4b8af3ba74c559e5e8a6a1c1d0add--a88f3d0ba6b142dc9b8654049c8f4819




528749bc79914640a3e753718d169cfd




a88f3d0ba6b142dc9b8654049c8f4819--528749bc79914640a3e753718d169cfd




85f81348098648228c448075b6c5e55a




528749bc79914640a3e753718d169cfd--85f81348098648228c448075b6c5e55a




1f9f05ec56634d8bb270253126d360a5




85f81348098648228c448075b6c5e55a--1f9f05ec56634d8bb270253126d360a5




c519c9ee62f643ad84ff9d53587dc250




1f9f05ec56634d8bb270253126d360a5--c519c9ee62f643ad84ff9d53587dc250




b30d335ad5fd4f6baa1e0e5e55c69488




c519c9ee62f643ad84ff9d53587dc250--b30d335ad5fd4f6baa1e0e5e55c69488




1850fce9ce774a86ad05e59940abb267




b30d335ad5fd4f6baa1e0e5e55c69488--1850fce9ce774a86ad05e59940abb267




39db0d906c96478b8145737f21d145e7




1850fce9ce774a86ad05e59940abb267--39db0d906c96478b8145737f21d145e7




6d4308847617449385b35fdda29364f6




39db0d906c96478b8145737f21d145e7--6d4308847617449385b35fdda29364f6




55094006b25b42a8bd2c6413d8a35a8d




6d4308847617449385b35fdda29364f6--55094006b25b42a8bd2c6413d8a35a8d




b7c87c43caba4364bc2a52da36c656b1




55094006b25b42a8bd2c6413d8a35a8d--b7c87c43caba4364bc2a52da36c656b1




547972a9d69b405ebec31ed13349c7c9




b7c87c43caba4364bc2a52da36c656b1--547972a9d69b405ebec31ed13349c7c9




ca581f32ae3b4905bebcdab551c7dd28




547972a9d69b405ebec31ed13349c7c9--ca581f32ae3b4905bebcdab551c7dd28




3155c3b1df644c9998c08866c7c1c9a9




ca581f32ae3b4905bebcdab551c7dd28--3155c3b1df644c9998c08866c7c1c9a9




8d7b2d0974e74757a9ebffbd158d8267




3155c3b1df644c9998c08866c7c1c9a9--8d7b2d0974e74757a9ebffbd158d8267




d337980a420d400d83d1b41b97f5ee4b

RX(b0)



8d7b2d0974e74757a9ebffbd158d8267--d337980a420d400d83d1b41b97f5ee4b




d337980a420d400d83d1b41b97f5ee4b--2c3113c86c0d4a3ca7eab65502025685




418b09fd5a054aea8ed6e231fec16cb4




1b5ad9cd3ac74d62b9a18729fb9436b1

H



32e31599c5b14c0ab16a588b69d7b75a--1b5ad9cd3ac74d62b9a18729fb9436b1




b478f5874bb64d6aaf020bb7af456388
3




6c7d70e7fba54961b7e63db31c8ccb77




1b5ad9cd3ac74d62b9a18729fb9436b1--6c7d70e7fba54961b7e63db31c8ccb77




a8f768103c834d1ab9d9160692f3d393




6c7d70e7fba54961b7e63db31c8ccb77--a8f768103c834d1ab9d9160692f3d393




31e9982767bc4e87add2bb685c5a8126




a8f768103c834d1ab9d9160692f3d393--31e9982767bc4e87add2bb685c5a8126




bd662cf36a96428493465ca320b124a7

X



31e9982767bc4e87add2bb685c5a8126--bd662cf36a96428493465ca320b124a7




bd662cf36a96428493465ca320b124a7--5dee34cff76a42b1a5e4a4c3bd074ef5




047e9a819576470481f2b89cbd677eb9

RZ(g0)



bd662cf36a96428493465ca320b124a7--047e9a819576470481f2b89cbd677eb9




5961eb4c2034460486e159ef9c413522

X



047e9a819576470481f2b89cbd677eb9--5961eb4c2034460486e159ef9c413522




5961eb4c2034460486e159ef9c413522--6ff20fe178434192ad37972020adb139




2bf6a9a7cfe84c86aceb3c890cda19b0




5961eb4c2034460486e159ef9c413522--2bf6a9a7cfe84c86aceb3c890cda19b0




8885b487327f48889cefb80bbd2472f8




2bf6a9a7cfe84c86aceb3c890cda19b0--8885b487327f48889cefb80bbd2472f8




567ab61a632d459d9edc4d7075dcec21




8885b487327f48889cefb80bbd2472f8--567ab61a632d459d9edc4d7075dcec21




410abbce98b44e5982610d8e3018e8be

X



567ab61a632d459d9edc4d7075dcec21--410abbce98b44e5982610d8e3018e8be




410abbce98b44e5982610d8e3018e8be--1850fce9ce774a86ad05e59940abb267




e0df7533e16c40d8a7cb5d256ecf8c35

RZ(g0)



410abbce98b44e5982610d8e3018e8be--e0df7533e16c40d8a7cb5d256ecf8c35




f8ecf3f508dd49eb8fd6bba3c365a20f

X



e0df7533e16c40d8a7cb5d256ecf8c35--f8ecf3f508dd49eb8fd6bba3c365a20f




f8ecf3f508dd49eb8fd6bba3c365a20f--6d4308847617449385b35fdda29364f6




0d7482aa724044a0ae55678852b75fbb




f8ecf3f508dd49eb8fd6bba3c365a20f--0d7482aa724044a0ae55678852b75fbb




230450758fbe4366ae9f6c6ce6a522cd




0d7482aa724044a0ae55678852b75fbb--230450758fbe4366ae9f6c6ce6a522cd




6f7336d2a06947abb5dbd20f4393d404




230450758fbe4366ae9f6c6ce6a522cd--6f7336d2a06947abb5dbd20f4393d404




908c1671c7a64c52b649922542b38eeb




6f7336d2a06947abb5dbd20f4393d404--908c1671c7a64c52b649922542b38eeb




90898fd382504d3a8faaac23be51a05b




908c1671c7a64c52b649922542b38eeb--90898fd382504d3a8faaac23be51a05b




d3909bb43f2045c0b13b8bf53f3dc6a7




90898fd382504d3a8faaac23be51a05b--d3909bb43f2045c0b13b8bf53f3dc6a7




da44a6e425d941f28a831fabf6b01f85

RX(b0)



d3909bb43f2045c0b13b8bf53f3dc6a7--da44a6e425d941f28a831fabf6b01f85




da44a6e425d941f28a831fabf6b01f85--418b09fd5a054aea8ed6e231fec16cb4




b50fe954cfa74efb98be4749eea15e78




f290f4b67a954978af34da378e1a3c0f

H



b478f5874bb64d6aaf020bb7af456388--f290f4b67a954978af34da378e1a3c0f




48b81ddba3b94a529a25caa8887e9066




f290f4b67a954978af34da378e1a3c0f--48b81ddba3b94a529a25caa8887e9066




6bdfa332578d496db90d0b1467a573ea




48b81ddba3b94a529a25caa8887e9066--6bdfa332578d496db90d0b1467a573ea




99451f28f621403e9e2aead1801d41ea




6bdfa332578d496db90d0b1467a573ea--99451f28f621403e9e2aead1801d41ea




b74285ddd05a42d3be75132eb8f4768e




99451f28f621403e9e2aead1801d41ea--b74285ddd05a42d3be75132eb8f4768e




35f5f38f49f44613b053e20a1693e2cb




b74285ddd05a42d3be75132eb8f4768e--35f5f38f49f44613b053e20a1693e2cb




3ef2a2e951164d51bb1eb525b59ef619




35f5f38f49f44613b053e20a1693e2cb--3ef2a2e951164d51bb1eb525b59ef619




a0dc967127a946c290e6d4ebdc0b576a

X



3ef2a2e951164d51bb1eb525b59ef619--a0dc967127a946c290e6d4ebdc0b576a




a0dc967127a946c290e6d4ebdc0b576a--6fab782198754555aa65da74834de6e0




eb326809b562442a9f80bad25335f438

RZ(g0)



a0dc967127a946c290e6d4ebdc0b576a--eb326809b562442a9f80bad25335f438




2a834e320e64402fabafedb402c6fe28

X



eb326809b562442a9f80bad25335f438--2a834e320e64402fabafedb402c6fe28




2a834e320e64402fabafedb402c6fe28--44603d02896140ddb54f1752b5a9dd47




a796430e6cf740a594c9f115e82873a3




2a834e320e64402fabafedb402c6fe28--a796430e6cf740a594c9f115e82873a3




635c3dfc89284b8791ff50ad942abbad




a796430e6cf740a594c9f115e82873a3--635c3dfc89284b8791ff50ad942abbad




fb1aa35359e14f24825722aed0854cf4




635c3dfc89284b8791ff50ad942abbad--fb1aa35359e14f24825722aed0854cf4




5aeabfb3708b4b10b5f352c0e8c50a0b

X



fb1aa35359e14f24825722aed0854cf4--5aeabfb3708b4b10b5f352c0e8c50a0b




5aeabfb3708b4b10b5f352c0e8c50a0b--55094006b25b42a8bd2c6413d8a35a8d




f8b3d9124a3d4cf391c072bec9deee55

RZ(g0)



5aeabfb3708b4b10b5f352c0e8c50a0b--f8b3d9124a3d4cf391c072bec9deee55




c51ac01cb1cb4e5e8b78a21650230aa5

X



f8b3d9124a3d4cf391c072bec9deee55--c51ac01cb1cb4e5e8b78a21650230aa5




c51ac01cb1cb4e5e8b78a21650230aa5--547972a9d69b405ebec31ed13349c7c9




a497d6e53ecc4de7954ad15a8ef3e857

X



c51ac01cb1cb4e5e8b78a21650230aa5--a497d6e53ecc4de7954ad15a8ef3e857




a497d6e53ecc4de7954ad15a8ef3e857--908c1671c7a64c52b649922542b38eeb




3b8203f547bc4190a8fe284a78d13cdb

RZ(g0)



a497d6e53ecc4de7954ad15a8ef3e857--3b8203f547bc4190a8fe284a78d13cdb




f7bcd4b7722b489b98c8c0001278b76c

X



3b8203f547bc4190a8fe284a78d13cdb--f7bcd4b7722b489b98c8c0001278b76c




f7bcd4b7722b489b98c8c0001278b76c--d3909bb43f2045c0b13b8bf53f3dc6a7




d5f0358a66cc4a6aa32cfa39454ef824

RX(b0)



f7bcd4b7722b489b98c8c0001278b76c--d5f0358a66cc4a6aa32cfa39454ef824




d5f0358a66cc4a6aa32cfa39454ef824--b50fe954cfa74efb98be4749eea15e78

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()}")

<span></span><code><a id="__codelineno-1-1" name="__codelineno-1-1" href="#__codelineno-1-1"></a><span class="err">I</span><span class="kc">n</span><span class="err">i</span><span class="kc">t</span><span class="err">ial</span><span class="w"> </span><span class="err">loss</span><span class="p">:</span><span class="w"> </span><span class="mf">-2.1782381363858794</span>
<a id="__codelineno-1-2" name="__codelineno-1-2" href="#__codelineno-1-2"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">10</span><span class="p">:</span><span class="w"> </span><span class="mf">3.7470706807026417</span>
<a id="__codelineno-1-3" name="__codelineno-1-3" href="#__codelineno-1-3"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">20</span><span class="p">:</span><span class="w"> </span><span class="mf">3.8378810288930216</span>
<a id="__codelineno-1-4" name="__codelineno-1-4" href="#__codelineno-1-4"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">30</span><span class="p">:</span><span class="w"> </span><span class="mf">3.9424197899236133</span>
<a id="__codelineno-1-5" name="__codelineno-1-5" href="#__codelineno-1-5"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">40</span><span class="p">:</span><span class="w"> </span><span class="mf">3.9981256255766002</span>
<a id="__codelineno-1-6" name="__codelineno-1-6" href="#__codelineno-1-6"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">50</span><span class="p">:</span><span class="w"> </span><span class="mf">3.996470528508214</span>
<a id="__codelineno-1-7" name="__codelineno-1-7" href="#__codelineno-1-7"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">60</span><span class="p">:</span><span class="w"> </span><span class="mf">3.9991374608876606</span>
<a id="__codelineno-1-8" name="__codelineno-1-8" href="#__codelineno-1-8"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">70</span><span class="p">:</span><span class="w"> </span><span class="mf">3.9994678542919555</span>
<a id="__codelineno-1-9" name="__codelineno-1-9" href="#__codelineno-1-9"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">80</span><span class="p">:</span><span class="w"> </span><span class="mf">3.999872558672829</span>
<a id="__codelineno-1-10" name="__codelineno-1-10" href="#__codelineno-1-10"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">90</span><span class="p">:</span><span class="w"> </span><span class="mf">3.9999475834121063</span>
<a id="__codelineno-1-11" name="__codelineno-1-11" href="#__codelineno-1-11"></a><span class="err">MaxCu</span><span class="kc">t</span><span class="w"> </span><span class="err">cos</span><span class="kc">t</span><span class="w"> </span><span class="err">a</span><span class="kc">t</span><span class="w"> </span><span class="err">i</span><span class="kc">terat</span><span class="err">io</span><span class="kc">n</span><span class="w"> </span><span class="mi">100</span><span class="p">:</span><span class="w"> </span><span class="mf">3.9999793311641003</span>
</code>

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
<?xml version="1.0" encoding="utf-8" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
  "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">





    2025-06-04T09:58:37.725120
    image/svg+xml


      Matplotlib v3.10.3, https://matplotlib.org/






  *{stroke-linejoin: round; stroke-linecap: butt}

References

Farhi et al. (external) - A Quantum Approximate Optimization Algorithm ↩

Previous
Classification with QNN Next
Solving a 1D ODE