Квантовый алгоритм, предложенный Шором для решения этой «не решаемой» традиционными методами задачи, оказался гораздо эффективнее. Он предполагает выполнение всего 1 0003 , то есть миллиарда квантовых операций, и автоматически переводит данную задачу в разряд почти тривиальных. Специалисты по вопросам компьютерной безопасности быстро оценили алгоритм Шора, позволяющий без особого труда взламывать большинство современных криптосистем. Дело в том, что стойкость многих систем шифрования информации основана именно на невозможности быстрого разложения многоразрядного числа на простые сомножители. В первую очередь это касается систем шифрования, использующих два вида ключей: открытый (не требующий хранения втайне) и закрытый (секретный). Один используют для шифрования сообщения, другой — для дешифровки. При организации секретного канала связи отправитель и получатель обмениваются открытыми ключами своих криптосистем и далее шифруют свои послания с помощью открытого ключа получателя. Ключи взаимосвязаны между собой. Открытый ключ по сути является произведением двух очень больших простых чисел. Поэтому, разложив его на простые множители, можно легко восстановить закрытый, вот только «легко разложить на множители» пока не получается.
Неудивительно, что алгоритм Шора стал довольно удачной рекламной акцией. С подачи американского математика «раскрутка» нового метода пошла столь успешно, что 1994 год стал началом великого бума на квантовые компьютеры. Исследовательские группы из США, Европы, Японии и специально созданные подразделения крупнейших IT-корпораций начали активную работу сразу в нескольких направлениях. Одни ученые занялись поиском способов практической реализации «компьютера будущего», другие продолжили поиски новых областей применения, отличных от решения чисто квантовых задач и дешифровки секретных сообщений.
Спасти коммивояжера
Помимо задачи факторизации Шора, в которой достигается колоссальный выигрыш во времени, имеются и другие примеры «ускоренного» решения хорошо известных задач. Одна из них — так называемая «универсальная задача перебора». Предположим, необходимо отыскать номер телефона, записанный произвольным образом на одном из 10 000 лежащих в аккуратной стопке листов. Чтобы найти нужный, возможно, потребуется последовательно пересмотреть всю стопку, то есть произвести 10 000 операций. Один из простейших квантовых алгоритмов — алгоритм американского математика Лова Гровера, предложенный в 1997 году, позволяет справиться с этим вопросом с гораздо меньшими затратами: нужное количество операций оказывается пропорционально всего лишь квадратному корню из числа возможных вариантов. Если вариантов 10 000, то потребуется 100 попыток.
Аналогичным образом можно ускорить решение еще одной довольно трудоемкой задачи — о коммивояжере, состоящей в отыскании кратчайшего маршрута неутомимого ходока, последовательно посещающего ряд городов. Кстати, квантовый алгоритм Гровера позволяет не только ускорить процесс, но и примерно вдвое увеличить число параметров, учитываемых при выборе оптимального решения. Решение этой задачи имеет самое непосредственное отношение к нашей жизни и стоимости товаров массового потребления, поскольку в конечную цену входят и транспортные расходы по доставке в магазин. Минимизация транспортных издержек — классическая задача коммивояжера.
Достаточно быстро появились и обещанные Фейнманом квантовые алгоритмы для моделирования поведения квантовомеханических систем, главная сфера приложения которых — квантовая химия и непосредственно расчет свойств химических и биохимических соединений и молекул.
Перспективы применения квантовых вычислений часто связывают и с так называемой NP-полной проблемой, очерчивающей круг задач, для которых очень трудно найти решение, но достаточно просто проверить его правильность. Такие задачи часто относятся к классу невычислимых в том смысле, что они не могут быть решены на классических компьютерах за время, пропорциональное некоторой степени числа битов, представляющих задачу. Сегодня невозможно точно определить круг всех вопросов, решение которых может быть получено с помощью квантовых алгоритмов и компьютеров. И это связано не только с отсутствием последних, но и с тем, что квантовая информатика находится в самом начале своего развития.
Системные суперпозиции
За счет чего же столь эффективны квантовые вычисления? Как известно, в классических компьютерах мы имеем дело с ячейками памяти и элементами логики, которые содержат бит информации, находящийся в одном из двух состояний — «0» или «1». Соответствовать этим состояниям может, к примеру, низкое или высокое напряжение на выходе транзистора. Вычислительный регистр классического компьютера в каждый момент времени описывается только одной комбинацией из N битов, причем состояние каждого бита однозначно определено: «0» или «1».
В квантовом компьютере элементарной единицей информации является квантовый бит, или
кубит (его роль может выполнять атом или любой другой квантовый объект), а поведение системы кубитов — вычислительного регистра — определяется законами квантовой механики. Кубит тоже может принимать «пограничные» логические состояния, соответствующие, к примеру, двум уровням энергии атома и обозначаемые как I0〉 или I1〉. Но он способен находиться и в «суперпозиции» этих состояний, то есть (с определенной долей вероятности) в каждом из них одновременно. Наглядно совокупность состояний кубита иногда изображают множеством точек на поверхности сферы, находящихся между ее южным и северным полюсами — «0» и «1».
Кубиты обладают и другими удивительными свойствами квантовых объектов: иногда между парой кубитов возникают так называемые сцепленные (связанные между собой) состояния. В этом случае, изменяя состояние одного, можно управлять состоянием другого.
Классический регистр, например, состоящий из трех битов, содержит в каждый момент времени только одно из восьми возможных значений: 000, 001, 010, 011, 100, 101, 110, 111, в то время как квантовый регистр может одновременно хранить все эти восемь чисел. Если мы будем добавлять кубиты в регистр, то его объем будет увеличиваться экспоненциально — 3 кубита могут хранить 8 различных чисел, 4 кубита — 16, N кубитов — 2N чисел одновременно. Причем над всеми числами сразу можно произвести некие математические операции.
Таким образом, квантовый компьютер с 1 000 кубитами в своей оперативной памяти может содержать 21 000 или примерно 10300 комбинаций нулей и единиц, что значительно превышает возможности самых современных суперкомпьютеров с терабайтами (1012 ) оперативной памяти.
Специалисты считают, что, научившись управлять всего 1 000 кубитами, можно создать полномасштабный квантовый компьютер и достичь существенного ускорения вычислительного процесса. На первый взгляд 1 000 кубитов — не так много, если сравнивать это число с количеством транзисторов (сотни миллионов), которые содержат процессоры современных классических компьютеров. Однако пока наибольшим объявленным достижением в квантовых вычислениях является возможность управлять всего лишь пятью–семью кубитами.
Ловушки для ионов
Сразу условимся: поскольку реально действующий квантовый компьютер до сих пор не создан (по крайней мере, открыто об этом никем не заявлено), имеет смысл говорить лишь о возможных путях его реализации, которые рассматриваются и разрабатываются в различных лабораториях мира, в том числе и в российских. У нас в стране активно этими исследованиями занимаются в Физико-технологическом институте Российской академии наук, возглавляемом академиком РАН К.А. Валиевым, поделившимся с нами своими мыслями по данному поводу.
Теоретических и экспериментальных моделей квантового компьютера предложено достаточно много. Процесс вычислений в них происходит за счет управления квантовой динамикой отдельных атомов (кубитов), осуществляемого подачей на них внешних сигналов.
Одна из моделей — компьютер на ионах в ловушке — основана на использовании так называемых «подвешенных» в вакууме ионов. Кубитом в этом случае служит атом или ион. Его изолируют с помощью электромагнитного поля и «обстреливают» лазерными импульсами. Каждый кубит удален от соседей на несколько микрон, имеет определенное пространственное положение, поэтому на нем не сложно сфокусировать лазерный луч, который подается импульсами и меняет состояние атома. Сегодня ученые научились «подвешивать» несколько атомов в виде линейной цепочки, образующей одномерный ионный кристалл. Правда, больших кристаллов получить пока не удается, рекорд на сегодняшний день — цепочка из 30 ионов. Больше всего экспериментов по квантовым вычислениям с использованием таких кристаллов предложили ученые Инсбрукского университета в Австрии, а осуществили — исследователи в Лос-Аламосской национальной лаборатории США.
