QAOA: Quantum Approximate Optimization

๐Ÿ“‘ 5 slides ๐Ÿ‘ 6 views ๐Ÿ“… 11/16/2026 ๐Ÿ“บ YouTube
0.0 (0 ratings)

QAOA at a Glance

Johannes, a research intern at IBM Quantum, introduces QAOA and its role in solving combinatorial optimization problems.

QAOA at a Glance
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.
VQE: A Hybrid Optimization Loop
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.
QUBO and the MaxCut Problem
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.
QAOA Circuit and Adiabatic Connection
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.
Results, Caveats, and Takeaways
1 / 5