MilestoneTheory & algorithmsConfirmed

A classical algorithm overtakes QAOA's guarantee on an optimization problem

May 13, 2015

In December 2014, Farhi, Goldstone and Gutmann applied QAOA to a constraint problem called Max E3LIN2, beating the best known classical guarantee. In May 2015, Boaz Barak and nine co-authors give a classical algorithm with a better guarantee.

Why it matters

It showed how quickly a claimed quantum edge in optimization can be erased by better classical methods, a pattern that recurs throughout the field.

Boaz Barak · Ankur Moitra · Ryan O'Donnell · Oded Regev · Luca Trevisan · Edward Farhi

See it on the timeline

Related

• MIT physicists propose QAOA, a quantum algorithm for approximate optimization (Nov 14, 2014)
• Ewin Tang removes an exponential quantum speedup for recommendation systems (Jul 10, 2018)