17] А. Barenco, D. Deutsch and A. Ekert. Phys. Rev. Lett. 74, 4083 (1995).

18] T.Sleator and H. Weinfurter. Phys. Rev. Lett. 74, 4087 (1995).

19] D. Deutsch, A.Barenco and A. Ekert. Proc. Roy. Soc. Lond. A 449, 669 (1995).

20] S.Lloyd. Almost any quantum logic gate is universal Los Alamos National Laboratory preprint.

21] P. W. Shor, presented at Quantum Computation 1994, Villa Gualino, Turin, Italy, October 1994, unpublished.

22] D. P. DiVincenzo, private communication and work presented at Quantum Computation 1995, Villa Gualino, Turin, Italy, June 1995, unpublished.

23] D. Coppersmith. An approximate Fourier transform useful in quantum factoring, IBM Research Report RC19642 (1994).

24] R. Cleve. A note on computing Fourier transforms by quantum programs, unpublished.

25] Необходимо, чтобы дискретное преобразование Фурье обеспечило достаточное разрешение для выделения кратного обратному периоду из соотношения c/q. Это всегда возможно, если число битов к в первом квантовом регистре удовлетворяет неравенству = 2.

26] Так как период г неизвестен, мы требуем q = 2. Тогда преобразование Фурье обеспечивает на данном этапе вычислений достаточное разрешение [1,2

27] I. L. Chuang, R. Laflamme, P. Shor and W. H. Zurek. Quantum computers, factoring and decoherence, Report LA-UR-95-241 (1995).

28] R. Jozsa. Proc. R. Soc. Lond. A 435, 563 (1991).

29] D. Deutsch and R. Jozsa. Proc. R. Soc. Lond. A 439, 554 (1992).

30] A. C.-C.Yao. Quantum circuit complexity, preprint.

31] C.H.Bennett, E.Bernstein, G. Brassard and U. V. Vaz Irani. Strengths and weaknesses of quantum computing, preprint.

32] W.G.Unruh. Phys. Rev. A 51, 992 (1995). 33] S.Lloyd. Science 261, 1569 (1993).

34] J.I. Cirac and P. Zoller. Phys. Rev. Lett. 74, 4091 (1995).

35] T. Pellizzari, S.A.Gardiner, J.I. Cirac and P. Zoller. Decoherence, continuous observation and quantum computing: a cavity QED models preprint.

36] Q.A.Turchette, C.J.Hood, W.Lange, H.Mabuchi and H.J.Kimble.

Measurement of conditional phase shifts for quantum logic, Caltech preprint.

37] R. Hughes, presented at Quantum Computation 1995, Villa Gualino, Turin, Italy, June 1995, unpublished.

38] G. H. Hardy and E. M. Wright. An introduction to the theory of numbers. Oxford, Clarendon Press, 1979.

Квантовые вычисления

Давид П. ДиВинченцо (David Р. DiVincenzo)

Если когда-нибудь компьютерные биты уменьшатся до размеров отдельных атомов, квантово-механические эффекты могут сильно изменить саму природу вычислений. Волновая функция такого компьютера будет определять суперпозицию многих вычислительных процессов, выполняемых одновременно. Возникающий параллелизм может быть использован для эффективного решения многих вычислительных проблем, таких, как разложение большого целого числа на простые множители. Однако создание квантовых компьютеров предъявляет такие требования к экспериментальной реализации систем с высокой квантовой когерентностью, о каких пока можно только мечтать. В настоящее время экспериментальные возможности в атомной физике и в других областях науки позволяют осуществить только самые элементарные квантовые вычисления.

1. Введение

Как часто случается в физике, плодотворные результаты достигаются после сочетания двух поначалу не связанных идей. Здесь мы обсудим такое сочетание: объединение квантовой механики и теории компьютеров. Вместе они порождают новый объект - квантовый компьютер, который начал определяться и искать путь к реальности, хотя этот долгий путь представляется пока грубо. Идея квантового компьютера проста. В исправно функционирующем обыкновенном компьютере

-ШМ Research Division, Thomas J. Watson Research Center, Post Office Box 218, York-town Heightsm, NY 10598, USA. (c) Science, vol. 270, 1995. Перевод 0. В. Павловского.