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…