Quantum search with variable times

Details Quantum search with variable times Quantum search with variable times

2006-09-21

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

Physics

Quantum Physics

19 pages

Scientific paper

Since Grover's seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items and we would like to find a marked item. We consider a new variant of this problem in which evaluating the i-th item may take a different number of time steps for different i. Let t_i be the number of time steps required to evaluate the i-th item. If the numbers t_i are known in advance, we give an algorithm that solves the problem in O(\sqrt{t_1^2+t_2^2+...+t_n^2}) steps. This is optimal, as we also show a matching lower bound. The case, when t_i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.

Affiliated with

Also associated with

No associations

Rating

Quantum search with variable times 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 Quantum search with variable times, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum search with variable times will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-130306