Physics – Quantum Physics
Scientific paper
2005-04-20
Quantum Information Processing, vol. 5, number 1, page 5-10, 2006
Physics
Quantum Physics
3 pages, 3 figures
Scientific paper
10.1007/s11128-005-0004-z
Quite often in database search, we only need to extract portion of the information about the satisfying item. Recently Radhakrishnan & Grover [RG] considered this problem in the following form: the database of $N$ items was divided into $K$ equally sized blocks. The algorithm has just to find the block containing the item of interest. The queries are exactly the same as in the standard database search problem. [RG] invented a quantum algorithm for this problem of partial search that took about $0.33\sqrt{N/K}$ fewer iterations than the quantum search algorithm. They also proved that the best any quantum algorithm could do would be to save $0.78 \sqrt(N/K)$ iterations. The main limitation of the algorithm was that it involved complicated analysis as a result of which it has been inaccessible to most of the community. This paper gives a simple analysis of the algorithm. This analysis is based on three elementary observations about quantum search, does not require a single equation and takes less than 2 pages.
Grover Lov K.
Korepin Vladimir E.
No associations
LandOfFree
Simple Algorithm for Partial Quantum Search 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 Simple Algorithm for Partial Quantum Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple Algorithm for Partial Quantum Search will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-315530