Why Quantum Computing does not Offer a Computational Speedup When Performing Addition

International Journal of Computer Science (IJCS Journal) Published by SK Research Group of Companies (SKRGC) Scholarly Peer Reviewed Research Journals

Format: Volume 1, Issue 2, No 4, 2013.

Copyright: All Rights Reserved ©2013

Year of Publication: 2013

Author: Ricardo B. Verschueren,Dr. Amina Basiouny Mousa Elshamly

Reference:IJCS-023

View PDF Format

Abstract

Quantum computing is used to solve complex computational problems. This solutions are based on addition, therefore addition is so often performed by a computer, although it is a simple to compute task, it is questioned whether a quantum computer can perform addition faster than its classical counterpart. The finding of this paper is: Classical and Quantum addition are both linear in performance. Quantum computation can be more efficient through a paradigm shift based on the quantum phenomena of state discrimination/distinguishability to computer with a higher number base.

References

1. Deutsch, D. and R. Jozsa, Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992. 439(1907): p. 553-558. 2. Grover, L.K. A fast quantum mechanical algorithm for database search. in Proceedings of the 28th Annual ACM Symposium on Theory of Computing. 1996. ACM. 3. Shor, P.W. Algorithms for quantum computation: discrete logarithms and factoring. in Proceedings of the 35th Symposium on Foundations of Computer Science. 1994. Los Alamitos: IEEE. 4. Feynman, R.P., Simulating physics with computers. International journal of theoretical physics, 1982. 21(6): p. 467-488. 5. Deutsch, D., Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1985. 400(1818): p. 97-117. 6. Barenco, A.E., A. Sanpera, A. & Machiavello, C. A Short Introduction to Quantum Computation. 1996 30 June2012; Available from: http://www.qubit.org/tutorials/25-quantum-computing.html. 7. Duwell, A., The Many‐Worlds Interpretation and Quantum Computation. Philosophy of Science, 2007. 74(5): p. 1007-1018. 8. Audenaert, K.M.R., M. Mosonyi, and F. Verstraete, Quantum state discrimination bounds for finite sample size. Arxiv preprint arXiv:1204.0711, 2012. 9. Bae, J. and W.-Y. Hwang, Minimum-error discrimination of qubit states: Methods, solutions, and properties. Physical Review A, 2013. 87(1): p. 012334. 10. Bergou, J.A., U. Futschik, and E. Feldman, Optimal Unambiguous Discrimination of Pure Quantum States. Physical review letters, 2012. 108(25): p. 250502. 11. Chefles, A., Quantum state discrimination. Contemporary Physics, 2000. 41(6): p. 401-424. 12. Dieks, D., Overlap and distinguishability of quantum states. Physics Letters A, 1988. 126(5-6): p. 303-306. 13. ROSELL, M., et al., Classical Computing in Nuclear Magnetic Resonance. 2010. 14. Barbosa, G.A., Quantum half-adder. Physical Review A, 2006. 73(5): p. 052321.


Keywords

Finite state adder, Computational complexity, Quantum computing.

This work is licensed under a Creative Commons Attribution 3.0 Unported License.   

TOP
Facebook IconYouTube IconTwitter IconVisit Our Blog