Understand
We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems.
- The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased.
- The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought.
- The depth of the circuit grows linearly with p times (at worst) the number of constraints.
Built on
Quantum Computation and Decision Trees, 1997
Edward Farhi, Sam Gutmann · 1997
Earlier work this paper cites.
Quantum computation by adiabatic evolution, 2000
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser · 2000
Earlier work this paper cites.
Similar
Quantum Adiabatic Evolution Algorithms versus Simulated Annealing, 2002
Edward Farhi, Jeffrey Goldstone, Sam Gutmann · 2002
Cited alongside, same era.
Journal of Algorithms, Volume 53 Issue 2, Pages 169-185
Eran Halperin, Dror Livnat, Uri Zwick. MAX CUT in cubic graphs, 2004 · 2004
Cited alongside, same era.
Then
Different strategies for optimization with the quantum adiabatic algorithm, 2014
Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han-Hsuan Lin, Peter Shor · 2014
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…