← Back to papers
A quantum advantage over classical for local max cut
Charles Carlson, Zackary Jorquera, A. Kolla, Steven Kordonowy·April 17, 2023
Physics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We compare the performance of a quantum local algorithm to a similar classical counterpart on a well-established combinatorial optimization problem LocalMaxCut. We show that a popular quantum algorithm first discovered by Farhi, Goldstone, and Gutmannn [1] called the quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs. These results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical computation.