нообразие и уровень изложения затронутых тем даст читателю представление о серьезности нового направления в физике и математике.

Заметим, что поскольку этот сборник задуман как первый из серии по квантовым вычислениям, в него вошли лишь оптимистические статьи. Работы, посвященные описанию серьезных трудностей, стоящих на пути создания полноценных квантовых компьютеров (а такие трудности стояли на пути любого важного направления в науке) и путей их преодоления (здесь уже есть много блестящих теоретических и экспериментальных находок) составят содержание дальнейших сборников.

Равным образом предлагается собрать внутри одной обложки как классические работы по основаниям квантовой механики, квантовой логике и теории квантовых вычислений, так и современные исследования, представляющие собой серьезный вклад в развитие квантовых компьютеров.

Отметим некоторые особенности принятой в сборнике терминологии. В англоязычной литературе общепринят термин gate, который по-разному переводится на русский язык. В частности, используются такие обороты, как «логический элемент» или «вентиль». Мы позволили себе употребить слово гейт (в мужском роде), надеясь, что этот термин приживется в русском языке, как уже прижились слова «компьютер», «бит», «байт ... ». Нам кажется, что поддержку в таком употреблении слова гейт можно найти у Дойча (1989), определяющего гейт как компьютер: «in the classical theory of computation a logic gate is a computing machine whose input and output consist of fixed numbers of bits and which performs a fixed time that is independent of the input ... A quantum gate is defined in a similar way».

Далее, в последнее время широкое распространение получили термины «entangled», «entanglement» («quantum systems» или «quantum states»), которые в нашем компьютерном фольклоре чаще всего переводятся как «запутанный», «перепутанный» и т. д. Английское «entanglement» - это прямой перевод немецкого слова «Verschrankung», введенного Шредингером в 1935 году (Naturwissenschaften 23, 807-812 (1935)). По-немецки verschanken - это «складывать накрест». В сборнике термины «entangled», «entanglement» переведены как «скрещение», «скрещенный», чтобы избежать невольного придания смысла случайности при переводе соответствующих терминов словом «запутанный». Этого смысла не было у Шредингера.

Литература

С. Bennett. Logical reversing of computation. IBM Journal of research and development, 17, 525-532 (1973).

2] P. Benioff. The computer as a physical system: a microscopic quantum mechanical hamiltonian model of computation as reversed by Turing machines. Journal of Statistical Physics 22, 563-591 (1980).

3] R. Feynmann. Simulating physics with computers. International Journal of Theoretical Physics 21(6/7), 467-488 (1982).

4] D.Deutsch. Quantum theory, the Church-Turing principle and universal quantum computer. Proceedings Royal Society London, A400, 97-117 (1985).

5] D.Deutsch. Quantum computational networks. Proceedings Royal Society London, A425, 73-90 (1989).

6] D.Deutsch, R.Jozsa. Rapid solution of problems by quantum computation. Proceedings Royal Society London, A439, 553-558 (1992).

P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on foundations of computer science, 124-134 (1994).

Наконец, слово «wavelate», которое, несомненно, скоро приобретет популярность и в квантовых вычислениях, точно также звучит и в переводе - «вейвлет».

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

В. А. Садовничий

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

руководство

с. л. Браунштейн (Samuel L. Braunstein)

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

Тогда Вы думаете о квантовом компьютере.

Чтобы понять, что такое квантовый компьютер, требуется всего лишь несколько относительно простых понятий квантовой механики. Тонкость состоит в том, чтобы научиться работать с этими положениями. Является ли такой компьютер неизбежностью, или построить его будет слишком сложно?

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

Схематически описывается модель квантового компьютера, а также некоторые тонкости в его программировании. Алгоритм Шора [1, 2 эффективной факторизации чисел на квантовом компьютере представлен в двух частях: квантовая процедура внутри алгоритма и классический алгоритм, который требует квантовую процедуру. Обсуждается

Encyclopedia of Applied Physics, Update, WILEY-VCH, 1999. Перевод В. В. Белокурова.