publication . Article . Preprint . 2007

Quantum physics and computers

Adriano Barenco;
Open Access
  • Published: 25 Jun 2007 Journal: Contemporary Physics, volume 37, pages 375-389 (issn: 0010-7514, eissn: 1366-5812, Copyright policy)
  • Publisher: Informa UK Limited
Recent theoretical results confirm that quantum theory provides the possibility of new ways of performing efficient calculations. The most striking example is the factoring problem. It has recently been shown that computers that exploit quantum features could factor large composite integers. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. The additional power of quantum computers comes from the possibility of employing a superposition of states, of following many distinct computation paths and of producing a final output that depends on the interference of all of the...
Persistent Identifiers
free text keywords: General Physics and Astronomy, Quantum Physics, Interference (wave propagation), Computation, Computer science, Exploit, Integer, Factoring problem, Superposition principle, Quantum computer, Quantum mechanics, Quantum
32 references, page 1 of 3

[1] R. Landauer, IBM J. Res. Dev. 5, 183 (1961); C.H. Bennett, IBM J. Res. Dev. 17, 525 (1973); C.H. Bennett, Int. J. Theor. Phys. 21, 905 (1982); C.H. Bennett, SIAM J. Comput. 18(4), 766 (1989).

[2] D. Deutsch, D., Proc. R. Soc. London A 400, 97 (1985).

[3] P.W. Shor, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society Press, Los Alamitos, CA), p. 124 (1994).

[4] R. Rivest, A. Shamir, L. Adleman, On Digital Signatures and Public-Key Cryptosystems, MIT Laboratory for Computer Science, Technical Report, MIT/LCS/TR-212 (January 1979).

[5] D. Welsh, Codes and cryptography, Clarendon Press, Oxford, (1988). H. S. Wilf, Algorithms and complexity, Prentice-Hall, Englewood Cliffs / Prentice-Hall International, London, (1986).

[6] A.K. Lenstra, H.W. Lenstra Jr., M.S. Manasse, and J.M. Pollard, in Proc. 22nd ACM Symposium on the Theory of Computing, p.564 (1990).

[7] D.E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (Addison-Wesley, 1981).

[8] B. Schumacher, Phys. Rev. A 51, 2738 (1995).

[9] A.S. Holevo, Problemy Peredachi Informatsii, 9, 3 (1979) (this journal is translated by IEEE under the title Problems of Information Transfer ); E.B. Davies, IEEE Trans. Inform. Theory, IT 24, 596 (1978); C.A. Fuchs and C.M. Caves, Phys. Rev. Lett. 73, 3047 (1994).

[10] S. Wiesner, Sigact News 15(1), 78 (1983); C.H. Bennett and G. Brassard in Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India pp175, (IEEE, New York, 1984); A. Ekert, Phys. Rev. Lett. 71, 4287 (1993). For a review of the field, see also R.J. Hughes, D.M. Alde, P. Dyer, G.G. Luther, G.L. Morgan and M. Schauer, Contemporary Physics 36(3), 149 (1995); and also S.J.D. Phoenix and P.D. Townsend, Contemporary Physics 36(3), 165 (1995).

[11] C.H. Bennett, G. Brassard, C. Cr´epeau, R. Jozsa, A. Peres, and W.K. Wootters, Phys. Rev. Lett. 70, 1895 (1993).

[12] C.H. Bennett and S. Wiesner, Phys. Rev. Lett. 69, 2881 (1992).

[13] A. Peres, Quantum Theory: Concepts and Methods (Kluwer, 1993).

[14] G.H. Hardy and E.M. Wright: An Introduction to the Theory of Numbers (4th edition, Oxford University Press, 1965).

[15] G.L. Miller, Journal of Computer Science 13, 300 (1976);

32 references, page 1 of 3
Any information missing or wrong?Report an Issue