Как часто случается в физике, плодотворные результаты достигаются после сочетания двух поначалу не связанных идей. Здесь мы обсудим такое сочетание: объединение квантовой механики и теории компьютеров. Вместе они порождают новый объект – квантовый компьютер, который начал определяться и искать путь к реальности, хотя этот долгий путь представляется пока грубо. Идея квантового компьютера проста. В исправно функционирующем обыкновенном компьютере
${ }^{1}$ IBM Research Division, Thomas J. Watson Research Center, Post Office Box 218, York-town Heightsm, NY 10598, USA.
(C) Science. vol. 270, 1995.
Перевод О. В. Павловского.
все биты в любой момент времени находятся в определенном состоянии, скажем $01110010 \ldots$, Состонние квантового компьютера может быть описано волновой функцией, представимой в виде
\[
\Psi=a|01110010 \ldots\rangle+b|11101010 \ldots\rangle+\ldots
\]

Коэффициенты $a, b, \ldots$ – комплексные числа, причем вероятность того, что компьютер находится в состоянии $01110010 \ldots$ равна $|a|^{2}$, а того, что он находится в состоянии $11101010 \ldots$ равна $|b|^{2}$, и так далее. Однако описание состояния компьютера с помощью волновой функции не ограничивается просто предположением о неопределенности отдельных состояний, которые описываются с помощью вероятностей. Существенное значение имеют фазы комплексных коэффициентов $a, b, \ldots$ Они описывают интерференцию между отдельными состояниями компьютера, которая оказывается чрезвычайно полезной при вычислениях. Волновая функция говорит, что компьютер существует сразу во всех состояниях одновременно. Если же будет произведено измерение, выделяющее определенное состояние, то оно будет наблюдаться с соответствующей ему вероятностью.

Сейчас не существует компьютера, который хорошо описывался бы такой волновой функцией, современные вычислительные машины в точности удовлетворяет условиям классической физики. Но если когданибудь размеры компьютерных битов сократятся до атомных размеров, то квантовое описание состояния битов и динамики компьютеров может оказаться полезным. Фейнман обсуждал эту возможность в 1985 году и оптимистически заметил [1]: «Кажется, что законы физики не будут препятствовать уменьшению размеров компьютеров до тех пор, пока они не достигнут размеров атомов, тогда квантовое поведение будет уже оказывать доминирующее влияние». В этой статье мы в первую очередь обсудим основу оптимизма Фейнмана, опирающегося на тот факт, что квантовый аналог компьютерных «гейтов» можно осуществить в рамках хорошо изученной (но весьма сложной) экспериментальной физики. Мы также обсудим то, чего Фейнман не знал, а именно: умело используя квантовую динамику для создания конструктивной или деструктивной интерференции, можно создавать удивительно мощные вычислительные алгоритмы, как факторизующий алгоритм Шора [2]. Зародыш этой идеи появился в 1985 году в работе Дойча [3]. Дойч показал, что квантовая механика уничтожает один из самых заветных принципов науки о компьютерах – принцип однозначности вычислительной сложности любой математической проблемы. Со времен работ Тьюринга [4] считалось, что ответ на вопрос, будет ли данная задача решена за время, полиномиально зависящее от размеров исходных данных или за большее время, не зависит от физической аппаратуры, на которой эта задача решается. Этот принцип кажется вполне справедливым для всех вычислительных машин, оперирующих принципами классической физики, но квантовые компьютеры могут решать за полиномиальное время задачи, которые требуют большего времени на любой классической машине.