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

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

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

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

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

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

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

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

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