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
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
| Line | Explanation |
|---|---|
| 1-3 | Imports. |
| 5 | The edges of the square. |
| 6 | Number of nodes. |
| 9-11 | Cut value of a bit string (reversed to match node indexing). |
| 14 | A function that builds a depth-1 QAOA circuit. |
| 15-16 | Uniform superposition. |
| 17-18 | The cost layer: RZZ(−γ) for each edge. |
| 19 | The mixing layer: RX(2β). |
| 20 | Return the circuit. |
| 23-25 | The expected cut ⟨C⟩ from the exact probabilities. |
| 28 | A grid of values γ ∈ [0, π] and β ∈ [0, π/2]. |
| 29 | The best point on the grid. |
| 30-31 | Print the parameters and ⟨C⟩. |
| 32-33 | The four most probable strings. |
| 34 | Print 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
- Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
- Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
- IBM Quantum (2025). Qiskit SDK API documentation. IBM Quantum Documentation quantum.cloud.ibm.com
