Why Quantum Computing does not Offer a Computational Speedup When Performing Addition
International Journal of Computer Science (IJCS) Published by SK Research Group of Companies (SKRGC).
Download this 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 June 2012; Available from: https://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
