Is partial quantum search of a database any easier?

Details Is partial quantum search of a database any easier? Is partial quantum search of a database any easier?

2004-07-15

arxiv.org/abs/quant-ph/0407122v4

Physics

Quantum Physics

15 pages, 4 figures

Scientific paper

In this paper, we consider the partial database search problem where given a database on N items, we are required to determine the first k bits of an address x such that f(x)=1. We derive an algorithm and a lower bound for this problem in the quantum circuits model. Let q(k,N) be the minimum number of queries needed to find the first k bits of the required address x. We show that there exist constants c_k and d_k such that (pi/4) (1 - d_k/sqrt{K}) sqrt{N} <= q(k,n) <= (pi/4) (1 - c_k/sqrt{K}) sqrt{N}, where K=2^k. Thus, it is always easier to determine a few bits of the target address than to find the entire address, but as k becomes large this advantage reduces rapidly.

Affiliated with

Also associated with

No associations

Rating

Is partial quantum search of a database any easier? 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 Is partial quantum search of a database any easier?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Is partial quantum search of a database any easier? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636555