2.1k citations · 8.3k across the 34 of their papers we have counts for
31 papers · 1 filter
Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA
Edward Farhi, Sam Gutmann, Daniel Ranard +1
We study MaxCut on 3-regular graphs of minimum girth for various 's. We obtain new lower bounds on the maximum cut achievable in such graphs by analyzing the Quantum Approxi…
Strategies for running the QAOA at hundreds of qubits
Brandon Augustino, Madelyn Cain, Edward Farhi +5
We explore strategies aimed at reducing the amount of computation, both quantum and classical, required to run the Quantum Approximate Optimization Algorithm (QAOA). First, followi…
The QAOA gets stuck starting from a good classical string
Madelyn Cain, Edward Farhi, Sam Gutmann +2
The Quantum Approximate Optimization Algorithm (QAOA) is designed to maximize a cost function over bit strings. While the initial state is traditionally a uniform superposition ove…
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
Edward Farhi, David Gamarnik, Sam Gutmann
The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. When conjugating…
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
Edward Farhi, David Gamarnik, Sam Gutmann
The Quantum Approximate Optimization Algorithm can naturally be applied to combinatorial search problems on graphs. The quantum circuit has p applications of a unitary operator tha…
The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1
The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of l…