For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Quantum Algorithms for Intersection and Proximity Problems
Kunihiko SADAKANE Norito SUGAWARA Takeshi TOKUYAMA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
quantum algorithms, computational geometry, intersection, proximity, amplitude amplification,
Full Text: PDF(219.5KB)>>
We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al. 's amplitude amplification method, and analogous to Buhrman et al. 's algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.