QAOA
Quantum Approximate Optimization Algorithm
Hybrid quantum–classical optimization for QUBO/Ising problems — transparent, reproducible, and benchmarked on Superpositions Studio.
Overview
The Quantum Approximate Optimization Algorithm (QAOA), introduced by Farhi et al. (2014), is a hybrid quantum–classical method for approximately solving combinatorial optimization problems that can be expressed as Ising/QUBO formulations. QAOA alternates between applying a problem-specific cost unitary and a mixer unitary for p layers, parameterized by angles γ (gamma) and β (beta). A classical optimizer tunes these angles to minimize the expected cost measured from the quantum circuit.
Why It Matters
Many real-world tasks reduce to discrete optimization: scheduling, routing, portfolio selection with discrete weights, graph partitioning, and more. QAOA provides a practical NISQ-friendly approach that leverages quantum circuits while relying on classical optimization for parameter search. It is modular (works across many QUBO encodings), interpretable (via problem and mixer Hamiltonians), and compatible with today's hardware for small to medium instances.
How QAOA Works
A five-step process to solve combinatorial optimization problems with hybrid quantum-classical optimization
Formulate the problem
Formulate the problem as an Ising/QUBO cost function C(z) over binary variables.
Initialize qubits
Initialize qubits (typically in a uniform superposition).
Apply p alternating layers
Apply p alternating layers: cost unitary U_C(γ) followed by mixer unitary U_B(β).
Measure and estimate
Measure bitstrings and estimate the expected cost.
Optimize and repeat
Use a classical optimizer to update (γ, β) and repeat until convergence.
At convergence, the bitstrings sampled from the circuit concentrate on high-quality solutions; the best observed or expected value is reported.
Real-World Applications
Where QAOA provides practical solutions for combinatorial optimization
Graph problems
Graph problems: MaxCut, MaxClique, vertex cover.
Logistics & operations
Logistics & operations: routing, scheduling, resource allocation.
Finance
Finance: discrete portfolio optimization, cardinality and budget constraints via QUBO.
Machine learning & feature selection
Machine learning & feature selection: sparse model selection framed as QUBO.
Strengths & Limitations
Strengths
- NISQ-friendly hybrid approach with shallow circuits at low p
- Flexible across many QUBO/Ising problem types
- Interpretable parameters (γ, β) with physics-informed insight
- Amenable to warm-starts and problem-specific mixers
Limitations
- Non-convex optimization; sensitive to initialization and noise
- Performance scales with p and embedding overhead; may not outperform strong classical solvers
- Barren plateaus and parameter concentration can appear as circuits deepen
- Hardware connectivity constraints impact circuit depth and quality
Benchmarking and Verification
Every QAOA run on Superpositions Studio is benchmarked against classical heuristics (e.g., random restarts, greedy, simulated annealing). We report approximation ratios, convergence curves, and cost distributions across shots, with seed-controlled reproducibility and complete logs.
Hardware & Requirements
Proof-of-Concept Example
Real experimental results demonstrating QAOA performance
Task
MaxCut on an 8–16 node graph (synthetic or user-provided)
Layers (p)
1–3
FAQ
Common questions about QAOA implementation and performance
Explore More Algorithms
Expand your quantum computing capabilities
Ready to Run QAOA?
Run QAOA on Superpositions Studio — prototype, benchmark, and export reproducible results. Get your report, code, and baseline comparisons today.
Powered by Superpositions Studio — Transparent, reproducible quantum computing