Quantum Partial Search
A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004. In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L.K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25-50%, 50-70% or 75-100% percentile.
To describe partial search, we consider a database separated into blocks, each of size . Obviously, the partial search problem is easier. Consider the approach we would take classically - we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the compliment). If we don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from to .
Grover's algorithm requires iterations. Partial search will be faster by a numerical factor which depends the number of blocks . Partial search uses global iterations and local iterations. The global Grover operator is designated and the local Grover operator is designated .
The global Grover operator acts acts on the blocks. Essentially, it is given as follows:
- Perform standard Grover iterations on the entire database.
- Perform local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block.
- Perform one standard Grover iteration
The optimal values of and are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by Korepin and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.
Read more about this topic: Grover's Algorithm
Famous quotes containing the words quantum, partial and/or search:
“A personality is an indefinite quantum of traits which is subject to constant flux, change, and growth from the birth of the individual in the world to his death. A character, on the other hand, is a fixed and definite quantum of traits which, though it may be interpreted with slight differences from age to age and actor to actor, is nevertheless in its essentials forever fixed.”
—Hubert C. Heffner (1901–1985)
“The only coöperation which is commonly possible is exceedingly partial and superficial; and what little true coöperation there is, is as if it were not, being a harmony inaudible to men. If a man has faith, he will coöperate with equal faith everywhere; if he has not faith, he will continue to live like the rest of the world, whatever company he is joined to.”
—Henry David Thoreau (1817–1862)
“At any age we must cherish illusions, consolatory or merely pleasant; in youth, they are omnipresent; in old age we must search for them, or even invent them. But with all that, boredom is their natural and inevitable accompaniment.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)