Physics – Quantum Physics
Scientific paper
2007-05-06
International Journal of Modern Physics B, Vol. 21, No. 31 (2007) 5187-5205
Physics
Quantum Physics
22 pages, 3 tables
Scientific paper
10.1117/12.717282
Database search has wide applications and is used as a subroutine in many important algorithms. We shall consider a database with one target item. Quantum algorithm finds the target item in a database faster than any classical algorithm. It frequently occurs in practice that only a portion of information about the target item is interesting, or we need to find a group of items sharing some common feature as the target item. This problem is in general formulated as search for a part of the database [a block] containing the target item, instead of the item itself. This is partial search. Partial search trades accuracy for speed, i.e. it works faster than a full search. Partial search algorithm was discovered by Grover and Radhakrishnan. We shall consider optimized version of the algorithm and call it GRK. It can be applied successively [in a sequence]. First the database is partitioned into blocks and we use GRK to find the target block. Then this target block is partitioned into sub-blocks and we use GRK again to find the target sub-block. [We can call it binary quantum search.] Another possibility is to partition the database into sub-blocks directly and use GRK to find the target sub-block in one time. In this paper we prove that the latter is faster [makes less queries to the oracle].
Korepin Vladimir
Xu Ying
No associations
LandOfFree
Binary 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 Binary Quantum Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary Quantum Search will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-111009