Журнал "Вокруг Света" №8 за 2005 года

Журнал Вокруг Света

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

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

по части как расшифровки чужих, так и укрепления собственных криптосистем.

Квантовый мир обещает подарки и обычным пользователям ПК, а также любителям компьютерных игр, интерактивного кино и электронных помощников — киборгов. Создание интеллектуальных систем, живо реагирующих на наши импульсы и желания, тоже невозможно без кардинального увеличения вычислительных мощностей электронных помощников. И быть может, уже к середине текущего века виртуальный мир станет не только похож на настоящий, но и заживет своей особой квантовой жизнью, активно взаимодействуя с нашим сознанием и имитируя не только простейшие ощущения, но и глубокие чувства.

Делите, Шор, делите!

В 1994 году американский математик Питер Шор совершил настоящий прорыв, написав для несуществующего квантового компьютера так называемый алгоритм факторизации, позволяющий разлагать на простые множители многоразрядные числа. Задача факторизации только на первый взгляд кажется безобидной. Для ее решения используют довольно примитивный, но единственно верный способ: деление заданного числа на простые числа, меньшие корня квадратного из самого числа. Количество необходимых математических действий при разложении сложного 1 000 значного числа достигает 21 000 , или приблизительно 10300 . Самый современный компьютер, способный произвести около 1015 операций в секунду, с таким числом управится не ранее чем за 10285 секунд — эта величина во много раз превышает возраст нашей Вселенной (ей, по мнению ученых, 15 млрд. лет, то есть всего 5х1017 секунд). Если к решению этой задачи подключить 10100 компьютеров, то и тогда ситуация мало изменится.

Квантовый алгоритм, предложенный Шором для решения этой «не решаемой» традиционными методами задачи, оказался гораздо эффективнее. Он предполагает выполнение всего 1 0003 , то есть миллиарда квантовых операций, и автоматически переводит данную задачу в разряд почти тривиальных. Специалисты по вопросам компьютерной безопасности быстро оценили алгоритм Шора, позволяющий без особого труда взламывать большинство современных криптосистем. Дело в том, что стойкость многих систем шифрования информации основана именно на невозможности быстрого разложения многоразрядного числа на простые сомножители. В первую очередь это касается систем шифрования, использующих два вида ключей: открытый (не требующий хранения втайне) и закрытый (секретный). Один используют для шифрования сообщения, другой — для дешифровки. При организации секретного канала связи отправитель и получатель обмениваются открытыми ключами своих криптосистем и далее шифруют свои послания с помощью открытого ключа получателя. Ключи взаимосвязаны между собой. Открытый ключ по сути является произведением двух очень больших простых чисел. Поэтому, разложив его на простые множители, можно легко восстановить закрытый, вот только «легко разложить на множители» пока не получается.

Неудивительно, что алгоритм Шора стал довольно удачной рекламной акцией. С подачи американского математика «раскрутка» нового метода пошла столь успешно, что 1994 год стал началом великого бума на квантовые компьютеры. Исследовательские группы из США, Европы, Японии и специально созданные подразделения крупнейших IT-корпораций начали активную работу сразу в нескольких направлениях. Одни ученые занялись поиском способов практической

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

Спасти коммивояжера

Помимо задачи факторизации Шора, в которой достигается колоссальный выигрыш во времени, имеются и другие примеры «ускоренного» решения хорошо известных задач. Одна из них — так называемая «универсальная задача перебора». Предположим, необходимо отыскать номер телефона, записанный произвольным образом на одном из 10 000 лежащих в аккуратной стопке листов. Чтобы найти нужный, возможно, потребуется последовательно пересмотреть всю стопку, то есть произвести 10 000 операций. Один из простейших квантовых алгоритмов — алгоритм американского математика Лова Гровера, предложенный в 1997 году, позволяет справиться с этим вопросом с гораздо меньшими затратами: нужное количество операций оказывается пропорционально всего лишь квадратному корню из числа возможных вариантов. Если вариантов 10 000, то потребуется 100 попыток.

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

Достаточно быстро появились и обещанные Фейнманом квантовые алгоритмы для моделирования поведения квантовомеханических систем, главная сфера приложения которых — квантовая химия и непосредственно расчет свойств химических и биохимических соединений и молекул.

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

Системные суперпозиции

За счет чего же столь эффективны квантовые вычисления? Как известно, в классических компьютерах мы имеем дело с ячейками памяти и элементами логики, которые содержат бит информации, находящийся в одном из двух состояний — «0» или «1». Соответствовать этим состояниям может, к примеру, низкое или высокое напряжение на выходе транзистора. Вычислительный регистр классического компьютера в каждый момент времени описывается только одной комбинацией из N битов, причем состояние каждого бита однозначно определено: «0» или «1».

В квантовом компьютере элементарной единицей информации является квантовый бит, или

кубит (его роль может выполнять атом или любой другой квантовый объект), а поведение системы кубитов — вычислительного регистра — определяется законами квантовой механики. Кубит тоже может принимать «пограничные» логические состояния, соответствующие, к примеру, двум уровням энергии атома и обозначаемые как I0 или I1. Но он способен находиться и в «суперпозиции» этих состояний, то есть (с определенной долей вероятности) в каждом из них одновременно. Наглядно совокупность состояний кубита иногда изображают множеством точек на поверхности сферы, находящихся между ее южным и северным полюсами — «0» и «1».