Quantum Sampling for Balanced Allocations

• IWAMA Kazuo

  Graduate School of Informatics, Kyoto University

• KAWACHI Akinori

  Graduate School of Informatics, Kyoto University

• YAMASHITA Shigeru

  Graduate School of Information Science, Nara Institute of Science and Technology

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.

Journal

• IEICE transactions on information and systems

  IEICE transactions on information and systems 88 (1), 39-46, 2005-01-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• quantum computing
• load balancing
• balls-and-bins game

Details

• CRID: 1572543027349076352
• NII Article ID: 110003214133
• NII Book ID: AA10826272
• ISSN: 09168532
• Text Lang: en
• Data Source:
  • CiNii Articles