Hostname: page-component-6bf8c574d5-xtvcr Total loading time: 0 Render date: 2025-02-21T03:52:10.800Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantum algorithmic methods for computational geometry

Published online by Cambridge University Press:  08 November 2010

MARCO LANZAGORTA  and
JEFFREY UHLMANN
MARCO LANZAGORTA
Affiliation:
Advanced Information Systems, ITT Corporation, Alexandria, Virginia 22303, U.S.A. Email: marco.lanzagorta@itt.com
JEFFREY UHLMANN
Affiliation:
Department of Computer Science, University of Missouri-Columbia, Columbia, Missouri 65211, U.S.A. Email: uhlmannj@missouri.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we develop novel quantum algorithms based on Quantum Multi-Object Search (QMOS) for convex hulls and general object intersection reporting, with applications to computer graphics. These algorithms are developed and described using standard concepts from computer science by encapsulating the physics of quantum computation within black-box subroutines.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Special Issue 6: Quantum Algorithms , December 2010 , pp. 1117 - 1125
Copyright
Copyright © Cambridge University Press 2010

References

Andersson, A. and Swanson, K. (1997) On the difficulty of range searching. Computational Geometry with Applications 8 (3)115–122.Google Scholar
Boyer, M., Brassard, G., Hoyer, P. and Tapp, A. (1996) Tight bounds on quantum searching. Proceedings of the Fourth Workshop on Physics and Computation.Google Scholar
Brassard, G., Hoyer, P., Mosca, M. and Tapp, A. (2000) Quantum amplitude amplification and estimation. e-print quant-ph/0005055.Google Scholar
Nielsen, M. A. and Chuang, I. L. (2000) Quantum Computation and Quantum Information, Cambridge University Press.Google Scholar
Preparata, F. P. and Shamos, M. I. (1985) Computational Geometry, Springer-Verlag.CrossRefGoogle Scholar