← Quantum Store · Guides · Lessons · Glossary · Packages · About · Türkçe

Quantum Store editors

QAOA for MaxCut — a hands-on lesson

A tested, commented Qiskit example that walks step by step through the quantum approximate optimisation algorithm (QAOA) on the MaxCut problem of a 4-node graph.

The problem

Split the nodes of a graph into two groups so that the number of edges between the two groups (the cut) is as large as possible. This is the MaxCut problem. Many network design, clustering and scheduling problems can be turned into this form.

The graph in the example is a 4-node ring plus one diagonal: 0-1, 1-2, 2-3, 3-0, 0-2. The best cut is 4.

QAOA steps

1. Start: A Hadamard is applied to every qubit, giving an equal superposition of all partitions.
2. Cost layer (γ): RZZ(2γ) is applied for each edge. This layer gives a phase to partitions with a large cut.
3. Mixer layer (β): RX(2β) is applied to each qubit.
4. Choosing parameters: A (γ, β) grid is scanned and the pair with the largest expected cut value is chosen.
5. Measurement: The best circuit is sampled 2000 times and the most frequent partition is read.

Test result

• The best parameters were γ=2.827 and β=1.885.
• The expected cut value was 3.230 (the best classical value is 4).
• The most frequently measured partition was 0101. Its cut value is 4, so the optimum was found.

Next steps

1. Use p=2 layers and scipy.optimize.minimize instead of a grid.
2. Try a larger graph (for example an 8-node 3-regular graph).

Installation and running

pip install qiskit numpy
python qaoa_maxcut.py

Tested with: qiskit 2.5.2, Python 3.12.

Links

• QAOA paper (arXiv:1411.4028)
• Qiskit documentation

Package contents

• qaoa_maxcut.py
• README.en.md — this file
• README.md — the same guide in Turkish
• LICENSE — the licence of the files in this package
• KAYNAK.json — a machine-readable summary of the official source

Licence

This package was prepared by the Quantum Store editors and is distributed under the MIT licence.

Quantum Store — https://hakanerdogan.com/en

Example code

The example shipped in the package, run and checked. Comments and printed messages are in Turkish; the code is the same in any language. Everything is in the ZIP.

qaoa_maxcut.py

"""QAOA ile MaxCut — Türkçe açıklamalı örnek (Qiskit).

Problem: Bir grafın düğümlerini iki gruba ayır; iki grup arasında kalan
kenar sayısını (kesimi) en büyük yap.

QAOA (Quantum Approximate Optimization Algorithm), maliyet Hamiltonyeni
(gamma) ve karıştırıcı (beta) katmanlarını sırayla uygular. Burada p=1
katman için (gamma, beta) parametrelerini ızgara taramasıyla seçiyoruz,
sonra en iyi devreyi örnekleyip en sık gelen kesimi okuyoruz.

Çalıştırma:
    pip install qiskit numpy
    python qaoa_maxcut.py
"""

import itertools

import numpy as np
from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler
from qiskit.quantum_info import SparsePauliOp, Statevector

# 4 düğümlü halka + bir köşegen: 0-1, 1-2, 2-3, 3-0, 0-2
n = 4
edges = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)]


def cut_value(bits: str) -> int:
    # Qiskit bit dizgesini sağdan sola okur: bits[-1] = kübit 0
    x = bits[::-1]
    return sum(1 for a, b in edges if x[a] != x[b])


best_classical = max(cut_value("".join(b)) for b in itertools.product("01", repeat=n))

# Maliyet operatörü: C = sum (1 - Z_a Z_b) / 2
terms = []
for a, b in edges:
    z = ["I"] * n
    z[n - 1 - a] = "Z"
    z[n - 1 - b] = "Z"
    terms.append(("".join(z), -0.5))
cost_op = SparsePauliOp.from_list(terms + [("I" * n, 0.5 * len(edges))])


def qaoa_circuit(gamma: float, beta: float, measure: bool) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    qc.h(range(n))
    for a, b in edges:
        qc.rzz(2 * gamma, a, b)  # maliyet katmanı
    qc.rx(2 * beta, range(n))  # karıştırıcı katman
    if measure:
        qc.measure_all()
    return qc


grid = np.linspace(0, np.pi, 41)
best = max(
    ((g, b) for g in grid for b in grid),
    key=lambda gb: Statevector(qaoa_circuit(*gb, measure=False)).expectation_value(cost_op).real,
)
expected = Statevector(qaoa_circuit(*best, measure=False)).expectation_value(cost_op).real
print(f"En iyi parametreler: gamma={best[0]:.3f}, beta={best[1]:.3f}")
print(f"Beklenen kesim değeri: {expected:.3f} (en iyi klasik: {best_classical})")

counts = (
    StatevectorSampler(seed=7)
    .run([qaoa_circuit(*best, measure=True)], shots=2000)
    .result()[0]
    .data.meas.get_counts()
)
top = max(counts, key=counts.get)
print(f"En sık ölçülen ayrım: {top} -> kesim = {cut_value(top)}")

assert cut_value(top) == best_classical
print("Tamam: QAOA en iyi kesimi buldu.")

Related concepts

• QAOA (quantum approximate optimisation algorithm) · QAOA combines parameterised quantum circuits with classical optimisation to search for approximate solutions to combinatorial optimisation problems such as MaxCut.

← All packages

Share: X · LinkedIn