Publications (28)
Invariant Quantum Algorithms for Insertion into an Ordered List
Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1
We consider the problem of inserting one item into a list of N-1 ordered items. We previously showed that no quantum algorithm could solve this problem in fewer than log N/(2 log l…
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…
Quantum Adiabatic Algorithms, Small Gaps, and Different Paths
Edward Farhi, Jeffrey Goldstone, David Gosset +3
We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all…
Finding cliques by quantum adiabatic evolution
Andrew M. Childs, Edward Farhi, Jeffrey Goldstone +1
Quantum adiabatic evolution provides a general technique for the solution of combinatorial search problems on quantum computers. We present the results of a numerical study of a pa…
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…
Quantum search by measurement
Andrew M. Childs, Enrico Deotto, Edward Farhi +3
We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar in spirit to quantum computation by adi…