Предпосылки создания квантовых компьютеров.

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

Сейчас ведутся разработки нового класса квантовых устройств - кванто­вых компьютеров. Идея кванто­вого компьютера возникла так.

Все началось в 1982 году, когда Фейнман написал очень интерес­ную статью [1], в которой рас­смотрел два вопроса. Он подошел к процессу вычисления как фи­зик: есть чисто логические огра­ничения на то, что можно вычис­лить (можно придумать задачу, для которой вообще нет алгорит­ма, можно придумать задачу, для которой любой алгоритм будет долго работать). А есть ли ограни­чения физические? Вот есть закон сохранения энергии - вечный двигатель невозможен; а есть ли какое-нибудь физическое огра­ничение на функционирование компьютера, которое накладыва­ет некие запреты на реализуемость алгоритмов? И Фейнман показал, что термодинамических ограни­чений, типа второго начала тер­модинамики, нет. Если мы будем уменьшать потери энергии, шумы, то мы можем сделать сколь угод­но длинные вычисления со сколь угодно малыми затратами энер­гии. Это означает, что вычисления можно сделать обратимым образом - потому что в необратимых про­цессах энтропия возрастает. Соб­ственно, Фейнмана это и заинте­ресовало: ведь реальное вычис­ление на реальном компьютере необратимо. И полученный им результат состоит в том, что мож­но так переделать любое вычис­ление - без особой потери эф­фективности, - чтобы оно стало обратимым. Те вычисления, кото­рые делаются «просто так», ко­нечно, необратимы, но «рост нео­братимости» пренебрежимо мал по сравнению, скажем, с шумами в современном компьютере. То есть необратимость - это тонкий эффект; тут вопрос не практичес­кий а принципиальный: если представить себе, что технология дойдет до такого уровня, что этот эффект станет существенным, то можно так перестроить вычисле­ния, чтобы добиться обратимости.

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

Кстати, Ю.И. Манин в конце семидесятых годов написал две популярные книжки по логике - «Вычислимое и невычислимое» и «Доказуемое и недоказуемое», и в одной из них есть сюжет про кван­товые автоматы, где он говорит о некоторых кардинальных отличи­ях этих автоматов от классических [2].

В середине восьмидесятых годов появились работы Дойча (D. Deutsch), Бернстайна и Вазирани (Е. Bernstein, U. Vazirani), Яo (A. Уао). В них были построены формальные модели квантового компьютера - напри­мер, квантовая машина Тьюринга [3-6].

Следующий этап - статья Шора (Р.W. Shor) 1994 года [7], вызвавшая лавинообразный рост числа публикаций о квантовых вы­числениях. Шор построил кван­товый (то есть реализуемый на квантовом компьютере) алгоритм факторизации (разложения це­лых чисел на множители - ис­пользуется в том числе для вскры­тия зашифрованных сообщений). Все известные алгоритмы для обычного компьютера - экспо­ненциальные (время их работы растет как экспонента от числа зна­ков в записи факторизуемого чис­ла). Факторизация 129-разряд­ного числа потребовала 500 MIPS-лет, или восемь месяцев непре­рывной работы системы из 1600 рабочих станций, объединенных через Интернет. А при числе раз­рядов порядка 300 это время су­щественно превзойдет возраст Вселенной - даже если работать одновременно на всех существующих в мире машинах. Считается (хотя это и не доказано!), что бы­строго алгоритма решения этой задачи не существует. Более того, гарантией надежности большин­ства существующих шифров яв­ляется именно сложность реше­ния задачи факторизации или од­ной из родственных ей теорети­ко-числовых задач, например - дискретного логарифма. И вдруг выясняется, что на квантовом ком­пьютере эта задача имеет всего лишь кубическую сложность! Пе­ред квантовым компьютером клас­сические банковские, военные и другие шифры мгновенно теряют всякую ценность. Короче говоря, работа Шора показала, что вся эта изысканная академическая дея­тельность непосредственно каса­ется такой первобытной стихии, как деньги. После этого и началась настоящая популярность .

Впрочем, выясняется, что не толь­ко классическая, но и квантовая криптография (наука о шифрова­нии сообщений) часто не способна противостоять квантовой криптоаналитике (науке о расшифровке). Некоторые важные криптографи­ческие протоколы, такие как «под­брасывание монеты по телефону», рушатся при переходе к квантовым вычислениям. Точнее, гарантией их надежности является отныне не сложность тех или иных алгорит­мов, а сложность задачи создания квантового компьютера.

Таким образом возникает новая отрасль вычислений – квантовые вычисления. Квантовые вычисления (КВ) - это, как можно догадаться, вычисле­ния на квантовом компьютере. Квантовых компьютеров на свете пока нет. Более того, до сих пор неясно, когда появятся практиче­ски полезные конструкции и поя­вятся ли вообще. Тем не менее, квантовые вычисления - пред­мет, чрезвычайно модный сейчас в математике и физике, как теоре­тической, так и эксперименталь­ной, и занимается им довольно много людей. Судя по всему, именно инте­рес стимулировал первопроход­цев - Ричарда Фейнмана, напи­савшего пионерскую работу, в ко­торой ставился вопрос о вычис­лительных возможностях уст­ройств на квантовых элементах; Дэвида Дойча, формализовавше­го этот вопрос в рамках современ­ной теории вычислений; и Питера Шора, придумавшего первый не­тривиальный квантовый алгоритм.

Типы квантовых компьютеров.

Строго говоря, можно выделить два типа квантовых ком­пьютеров. И те, и другие основаны на квантовых явлениях, только разного порядка.

Представителями первого типа являются, например, компьютеры, в основе которых лежит квантова­ние магнитного потока на наруше­ниях сверхпроводимости - Джозефсоновских переходах. На эф­фекте Джозефсона уже сейчас де­лают линейные усилители, аналого-цифровые преобразователи, СКВИДы и корреляторы. Известен проект создания RISC-процессора на RSFQ-логике (Rapid Single Flux Quantum). Эта же элементная база используется в проекте создания петафлопного (1015 оп./с) компью­тера. Экспериментально достиг­нута тактовая частота 370 ГГц, ко­торая в перспективе может быть доведена до 700 ГГц. Однако время расфазировки волновых функций в этих устройствах сопоставимо со временем переключения отдель­ных вентилей, и фактически на но­вых, квантовых принципах реали­зуется уже привычная нам элемент­ная база - триггеры, регистры и другие логические элементы.