HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
2008; World Scientific; Volume: 06; Issue: 03 Linguagem: Inglês
10.1142/s021974990800358x
ISSN1793-6918
AutoresEdward Farhi, Jeffrey Goldstone, Sam Gutmann, Daniel Nagaj,
Tópico(s)Quantum Mechanics and Applications
ResumoThe quantum adiabatic algorithm is a Hamiltonian based quantum algorithm designed to find the minimum of a classical cost function whose domain has size N. We show that poor choices for the Hamiltonian can guarantee that the algorithm will not find the minimum if the run time grows more slowly than [Formula: see text]. These poor choices are nonlocal and wash out any structure in the cost function to be minimized, and the best that can be hoped for is Grover speedup. These failures tell us what not to do when designing quantum adiabatic algorithms.
Referência(s)