Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T05:36:50.122Z 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: [email protected]
JEFFREY UHLMANN
Affiliation:
Department of Computer Science, University of Missouri-Columbia, Columbia, Missouri 65211, U.S.A. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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