Project: QAOA Tuning

The Quantum Approximate Optimization Algorithm (QAOA) contains two tunable knobs: the depth $p$ (how many cost-then-mixer layers to stack) and the angle vectors $(\vec\gamma, \vec\beta) \in \mathbb{R}^p \times \mathbb{R}^p$ . Getting either wrong costs you solution quality; getting both right is the whole game.

The QAOA circuit structure

A depth- $p$ QAOA circuit on $n$ qubits is:

= U_B(\beta_p)\,U_C(\gamma_p)\,\cdots\,U_B(\beta_1)\,U_C(\gamma_1)\,|{+}\rangle^{\otimes n},$$ where the initial state $|{+}\rangle^{\otimes n} = H^{\otimes n}|0\rangle^{\otimes n}$ is the uniform superposition over all $2^n$ bit strings. The two unitaries alternate: - **Cost layer** $U_C(\gamma_k) = e^{-i\gamma_k H_C}$: encodes the objective by phase-shifting each basis state $|z\rangle$ by $-\gamma_k C(z)$, where $C(z)$ is the cost of solution $z$. High-cost states accumulate more phase, which the mixer then converts into amplitude. - **Mixer layer** $U_B(\beta_k) = e^{-i\beta_k B}$ with $B = \sum_i X_i$: drives coherent tunneling between bit strings so the algorithm explores the solution space. ## Depth and quality: why larger $p$ helps Increasing $p$ strictly expands the set of reachable states, so the maximum achievable $\langle C\rangle$ is non-decreasing in $p$. More precisely, in the limit $p \to \infty$ the optimal QAOA state approaches the true ground state of $H_C$ (Farhi et al. 2014, Theorem 1). For finite $p$ the best approximation ratio depends on the problem structure. For Max-Cut on a graph with $n$ nodes and edge set $E$, the cost Hamiltonian is $$H_C = \frac{1}{2}\sum_{(i,j)\in E}(I - Z_i Z_j).$$ Each term $\frac{1}{2}(I - Z_i Z_j)$ contributes 1 when qubits $i$ and $j$ disagree ($|01\rangle$ or $|10\rangle$) and 0 when they agree, exactly matching the edge-cut definition. ## Implementing the cost unitary for a single edge For the single-edge graph $(q_0, q_1)$, the cost unitary is $$U_C(\gamma) = e^{-i\gamma H_C} = e^{-i\gamma/2}\,e^{i\gamma Z_0 Z_1/2}.$$ The global phase $e^{-i\gamma/2}$ is unobservable. The $ZZ$ interaction $e^{i\gamma Z_0Z_1/2}$ is diagonal in the computational basis with eigenvalues $+1$ for $|00\rangle,|11\rangle$ and $-1$ for $|01\rangle,|10\rangle$, so $$U_C(\gamma)|z_0 z_1\rangle = e^{i\gamma(-1)^{z_0 + z_1}/2}|z_0 z_1\rangle.$$ The standard circuit decomposition uses a CNOT to entangle the parity into a single qubit, then an $R_z$ rotation to apply the phase, then a second CNOT to uncompute: $$e^{i\gamma Z_0 Z_1/2}:\quad CX_{0\to1},\quad R_z(-\gamma)_1,\quad CX_{0\to1}.$$ This adds phase $e^{-i(-\gamma)/2} = e^{i\gamma/2}$ when qubit 1 is $|0\rangle$ after the first CNOT (states $|00\rangle,|11\rangle$ agree, parity 0) and $e^{i\gamma/2} \cdot (-1)$ when qubit 1 is $|1\rangle$ (states $|01\rangle,|10\rangle$ disagree, parity 1), reproducing the eigenvalue structure above. ## Optimal $p=1$ angles for a single edge For $p = 1$ on a single edge, the expectation value has the closed-form expression derived in Appendix B of Farhi et al. (2014): $$\langle C(\gamma,\beta)\rangle = \frac{1}{2} + \frac{1}{2}\sin(\gamma)\sin(4\beta).$$ This is maximized when both sine factors equal 1: $$\gamma^* = \frac{\pi}{2}, \qquad \beta^* = \frac{\pi}{8}, \qquad \langle C\rangle_{\max} = 1.$$ Since the maximum possible cut value for a single edge is 1, the **approximation ratio** is $1$: a single layer of QAOA suffices to find the exact optimum for this graph. By symmetry the optimal state concentrates all probability on the two Max-Cut solutions: $$P(|01\rangle) = P(|10\rangle) = \frac{1}{2}, \qquad P(|00\rangle) = P(|11\rangle) = 0.$$ You can verify this by noting $\langle C\rangle = 1 \cdot P_{cut} + 0 \cdot P_{no-cut} = 1$ and using the symmetry $P(|01\rangle) = P(|10\rangle)$. <Callout type="tip"> Depth is not free: every additional layer adds $2n$ parameters and more gates. For small instances the optimal angles can be found analytically (as here) or by grid search. For large $p$ or large $n$, gradient-based methods such as COBYLA or gradient descent with the parameter-shift rule are used. A useful heuristic called **parameter concentration** shows that optimal angles for small instances often transfer to larger graphs of the same type, reducing the classical optimization cost significantly. </Callout> ## Try it Build the complete $p = 1$ QAOA circuit on 2 qubits for single-edge Max-Cut, using the analytically optimal angles $\gamma = \pi/2$ and $\beta = \pi/8$. The grader checks the output **distribution**: the cut states $|01\rangle$ and $|10\rangle$ should each receive probability $1/2$, and the no-cut states $|00\rangle$ and $|11\rangle$ should each receive probability $0$. <RunnableExample /> After grading, try changing $\gamma$ or $\beta$ away from their optimal values and notice how the probability shifts away from the cut states — that is exactly what classical angle-tuning is optimizing against.