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


View PDF Format


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.


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.


Finite state adder, Computational complexity, Quantum computing.

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

Facebook IconYouTube IconTwitter IconVisit Our Blog