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
Is QAOA guaranteed to beat classical algorithms?
No. It can perform competitively on some instances, especially at low p, but results are problem- and hardware-dependent.
How do I choose p (the number of layers)?
Start with p=1–2 for shallow circuits; increase gradually while monitoring noise and convergence.
Can I run QAOA on real quantum hardware?
Yes, for small to medium instances after embedding the problem to the device topology. Simulators provide reproducible baselines.
Which optimizers are recommended?
Gradient-free methods like COBYLA/Nelder–Mead and stochastic approaches like SPSA are commonly used; choice depends on noise and landscape.
Related pages
Algorithms, applied use cases and benchmarks connected to this page
Finance
Quantum Portfolio Optimization: QAOA, HHL and Annealing
Compare quantum portfolio optimization: QAOA with quantum walk mixers, HHL mean-variance allocation, and quantum annealing for cardinality-constrained QUBOs.
Comparisons
QAOA vs MILP for Portfolio Knapsack Optimization
Compare constrained QAOA with MILP on a 5-asset portfolio knapsack PoC using an 11-qubit simulator run, feasibility checks, and objective-quality audits.
Algorithms
Quantum Annealing for QUBO and Ising Problems
Map combinatorial optimization problems to QUBO and Ising form and benchmark quantum annealing with reproducible runs, baselines, and hardware notes.
Comparisons
Quantum Annealing vs QAOA for QUBO Problems
Compare quantum annealing with QAOA on QUBO/Ising optimization: hardware, constraints, scaling, and two real portfolio-optimization benchmarks.
Algorithms
Variational Quantum Eigensolver (VQE)
Estimate ground-state energies with the Variational Quantum Eigensolver using reproducible quantum chemistry workflows, benchmarks, and implementation notes.
Chemistry & Materials
Molecular Optimization with VQE Simulations
Optimize molecular structures with VQE simulations, ground-state energy estimation, reproducible reports, and quantum chemistry benchmarks.
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