QAOA

Quantum Approximate Optimization Algorithm: a hybrid algorithm for combinatorial optimization problems.

QAOA (Quantum Approximate Optimization Algorithm) is a variational algorithm designed to find approximate solutions to combinatorial optimization problems. Introduced by Farhi et al. in 2014.

The Setup

Given an optimization problem encoded as a cost function $C(z)$ over bit strings $z$, find:

$$z^{\ast }=\arg \underset{z}{\max }C(z)$$

Examples: MaxCut, traveling salesman, scheduling, portfolio optimization.

The Algorithm

QAOA uses a parameterized quantum circuit alternating between two operations:

1. Problem Hamiltonian $H_C$

Encodes the cost function: $$U_C(\gamma )=e^{-i\gamma H_C}$$

2. Mixer Hamiltonian $H_B$

Creates transitions between states: $$U_B(\beta )=e^{-i\beta H_B}$$

Usually $H_B={\sum }_i{X}_i$ (sum of Pauli X on all qubits).

The Circuit (depth $p$)

|+⟩^n ── U_C(γ₁) ── U_B(β₁) ── U_C(γ₂) ── U_B(β₂) ── ... ── Measure

Parameters: $\vec{\gamma }=({\gamma }_1,\dots ,{\gamma }_p)$ and $\vec{\beta }=({\beta }_1,\dots ,{\beta }_p)$

The Variational Loop

1. Choose p (circuit depth)
2. Initialize parameters (γ, β)
3. Repeat:
   a. Run QAOA circuit on quantum computer
   b. Measure in computational basis
   c. Compute expected cost ⟨C⟩
   d. Classical optimizer updates (γ, β)
4. Return best solution found

Example: MaxCut

Problem: Partition graph vertices to maximize edges cut.

Encoding: $$H_C=\sum _{(i,j)\in E}\frac{1}{2}(1-Z_i{Z}_j)$$

Each edge contributes 1 if endpoints have different values (cut), 0 otherwise.

Performance

Theoretical

• $p\to \infty$: Converges to optimal solution
• Small $p$: Provides approximation

Practical (NISQ)

• Low depth ($p=1-3$) to manage noise
• Approximation quality varies by problem
• Ongoing research on when QAOA beats classical

Variants

Comparison with VQE

Challenges

• Parameter optimization: Non-convex landscape
• Barren plateaus: Can occur at high depth
• Classical competition: Best classical algorithms are strong
• Noise sensitivity: Errors accumulate with depth

See also: VQE, Variational Quantum Algorithm, NISQ, Quantum Speedup