Exercises: Chapter 20 — QAOA — The Quantum Approximate Optimization Algorithm for Combinatorial Problems

Exercise 20.1: MaxCut by Hand

Consider a 4-node cycle graph $C_4$ (a square). Write the MaxCut cost Hamiltonian $H_C$ explicitly as a sum of Pauli-$Z$ operators. Find all ground states of $H_C$ and verify they correspond to maximum cuts. What is the degeneracy of the ground state, and why?

Exercise 20.2: QAOA Circuit for a Triangle

Draw the complete QAOA circuit ($p=1$) for MaxCut on a triangle graph (3 nodes, fully connected). Label all rotation angles. Compute the expectation value $\langle H_C \rangle$ analytically as a function of $\gamma$ and $\beta$. Find the optimal $(\gamma, \beta)$ that minimizes $\langle H_C \rangle$.

Exercise 20.3: Implement and Compare Depths

Implement QAOA for MaxCut on a 6-node Erdős-Rényi random graph with edge probability 0.5. Run QAOA with $p=1, 2, 3$ and compare the approximation ratios. Plot approximation ratio vs. $p$. Discuss the trade-off between solution quality and circuit depth.

Exercise 20.4: Parameter Concentration

Generate 10 random 3-regular graphs with $n=8, 10, 12, 14$ nodes. For each, optimize QAOA with $p=1$ and record the optimal $(\gamma, \beta)$. Plot the parameters and assess whether they concentrate. If they do, use the average parameters on a new 16-node 3-regular graph and compare the approximation ratio to the optimized ratio.

Exercise 20.5: Constrained Mixer Design

Design a QAOA circuit for the Maximum Independent Set problem on a 4-node path graph. Use the standard cost Hamiltonian (penalize adjacent selected vertices) and an XY-mixer that preserves the number of selected vertices. Implement in Qiskit and compare the solution quality with the standard X-mixer.

Exercise 20.6: QUBO to Ising Conversion

Convert the following QUBO to its Ising representation: $C(\mathbf{z}) = -5z_1 + 3z_2 - 2z_3 + 4z_1 z_2 - z_2 z_3$. Write the resulting Pauli-$Z$ Hamiltonian and identify the number of qubits and terms.

Exercise 20.7: Trotter Error Analysis

For a 4-qubit MaxCut problem on a square graph with $p=2$ QAOA layers, compute the Trotter error for first-order and second-order Trotter decompositions. What is the maximum error as a function of $\gamma$ and $\beta$?

Exercise 20.8: Noise Impact on QAOA

Using the noise model from Section 20.6.1, run QAOA with $p=1, 2, 3$ for increasing depolarizing error rates $p_{2q} \in [0.001, 0.01, 0.05, 0.1]$. At what error rate does QAOA perform worse than random assignment? Plot the approximation ratio vs. error rate for each depth $p$.

Exercise 20.9: Warm-Start QAOA

Implement warm-start QAOA for MaxCut on a 10-node random graph. Compare: (a) standard QAOA starting from $|+\rangle^{\otimes n}$, (b) warm-start QAOA starting from a greedy classical solution, (c) warm-start QAOA starting from a Goemans-Williamson solution. How much does warm-starting improve the approximation ratio?

Exercise 20.10: Portfolio Optimization

Encode a 4-asset portfolio optimization problem as an Ising Hamiltonian. The objective is to minimize risk (variance) subject to a target return and budget constraint. Implement QAOA with an XY-mixer that preserves the number of selected assets. Compare the results with brute-force enumeration.

Exercise 20.11: Weighted MaxCut

Implement QAOA for weighted MaxCut on a 6-node graph with random edge weights in $[1, 10]$. Compare the approximation ratios achieved at $p=1, 2, 3$. Does increasing $p$ improve the ratio? How does the optimal QAOA solution compare with the Goemans-Williamson solution?

Exercise 20.12: QAOA with XY-Mixer for Constrained Problems

Implement QAOA with an XY-mixer for the Maximum Independent Set problem on a 5-node cycle graph. Compare the feasibility rate (fraction of measurements that satisfy the independence constraint) with standard QAOA using the $X$-mixer. How many of the measured bitstrings are feasible in each case?

Exercise 20.13: QAOA Parameter Landscape Visualization

For a 4-node cycle graph, compute the QAOA energy landscape $F_1(\gamma, \beta)$ on a grid of $100 \times 100$ parameter values in $[0, 2\pi]^2$. Create a 2D contour plot showing the local minima. How many local minima are there? What is the landscape structure? Does the symmetry $F(\gamma, \beta) = F(-\gamma, -\beta)$ hold?

Exercise 20.14: Recursive QAOA Implementation

Implement recursive QAOA (RQAOA) for MaxCut on a 10-node random graph. At each level, measure $\langle Z_i Z_j \rangle$ for all edges and fix the variable with the largest $|\langle Z_i Z_j \rangle|$. Reduce the problem and repeat. Compare the approximation ratio with standard QAOA at the same total depth.

Exercise 20.15: Deriving the QAOA Cost Function for a Specific Graph

Consider the weighted graph with 4 vertices and edges: $(0,1)$ weight 2, $(1,2)$ weight 3, $(2,3)$ weight 1, $(3,0)$ weight 4, $(0,2)$ weight 2. (a) Write the cost Hamiltonian $H_C$ as a sum of Pauli-$Z$ operators. (b) Compute $\langle H_C \rangle$ for the computational basis state $|0101\rangle$ and verify it corresponds to a cut value. (c) What is the maximum weighted cut, and which basis state(s) achieve it? (d) Compute the approximation ratio if QAOA yields $\langle H_C \rangle = -7.5$.

Exercise 20.16: Weighted MaxCut Implementation

Implement QAOA for weighted MaxCut on a 5-node complete graph $K_5$ with random integer weights drawn from $\{1, 2, \ldots, 10\}$. Use the weighted cost function from Section 20.11.3. (a) Find the optimal weighted cut by brute force. (b) Run QAOA with $p=1, 2, 3$ and compare approximation ratios. (c) Compare with the unweighted case (all weights = 1) on the same graph structure. Does the weight distribution make optimization harder? (d) Plot the QAOA parameter landscape for $p=1$ and compare the number of local minima in the weighted vs. unweighted cases.

Exercise 20.17: Parameter Concentration Experiment

Generate random 3-regular graphs of sizes $n \in \{8, 12, 16, 20, 24\}$. For each size, generate 10 instances. (a) Optimize QAOA with $p=1$ on each instance and record the optimal $(\gamma^*, \beta^*)$. (b) For each size, compute the mean and standard deviation of the optimal parameters. (c) Plot the standard deviation as a function of $n$. Does it decrease as predicted by the concentration bound? (d) Transfer the mean parameters from $n=8$ to a new $n=50$ graph and compare with full re-optimization. What is the performance gap? (e) Repeat for $p=2$. Does concentration still hold?