Invariant Quantum Algorithms for Insertion into an Ordered List

Details Invariant Quantum Algorithms for Insertion into an Ordered List Invariant Quantum Algorithms for Insertion into an Ordered List

1999-01-19

arxiv.org/abs/quant-ph/9901059v1

Physics

Quantum Physics

19 pages, LaTeX, amssymb,amsmath packages; email to farhi@mit.edu

Scientific paper

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 log N) queries, for N large. We transform the problem into a "translationally invariant" problem and restrict attention to invariant algorithms. We construct the "greedy" invariant algorithm and show numerically that it outperforms the best classical algorithm for various N. We also find invariant algorithms that succeed exactly in fewer queries than is classically possible, and iterating one of them shows that the insertion problem can be solved in fewer than 0.53 log N quantum queries for large N (where log N is the classical lower bound). We don't know whether a o(log N) algorithm exists.

Affiliated with

Also associated with

No associations

Rating

Invariant Quantum Algorithms for Insertion into an Ordered List does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Invariant Quantum Algorithms for Insertion into an Ordered List, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Invariant Quantum Algorithms for Insertion into an Ordered List will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6170