4 papers
Optimal Constructions of Hybrid Algorithms
Ming-Yang Kao, Yuan Ma, Michael Sipser +1
We study on-line strategies for solving problems with hybrid algorithms. There is a problem Q and w basic algorithms for solving Q. For some lambda <= w, we have a computer with la…
Quantum Computation by Adiabatic Evolution
Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1
We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Ha…
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…
A Limit on the Speed of Quantum Computation for Insertion into an Ordered List
E. Farhi, J. Goldstone, S. Gutmann +1
We consider the problem of inserting a new item into an ordered list of N-1 items. The length of an algorithm is measured by the number of comparisons it makes between the new item…