Journal
INTERNATIONAL JOURNAL OF QUANTUM INFORMATION
Volume 6, Issue 3, Pages 503-516Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S021974990800358X
Keywords
adiabatic; quantum; bounds
Categories
Funding
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [829421] Funding Source: National Science Foundation
Ask authors/readers for more resources
The 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 root N. 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available