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…