Bad Qubits — Learn Quantum by Doing

Multiple choice

For depth p = 1 on unweighted 3-regular graphs, Farhi et al. derived the optimized Max-Cut approximation ratio achievable by QAOA. What bound does the lesson state?

alpha_1 >= 0.878 — matching the Goemans-Williamson guarantee
alpha_1 >= 0.6924 — better than random (0.5) but below the Goemans-Williamson 0.878
alpha_1 >= 0.5 — exactly the random-guessing baseline, with no improvement
alpha_1 = 1.0 — QAOA at p=1 already solves Max-Cut exactly