Abstract | ||
---|---|---|
It is known that the original Grover Search (GS) can be modified to use a general value for the phase θ of the diffusion transform. Then, if the number of answers is relatively large, this modified GS can find one of the answers
with probability one in a single iteration. However, such a quick and error-free GS can only be possible if we can initially
adjust the value of θ correctly against the number of answers, and this seems very hard in usual occasions. A natural question now arises: Can
we enjoy a merit even if GS is used without such an adjustment? In this paper, we give a positive answer using the balls-and-bins
game in which the random sampling of bins is replaced by the quantum sampling, i.e., a single round of modified GS. It is
shown that by using the quantum sampling: (i) The maximum load can be improved quadratically for the static model of the game
and this improvement is optimal. (ii) That is also improved to O(1) for the continuous model if we have a certain knowledge about the total number of balls in the bins after the system becomes
stable.
|
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/3-540-45071-8_32 | Computing and Combinatorics |
Keywords | Field | DocType |
continuous model,single iteration,total number,general value,quantum sampling,improved quadratically,modified gs,balanced allocation,balls-and-bins game,random sampling,error-free gs | Continuous modelling,Static model,Quantum,Discrete mathematics,Quadratic growth,Combinatorics,Ball (bearing),Sampling (statistics),Mathematics | Journal |
Volume | Issue | ISSN |
88-D | 1 | 1745-1361 |
ISBN | Citations | PageRank |
3-540-40534-8 | 0 | 0.34 |
References | Authors | |
17 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kazuo Iwama | 1 | 1400 | 153.38 |
Akinori Kawachi | 2 | 185 | 20.66 |
shigeru yamashita | 3 | 174 | 31.87 |