Combinatorial Optimization with QAOA | Quantum Computing Hub
The Quantum Approximate Optimization Algorithm (QAOA) is a leading NISQ-era algorithm for combinatorial optimization. This guide covers QAOA circuit design for MaxCut, TSP, portfolio optimization, and CSPs, with parameter optimization strategies and NISQ-era limitations. 1. QAOA Fundamentals 1.1 Theory Overview # qaoa_theory.py # QAOA solves: max_x C(x) where C: {0,1}^n → ℝ # # Hamiltonian formulation: # H_C = Σ C_i Z_i + Σ C_ij Z_i Z_j + ... (problem Hamiltonian) # H_M = Σ X_i (mixer Hamiltonian) # # QAOA state: |ψ(γ, β)⟩ = ∏_{p=1}^P e^{-iβ_p H_M} e^{-iγ_p H_C} |+⟩^{⊗n} # # Optimal parameters (γ*, β*) = argmax ⟨ψ(γ, β)| H_C |ψ(γ, β)⟩ # # As P → ∞, QAOA finds exact optimum (adiabatic theorem) # For finite P: approximation ratio depends on problem structure import numpy as np from qiskit import QuantumCircuit from qiskit.circuit import Parameter # QAOA ansatz construction def qaoa_ansatz(n_qubits, p, H_C, H_M): """Construct QAOA circuit for P layers""...