Уже сейчас существует множество систем, в работе которых кванто¬вые эффекты играют существен¬ную роль. Одним из наиболее из¬вестных примеров может служить лазер: поле его излучения поро¬ждается квантово-механическими событиями - спонтанным и ин¬дуцированным излучением света. Другим важным примером таких систем являются современные микросхемы - непрерывное ужесточение проектных норм приводит к тому, что квантовые эффекты начинают играть в их поведении существенную роль. В диодах Ганна возникают осцил¬ляции электронных токов, в полу¬проводниках образуются слои¬стые структуры: электроны или дырки в различных запертых состояниях могут хранить информа¬цию, а один или несколько элек¬тронов могут быть заперты в так называемых квантовых ямах.
Сейчас ведутся разработки нового класса квантовых устройств - кванто¬вых компьютеров. Идея кванто¬вого компьютера возникла так.
Все началось в 1982 году, когда Фейнман написал очень интерес¬ную статью [1], в которой рас¬смотрел два вопроса. Он подошел к процессу вычисления как фи¬зик: есть чисто логические огра¬ничения на то, что можно вычис¬лить (можно придумать задачу, для которой вообще нет алгорит¬ма, можно придумать задачу, для которой любой алгоритм будет долго работать). А есть ли ограни¬чения физические? Вот есть закон сохранения энергии - вечный двигатель невозможен; а есть ли какое-нибудь физическое огра¬ничение на функционирование компьютера, которое накладыва¬ет некие запреты на реализуемость алгоритмов? И Фейнман показал, что термодинамических ограни¬чений, типа второго начала тер¬модинамики, нет. Если мы будем уменьшать потери энергии, шумы, то мы можем сделать сколь угод¬но длинные вычисления со сколь угодно малыми затратами энер¬гии. Это означает, что вычисления можно сделать обратимым образом - потому что в необратимых про¬цессах энтропия возрастает. Соб¬ственно, Фейнмана это и заинте¬ресовало: ведь реальное вычис¬ление на реальном компьютере необратимо. И полученный им результат состоит в том, что мож¬но так переделать любое вычис¬ление - без особой потери эф¬фективности, - чтобы оно стало обратимым. Те вычисления, кото¬рые делаются «просто так», ко¬нечно, необратимы, но «рост нео¬братимости» пренебрежимо мал по сравнению, скажем, с шумами в современном компьютере. То есть необратимость - это тонкий эффект; тут вопрос не практичес¬кий а принципиальный: если представить себе, что технология дойдет до такого уровня, что этот эффект станет существенным, то можно так перестроить вычисле¬ния, чтобы добиться обратимости.
И в этой же работе Фейнман об¬ратил внимание на то, что если у нас имеется устройство квантовое, то есть подчиняющееся законам кван¬товой механики, то его вычисли¬тельные возможности совершенно не обязательно должны совпадать с возможностями обычного устрой¬ства. Возникают некоторые допол¬нительные возможности. Но пока непонятно, позволяют они полу¬чить какой-то выигрыш или нет. Фактически, он и поставил своей статьей такой вопрос.
Кстати, Ю.И. Манин в конце семидесятых годов написал две популярные книжки по логике - «Вычислимое и невычислимое» и «Доказуемое и недоказуемое», и в одной из них есть сюжет про кван¬товые автоматы, где он говорит о некоторых кардинальных отличи¬ях этих автоматов от классических [2].
В середине восьмидесятых годов появились работы Дойча (D. Deutsch), Бернстайна и Вазирани (Е. Bernstein, U. Vazirani), Яo (A. Уао). В них были построены формальные модели квантового компьютера - напри¬мер, квантовая машина Тьюринга [3-6].
Следующий этап - статья Шора (Р.W. Shor) 1994 года [7], вызвавшая лавинообразный рост числа публикаций о квантовых вы¬числениях. Шор построил кван¬товый (то есть реализуемый на квантовом компьютере) алгоритм факторизации (разложения це¬лых чисел на множители - ис¬пользуется в том числе для вскры¬тия зашифрованных сообщений). Все известные алгоритмы для обычного компьютера - экспо¬ненциальные (время их работы растет как экспонента от числа зна¬ков в записи факторизуемого чис¬ла). Факторизация 129-разряд¬ного числа потребовала 500 MIPS-лет, или восемь месяцев непре¬рывной работы системы из 1600 рабочих станций, объединенных через Интернет. А при числе раз¬рядов порядка 300 это время су¬щественно превзойдет возраст Вселенной - даже если работать одновременно на всех существующих в мире машинах. Считается (хотя это и не доказано!), что бы¬строго алгоритма решения этой задачи не существует. Более того, гарантией надежности большин¬ства существующих шифров яв¬ляется именно сложность реше¬ния задачи факторизации или од¬ной из родственных ей теорети¬ко-числовых задач, например - дискретного логарифма. И вдруг выясняется, что на квантовом ком¬пьютере эта задача имеет всего лишь кубическую сложность! Пе¬ред квантовым компьютером клас¬сические банковские, военные и другие шифры мгновенно теряют всякую ценность. Короче говоря, работа Шора показала, что вся эта изысканная академическая дея¬тельность непосредственно каса¬ется такой первобытной стихии, как деньги. После этого и началась настоящая популярность...
Впрочем, выясняется, что не толь¬ко классическая, но и квантовая криптография (наука о шифрова¬нии сообщений) часто не способна противостоять квантовой криптоаналитике (науке о расшифровке). Некоторые важные криптографи¬ческие протоколы, такие как «под¬брасывание монеты по телефону», рушатся при переходе к квантовым вычислениям. Точнее, гарантией их надежности является отныне не сложность тех или иных алгорит¬мов, а сложность задачи создания квантового компьютера.
Таким образом возникает новая отрасль вычислений – квантовые вычисления. Квантовые вычисления (КВ) - это, как можно догадаться, вычисле¬ния на квантовом компьютере. Квантовых компьютеров на свете пока нет. Более того, до сих пор неясно, когда появятся практиче¬ски полезные конструкции и поя¬вятся ли вообще. Тем не менее, квантовые вычисления - пред¬мет, чрезвычайно модный сейчас в математике и физике, как теоре¬тической, так и эксперименталь¬ной, и занимается им довольно много людей. Судя по всему, именно инте¬рес стимулировал первопроход¬цев - Ричарда Фейнмана, напи¬савшего пионерскую работу, в ко¬торой ставился вопрос о вычис¬лительных возможностях уст¬ройств на квантовых элементах; Дэвида Дойча, формализовавше¬го этот вопрос в рамках современ¬ной теории вычислений; и Питера Шора, придумавшего первый не¬тривиальный квантовый алгоритм.