Code exampleAdvancedquantum optimisation

QAOA by Hand for Max-Cut on the Square

Build a depth-1 QAOA circuit from R_ZZ and R_X and grid-search (γ, β); the best ⟨C⟩ is 3 out of the optimum 4.

The cost layer $e^{-i\gamma H_C}$ with $H_C=\sum(1-Z_iZ_j)/2$ equals, up to a global phase, $\prod R_{ZZ}(-\gamma)$, and the mixing layer is $\prod R_X(2\beta)$. We compute $\langle C\rangle$ exactly from the state vector and then search a $41\times41$ grid. The result: $\gamma=3\pi/4$, $\beta=3\pi/8$ and $\langle C\rangle=3$ (ratio 0.75), and the two optimal solutions 0101 and 1010 each have probability of about $0.266$. This matches the lab's engine. QAOA here does not outperform the simple classical solution for this small graph.

Requirements: pip install qiskit numpy. The code runs on your machine or in Colab, not inside WordPress.

Code

Qiskit
import numpy as np
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
n = 4


def cut_value(bits):
    z = bits[::-1]
    return sum(z[i] != z[j] for i, j in edges)


def qaoa_p1(gamma, beta):
    qc = QuantumCircuit(n)
    qc.h(range(n))
    for i, j in edges:
        qc.rzz(-gamma, i, j)
    qc.rx(2 * beta, range(n))
    return qc


def expected_cut(gamma, beta):
    probs = Statevector.from_instruction(qaoa_p1(gamma, beta)).probabilities_dict()
    return sum(p * cut_value(b) for b, p in probs.items())


grid = [(g, b) for g in np.linspace(0, np.pi, 41) for b in np.linspace(0, np.pi / 2, 41)]
g_best, b_best = max(grid, key=lambda gb: expected_cut(*gb))
print(f"gamma = {g_best:.4f}, beta = {b_best:.4f}")
print("<C> =", round(expected_cut(g_best, b_best), 4), "| optimum = 4")
probs = Statevector.from_instruction(qaoa_p1(g_best, b_best)).probabilities_dict()
top = sorted(probs.items(), key=lambda kv: -kv[1])[:4]
print([(str(b), round(float(p), 4), cut_value(b)) for b, p in top])

Line-by-line code explanation

LineExplanation
1-3Imports.
5The edges of the square.
6Number of nodes.
9-11Cut value of a bit string (reversed to match node indexing).
14A function that builds a depth-1 QAOA circuit.
15-16Uniform superposition.
17-18The cost layer: RZZ(−γ) for each edge.
19The mixing layer: RX(2β).
20Return the circuit.
23-25The expected cut ⟨C⟩ from the exact probabilities.
28A grid of values γ ∈ [0, π] and β ∈ [0, π/2].
29The best point on the grid.
30-31Print the parameters and ⟨C⟩.
32-33The four most probable strings.
34Print them with their cut values.

Expected output (from an actual run)

gamma = 2.3562, beta = 1.1781
<C> = 3.0 | optimum = 4
[('0101', 0.2656, 4), ('1010', 0.2656, 4), ('0110', 0.0781, 2), ('1001', 0.0781, 2)]

The output is deterministic (a grid search over exact probabilities).

Try it yourself

Related topics

References

  1. Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
  2. Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
  3. IBM Quantum (2025). Qiskit SDK API documentation. IBM Quantum Documentation quantum.cloud.ibm.com