New applications of quantum algorithms to computer graphics: the quantum random sample consensus algorithm

ABSTRACT

The inherent parallelism of quantum systems determined not only the investigation of innovative applications that can be developed using these high performance computing systems, but also of ways to improve the performances over the classical case. Exploiting this parallelism recently led to the emergence of innovative ideas in the field of computer graphics, sketching the development of quantum rendering and quantum computational geometry. Following these tracks, we propose a new quantum algorithm for the RANdom SAmple Consensus (RANSAC) voting scheme. In this paper we show that by exploiting the unique features of quantum computing, generating uniform superpositions of states in the problem space and applying quantum operators to all states simultaneously, the performance of our quantum algorithm is orders of magnitude faster than the classical variant.

REFERENCES

• 1: G. Beach, C. Lomont, and C. Cohen. Quantum image processing (quip). In Proceedings of Applied Imagery Pattern Recognition Workshop, pages 39--44, 2003.
• 2: M. Boyer, G. Brassard, P. Hoyer, and A. Tapp. Tight bounds on quantum searching. In Proceedings of Fourth Workshop on Physics and Computation, 1996.
• 3: G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation, 2000. quant-ph/0005055.
• 4: V. Buzek, S. Braunstein, M. Hillery, and D. BruSS. Quantum copying: a network. A Physical Review, 56(5):3446--3452, 1997.
• 5: V. Buzek and M. Hillery. Quantum copying: Beyond the no-cloning theorem. A Physical Review, 54(3):1844--1852, 1996.
• 6: J. H. Cole, L. C. L. Hollenberg, and S. Prawer. An algorithm for simulating the ising model on a type-ii quantum computer. Computer Physics Communications, 161(1-2):18--26, 2004.
• 7: D. Curtis and D. A. Meyer. Towards quantum template matching. In Proceedings of the SPIE, volume 5161, pages 134--141, 2004.
• 8: C. Durr and P. Hoyer. A quantum algorithm for finding the minimum, 1999. quant-ph/9607014.
• 9: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 10: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 11: Richard Hartley , Andrew Zisserman, Multiple view geometry in computer visiond, Cambridge University Press, New York, NY, 2001
• 12: Marco Lanzagorta , Jeffrey K. Uhlmann, Hybrid quantum-classical computing with applications to computer graphics, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198723]
• 13: M. Lanzagorta and J.Uhlmann. Hybrid quantum computing: semicloning for general database retrieval. In Proceedings of the Quantum Information and Quantum Computation Conference, SPIE Defense and Security Symposium, volume 5815, pages 78--86, 2005.
• 14: M. Lanzagorta, J.Uhlmann, and R.Gomez. Quantum rendering. In Proceedings of the Quantum Information and Computation Conference, SPIE Defense and Security Symposium, volume 5105, pages 128--136, 2003.
• 15: N. David Mermin, Quantum Computer Science: An Introduction, Cambridge University Press, New York, NY, 2007
• 16: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 17: Harumichi Nishimura , Tomoyuki Yamakami, Polynomial time quantum computation with advice, Information Processing Letters, v.90 n.4, p.195-204, 31 May 2004 [doi>10.1016/j.ipl.2004.02.005]
• 18: David Nistér, Preemptive RANSAC for live structure and motion estimation, Machine Vision and Applications, v.16 n.5, p.321-329, December 2005 [doi>10.1007/s00138-005-0006-y]
• 19: J. Preskill. Quantum computation. on-line lecture notes, http://www.theory.caltech.edu/people/preskill/.
• 20: H. D. Raedt and K. Michielsen. Computational methods for simulating quantum computers, 2004. arXiv:quant-ph/0406210.
• 21: R. Schnabel, R. Wahl, and R. Klein. Efficient ransac for point-cloud shape detection. Computer Graphics Forum, 26(2):214--226, 2007.
• 22: P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, p.124-134, November 20-22, 1994 [doi>10.1109/SFCS.1994.365700]
• 23: P. H. S. Torr , D. W. Murray, The Development and Comparison of Robust Methodsfor Estimating the Fundamental Matrix, International Journal of Computer Vision, v.24 n.3, p.271-300, Sept./Oct. 1997 [doi>10.1023/A:1007927408552]
• 24: P. H. S. Torr and A. Zisserman. Robust parameterization and computation of the trifocal tensor. Image and Vision Computing, 15:591--605, 1997.
• 25: S. E. Venegas-Andraca and S. Bose. Quantum computation and image processing: New trends in artificial intelligence. In Proceedings of IJCAI'03, pages 1563--1564, 2003.
• 26: W. Wootters and W. Zurek. A single quantum cannot be cloned. Nature, 299:802--803, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
computer graphics, quantum algorithms, quantum computing, ransac