Quantum Sampling for Balanced Allocations(<Special Section>Foundations of Computer Science)

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.