QAOA MaxCut: Random 3-Regular Graphs

## Background The Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising candidates for demonstrating quantum advantage on near-term hardware. Introduced by Farhi, Goldstone, and Gutmann in 2014, QAOA uses alternating layers of problem-specific and mixer unitaries to find approximate solutions to combinatorial optimization problems. MaxCut is the canonical benchmark for QAOA: given an unweighted graph G = (V, E), partition the vertices into two sets S and S̄ to maximize the number of edges crossing the partition. MaxCut is NP-hard in general, but random 3-regular graphs provide well-characterized instances where: - The Parisi formula gives the asymptotic optimal cut fraction (~0.9163 for large random 3-regular graphs) - Small instances (8-20 vertices) have known exact solutions via brute force - QAOA performance at depth p is theoretically bounded (p=1 guarantees ≥ 0.6924 approximation ratio on 3-regular graphs) This challenge asks you to implement QAOA to solve MaxCut on random 3-regular graphs of increasing size, optimizing both solution quality and circuit efficiency. ## Problem Statement Given a set of random 3-regular graphs (every vertex has exactly 3 neighbors), implement QAOA to find approximate maximum cuts. Your circuit should encode the MaxCut cost operator: C = Σ_{(i,j)∈E} ½(1 - Z_i Z_j) and use the standard transverse field mixer: B = Σ_i X_i The QAOA ansatz applies p rounds of: e^{-iγC} · e^{-iβB} to the uniform superposition |+⟩^n. Optimize the 2p variational parameters (γ₁,...,γₚ, β₁,...,βₚ) to maximize the expected cut value ⟨C⟩. ## Test Cases TC-1: n=8, |E|=12, Optimal Cut=11, Seed=100 (Public) TC-2: n=10, |E|=15, Optimal Cut=13, Seed=200 (Public) TC-3: n=12, |E|=18, Optimal Cut=16, Seed=300 (Hidden) TC-4: n=16, |E|=24, Optimal Cut=22, Seed=400 (Hidden) TC-5: n=20, |E|=30, Optimal Cut=27, Seed=500 (Hidden) Graphs are generated using NetworkX: nx.random_regular_graph(3, n, seed=seed). Edge lists are provided in the submission template. ## Scoring Approximation Ratio (40%): Mean ⟨C⟩/C_opt across all test cases Circuit Efficiency (25%): Normalized (depth × width) — lower is better Scalability (20%): Performance degradation ratio from n=8 to n=20 Reproducibility (15%): Coefficient of variation across 5 seeded runs Targets: - Approximation ratio ≥ 0.90 for full marks (QAOA p≥2 typically achieves this on small instances) - Partial credit for ratio ≥ 0.75 (achievable with p=1) - Bonus consideration for p=1 solutions that beat the 0.6924 theoretical guarantee ## Constraints Frameworks: PennyLane, Qiskit, Cirq, Braket, CUDA-Q, or any gate-based simulator Hardware: Simulator only (no QPU required) Qubits: Equal to graph size n (no ancillas required, but allowed) Seed: Use seed=42 for reproducibility runs Time limit: 5 minutes per test case on consumer hardware QAOA depth: Minimum p=1, recommended p≤5 for efficiency scoring ## References Farhi, Goldstone, Gutmann — A Quantum Approximate Optimization Algorithm (arXiv:1411.4028, 2014) Guerreschi, Matsuura — QAOA for MaxCut requires hundreds of qubits for quantum speed-up (Scientific Reports, 2019) Wurtz, Love — MaxCut QAOA performance guarantees for p>1 (Physical Review A, 2021) Lykov et al. — Tensor network simulation of QAOA (npj Quantum Information, 2022)