QAOA: Quantum Approximate Optimization
๐ 5 slides
๐ 6 views
๐
11/16/2026
๐บ YouTube
QAOA at a Glance
Johannes, a research intern at IBM Quantum, introduces QAOA and its role in solving combinatorial optimization problems.
2
VQE: A Hybrid Optimization Loop
- A Hamiltonian represents a system's energy; its ground state is the quantum state with the lowest expectation value.
- VQE prepares a parameterized trial state, measures its energy, and adjusts circuit parameters to seek a lower value.
- The variational principle ensures every measured trial-state energy is an upper bound on the true ground-state energy.
- A classical optimizer updates the circuit parameters, while a quantum computer estimates energy through repeated measurements.
3
QUBO and the MaxCut Problem
- QUBO minimizes or maximizes a quadratic objective over binary variables, with each variable restricted to zero or one.
- MaxCut partitions graph vertices into two sets and maximizes the total weight of edges crossing between them.
- Representing each vertex with a binary variable makes the cut value a quadratic function that can be encoded as a QUBO.
- For general MaxCut, the GoemansโWilliamson method achieves an approximation ratio of about 0.878 under the unique games conjecture.
4
QAOA Circuit and Adiabatic Connection
- QAOA begins with Hadamard gates to create an equal superposition, then repeats cost and mixer layers before measurement.
- Each cost layer applies the problem Hamiltonian using parameter ฮณ; each mixer layer applies X rotations using parameter ฮฒ.
- At depth P, the circuit has 2P parameters, and measured bit strings provide candidate solutions evaluated by a classical optimizer.
- QAOA resembles a Trotterized adiabatic evolution; increasing depth expands the reachable state space, but finite-depth guarantees are limited.
5
Results, Caveats, and Takeaways
- Low-depth QAOA is not guaranteed to outperform classical methods; results show sub-logarithmic depth can limit approximation quality.
- Hardware connectivity, extra routing gates, sampling noise, and growing measurement needs complicate practical execution.
- Conditional value at risk emphasizes the best fraction of measured outcomes, while warm starts use classical relaxations to seed circuits.
- Optimal parameters can concentrate across related instances, enabling solutions from smaller or similar problems to guide later searches.
1 / 5