Presentation	2001/11/9 Quantum Algolithms for Occupancy Problem Akinori KAWAUCHI, Shigeru YAMASHITA, Kazuo IWAMA,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	When we put N balls N bins uniformally at randam, we obtain the highest bin which contains (*⊝)()balls with high probability. This problem has a proactical meaning such as load balancing. In this paper, we investigate to use a quantum sampling for this problem, based on Grover's quantum searching algorithm. We show that our quantum algorithm creates a bin which has Ω() balls with higt probability. However, it is known that the highest bin contains only O(ln ln N)if we choose two bins at random for each ball and put it into the one which is less full. This simple randomized algorithm significantly outperforms the quantum algorithm.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Occupancy problem / Load balancing / Quantum computing / Grover's algorithm
Paper #	CONP 2001-56
Date of Issue

Conference Information
Committee	COMP
Conference Date	2001/11/9(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Quantum Algolithms for Occupancy Problem
Sub Title (in English)
Keyword(1)	Occupancy problem
Keyword(2)	Load balancing
Keyword(3)	Quantum computing
Keyword(4)	Grover's algorithm
1st Author's Name	Akinori KAWAUCHI
1st Author's Affiliation	Graduate School of Informatics, Kyoto University:Quantum Computation and Information Project, ERATO, Japan Science and Technology Corporation()
2nd Author's Name	Shigeru YAMASHITA
2nd Author's Affiliation	NTT Communication Science Laboratories:Quantum Computation and Information Project, ERATO, Japan Science and Technology Coporation
3rd Author's Name	Kazuo IWAMA
3rd Author's Affiliation	Graduate School of Informatics, Kyoto University:Quantum Computation and Information Project, ERATO, Japan Science and Technology Coporation
Date	2001/11/9
Paper #	CONP 2001-56
Volume (vol)	vol.101
Number (no)	431
Page	pp.pp.-
#Pages	6
Date of Issue