IEICE TRANSACTIONS on Information
Quantum Sampling for Balanced Allocations
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.39-46
- Publication Date
- 2005/01/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietisy/e88-d.1.39
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuo IWAMA, Akinori KAWACHI, Shigeru YAMASHITA, "Quantum Sampling for Balanced Allocations" in IEICE TRANSACTIONS on Information,
vol. E88-D, no. 1, pp. 39-46, January 2005, doi: 10.1093/ietisy/e88-d.1.39.
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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.1.39/_p
Copy
@ARTICLE{e88-d_1_39,
author={Kazuo IWAMA, Akinori KAWACHI, Shigeru YAMASHITA, },
journal={IEICE TRANSACTIONS on Information},
title={Quantum Sampling for Balanced Allocations},
year={2005},
volume={E88-D},
number={1},
pages={39-46},
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.},
keywords={},
doi={10.1093/ietisy/e88-d.1.39},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Quantum Sampling for Balanced Allocations
T2 - IEICE TRANSACTIONS on Information
SP - 39
EP - 46
AU - Kazuo IWAMA
AU - Akinori KAWACHI
AU - Shigeru YAMASHITA
PY - 2005
DO - 10.1093/ietisy/e88-d.1.39
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2005
AB - 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.
ER -
English
