QAOA

Can a quantum computer plan a delivery route better than a normal one? Not yet. Here's what QAOA, the Quantum Approximate Optimization Algorithm, actually does, and where it stands.

What this Short covers:

1. Why routing is hard: one van with 15 stops has 43,589,145,600 possible round trips, and the count explodes with every stop you add.
2. QAOA alternates two moves: one rewards good routes (the cost step), one mixes things up (the mixer step), repeated over several rounds.
3. A normal computer tunes how hard each move pushes, round after round, until good answers stand out. That makes QAOA a hybrid quantum-classical algorithm.
4. QAOA was proposed in 2014. There is still no proven advantage over the best classical methods on real-world problems.
5. Verdict: worth watching, not worth the hype yet.

Fine print: 43,589,145,600 = (15-1)!/2, the number of distinct round trips through 15 stops, ignoring direction. "No computer can check them all" is about brute force: at 20 stops (6.1 x 10^16 routes) a 1-exaFLOPS supercomputer checks every route in about a second; at 30 stops (4.4 x 10^30) it's millions of years. Real classical solvers never brute-force: Concorde has solved a tour through 85,900 points exactly. QAOA's "reward" and "mix" moves are the cost and mixer operators; the "tuning" is a classical optimiser setting their angles. The strongest pro-QAOA result so far (Shaydulin et al. 2024) shows better scaling than a classical branch-and-bound solver on one benchmark problem, in noiseless simulation up to 40 qubits: real progress, not a real-world win.

1. Farhi, Goldstone, Gutmann, "A Quantum Approximate Optimization Algorithm" (2014)arxiv.org
2. Blekos et al., "A Review on Quantum Approximate Optimization Algorithm and its Variants" (2023)arxiv.org
3. Shaydulin et al., "Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem", Science Advances (2024)arxiv.org
4. Travelling salesman problem, tour count (n-1)!/2en.wikipedia.org
5. Concorde TSP solver, 85,900-city optimal tourmath.uwaterloo.ca
6. top500.org
7. pmc.ncbi.nlm.nih.gov