Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2697))
Included in the following conference series:
943Accesses
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 toO(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.
Current affiliation: Graduate School of Information Science, Nara Institute of Science and Technology.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Aaronson, “Quantum Lower Bound for the Collision Problem,” Proceedings of the 34th ACM Symposium on Theory of Computing, 635–642, 2002.
Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, “Balanced Allocations,” SIAM Journal on Computing, Vol. 29, No. 1, 180–200, 1999.
M. Adler, S. Chakarabarti, M. Mitzenmacher, and L. Rasmussen, “Parallel Randomized Load Balancing,” Proceedings of the 27th ACM Symposium on Theory of Computing, 238–247, 1995.
M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight Bounds on Quantum Searching,” Fortschritte der Physik, vol. 46(4–5), 493–505, 1998.
G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum amplitude amplification and estimation”, Quantum Computation and Quantum Information: A Millennium Volume, AMS Contemporary Mathematics Series, May 2000.
P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking, “Balanced Allocations: The Heavily Loaded Case,” Proceedings of the 32nd ACM Symposium on Theory of Computing, 745–754, 2000.
G. Brassard, P. Høyer and A. Tapp, “Quantum cryptanalysis of hash and claw-free functions,” Proceedings of 3rd Latin American Symposium on Theoretical Informatics (LATIN’98), Vol. 1380 of Lecture Notes in Computer Science, 163–169, 1998.
G. Brassard, P. Høyer, and A. Tapp, “Quantum Counting,” Proceedings of the 25th International Colloquium on Automata, Languages, and Programming, Vol. 1443 of Lecture Notes in Computer Science, 820–831, 1998.
H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and R. de Wolf, “Quantum Algorithm for Element Distinctness”, Proceedings of the 16th IEEE Conference on Computational Complexity, 131–137, 2001.
D. P. Chi and J. Kim, “Quantum Database Searching by a Single Query,” Lecture at First NASA International Conference on Quantum Computing and Quantum Communications, 1998.
T. H. Cormen, C. E. Leiserson and R. L. Rivest, “Introduction to Algorithms,” Cambridge, Mass.: MIT Press, 1990.
C. Dürr and P. Høyer “A Quantum Algorithm for Finding the Minimum,” LANL preprint, http://xxx.lanl.gov/archive/quant-ph/9607014.
L. K. Grover, “A fast quantum mechanical algorithm for database search,” Proceedings of the 28th ACM Symposium on Theory of Computing, 212–218, 1996.
L. K. Grover, “A framework for fast quantum mechanical algorithms,” Proceedings of the 30th ACM Symposium on Theory of Computing, 53–56, 1998.
L. K. Grover, “Rapid sampling through quantum computing,” Proceedings of the 32nd ACM Symposium on Theory of Computing, 618–626, 2000.
N. Johnson, and S. Kotz, “Urn Models and Their Application,” John Wily & Sons, New York, 1977.
V. Kolchin, B. Sevastyanov, and V. Chistyakov, “Random Allocations,” John Wiley & Sons, New York, 1978.
G. L. Long, “Grover Algorithm with Zero Theoretical Failure Rate,” Physical Review A, Vol. 6 4022307, June, 2001.
M. Mitzenmacher, “The Power of Two Choices in Randomized Load Balancing,” Ph.D. Thesis, 1996.
R. Motwani, and P. Raghavan, “Randomized Algorithms,” Cambridge University Press, 1995.
Y. Shi, “Quantum Lower Bounds for the Collision and the Element Distinctness Problems,” Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 513–519, 2002.
P. W. Shor, “Algorithms for Quantum Computation: Discrete Log and Factoring”, SIAM Journal of Computing, Vol. 26, No. 5, 1414–1509, 1997.
B. Vöcking, “How Asymmetry Helps Load Balancing,” Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, 131–140, 1999.
Author information
Authors and Affiliations
Imai Quantum Computation and Information Project, ERATO, Japan Sci. and Tech. Corp., 406, Iseya-cho, Kamigyo-ku, Kyoto, 602-0873, Japan
Kazuo Iwama, Akinori Kawachi & Shigeru Yamashita
Graduate School of Informatics, Kyoto University Yoshida Honmachi, Sakyo-ku, Kyoto, 606-8501, Japan
Kazuo Iwama & Akinori Kawachi
- Kazuo Iwama
You can also search for this author inPubMed Google Scholar
- Akinori Kawachi
You can also search for this author inPubMed Google Scholar
- Shigeru Yamashita
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Department of Computer Science, University of Texas at Austin, One University Station, C0500, Austin, TX, 78712, USA
Tandy Warnow
Department of Computer Science, Montana State University, EPS 357, Bozeman, MT, 59717, USA
Binhai Zhu
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Iwama, K., Kawachi, A., Yamashita, S. (2003). Quantum Sampling for Balanced Allocations. In: Warnow, T., Zhu, B. (eds) Computing and Combinatorics. COCOON 2003. Lecture Notes in Computer Science, vol 2697. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45071-8_32
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-40534-4
Online ISBN:978-3-540-45071-9
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative