Marco Lanzagorta
ABSTRACT
Quantum computing (QC) has become an important area of research in computer science because of its potential to provide more efficient algorithmic solutions to certain problems than are possible with classical computing (CC). In particular, QC is able to exploit the special properties of quantum superposition to achieve computational parallelism beyond what can be achieved with parallel CC computers. However, these special properties are not applicable for general computation. Therefore, we propose the use of "hybrid quantum computers" (HQCs) that combine both classical and quantum computing architectures in order to leverage the benefits of both. We demonstrate how an HQC can exploit quantum search to support general database operations more efficiently than is possible with CC. Our solution is based on new quantum results that are of independent significance to the field of quantum computing. More specifically, we demonstrate that the most restrictive implications of the quantum No-Cloning Theorem can be avoided through the use of semiclones. In this paper we discuss specific applications of quantum search to problems in computational geometry, simulation, and computer graphics.
- A. Andersson and K. Swanson. On the difficulty of range searching. Computational Geometry with Applications, 8(3):115--122, 1997. Google Scholar
Digital Library
- H. Bechmann-Pasquinucci and N. Gisin. Incoherent and coherent eavesdropping in the six-state protocol of quantum cryptography. Physical Review A, 59(4238), 1999.Google Scholar
- M. Boyer, G. Brassard, P. Hoyer, and A. Tapp. Tight bounds on quantum searching. Proceedings of the Fourth Workshop on Physics and Computation, 1996.Google Scholar
- G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. e-print quant-ph/0005055, 2000.Google Scholar
- V. Buzek and M. Hillery. Quantum copying: Beyond the no-cloning theorem. Physical Review A, 54(1844), 1996.Google Scholar
- V. Buzek and M. Hillery. Quantum copying: A network. e-print quant-ph/9703046, 1997.Google Scholar
- V. Buzek and M. Hillery. Universal optimal cloning of arbitrary quantum states: From qubits to quantum registers. Physical Review Letters, 81(22), 1998.Google ScholarCross Ref
- C. S. Calude, M. J. Dinneen, and K. Svozil. Reflections on quantum computing. Complexity, 6(1):35--37, 2000. Google ScholarDigital Library
- M. F. Cohen and J. R. Wallace. Radiosity and Realistic Image Synthesis. Morgan Kauffman, 1993. Google ScholarDigital Library
- C. Durr and P. Hoyer. A quantum algorithm for finding the minimum. e-print quant-ph/9607014, 1999.Google Scholar
- C. H. Bennet et. al. Strengths adn weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510--1524, Oct 1997. Google ScholarDigital Library
- J. D. Foley, A. Van Dam, S. K. Feiner, and J. F. Hughes. Computer Graphics, Principles and Practice. Addison Wesley, 1996. Google ScholarDigital Library
- E. Galvao and L. Hardy. Cloning and quantum computation. Physical Review A, 62(022301), 2000.Google Scholar
- A. Glassner. An Introduction to Ray Tracing. Academic Press, 1989. Google ScholarDigital Library
- A. Glassner. Andrew glassner's notebook: Quantum computing, part 1. IEEE Computer Graphics with Applications, 21(4), Jul/Aug 2001. Google ScholarDigital Library
- A. Glassner. Andrew glassner's notebook: Quantum computing, part 2. IEEE Computer Graphics with Applications, 21(5), Sep/Oct 2001. Google ScholarDigital Library
- A. Glassner. Andrew glassner's notebook: Quantum computing, part 3. IEEE Computer Graphics with Applications, 21(6), Nov/Dec 2001. Google ScholarDigital Library
- L. Grover. A fast quantum mechanical algorithm for database search. Proc. of 28th ACM Annual STOC, pages 212--219, 1996. Google ScholarDigital Library
- D. E. Knuth. The Art of Computer Programming Vol. 3: Sorting and Searching. Addison Wesley Longman, 1998. Google ScholarDigital Library
- M. Lanzagorta and J. Uhlmann. Quantum computational geometry. In Proceedings of the Quantum Information and Quantum Computation Conference. SPIE Defense and Security Symposium, 2004.Google ScholarCross Ref
- M. Lanzagorta and J. Uhlmann. Hybrid quantum computing. In Proceedings of the Quantum Information and Quantum Computation Conference. SPIE Defense and Security Symposium, 2005.Google Scholar
- M. Lanzagorta, J. Uhlmann, and R. Gomez. Quantum rendering. In Proceedings of the Quantum Information and Quantum Computation Conference. SPIE Defense and Security Symposium, 2003.Google ScholarCross Ref
- D. Luebke, M. Reddy, J. D. Cohen, A. Varshney, B. Watson, and R. Huebner. Level of Detail for 3D Graphics. Morgan Kauffman, 2002. Google ScholarDigital Library
- K. Murayama and P. L. Knight. Quantum state restoration by quantum cloning and measurement. e-print quant-ph/0309167, 2003.Google Scholar
- M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google ScholarDigital Library
- F. P. Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag, 1985. Google ScholarDigital Library
- P. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52(2493), 1995.Google Scholar
- R. Werner. Optimal cloning of pure states. Physical Review A, 58(1827), 1998.Google Scholar
- W. Wooters and W. Zurek. A single quantum cannot be copied. Nature, 299(802), 1982.Google Scholar
Recommendations
New applications of quantum algorithms to computer graphics: the quantum random sample consensus algorithm
CF '09: Proceedings of the 6th ACM conference on Computing frontiersThe 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. ...
Visualization of the Quantum Fourier Transform Using a Quantum Computer Simulator
The quantum Fourier transform (QFT) is a key subroutine of quantum algorithms for factoring and simulation and is the heart of the hidden-subgroup problem, the solution of which is expected to lead to the development of new quantum algorithms. The QFT ...
A Symbolic Classical Computer Language for Simulation of Quantum Algorithms
QI '09: Proceedings of the 3rd International Symposium on Quantum InteractionQuantum computing is an extremely promising research combining theoretical and experimental quantum physics, mathematics, quantum information theory and computer science. Classical simulation of quantum computations will cover part of the gap between ...
Comments