Квантовый алгоритм, предложенный Шором для решения этой «не решаемой» традиционными методами задачи, оказался гораздо эффективнее. Он предполагает выполнение всего 1 000
Неудивительно, что алгоритм Шора стал довольно удачной рекламной акцией. С подачи американского математика «раскрутка» нового метода пошла столь успешно, что 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 кубитов — 2
Таким образом, квантовый компьютер с 1 000 кубитами в своей оперативной памяти может содержать 2
Специалисты считают, что, научившись управлять всего 1 000 кубитами, можно создать полномасштабный квантовый компьютер и достичь существенного ускорения вычислительного процесса. На первый взгляд 1 000 кубитов — не так много, если сравнивать это число с количеством транзисторов (сотни миллионов), которые содержат процессоры современных классических компьютеров. Однако пока наибольшим объявленным достижением в квантовых вычислениях является возможность управлять всего лишь пятью–семью кубитами.
Ловушки для ионов
Сразу условимся: поскольку реально действующий квантовый компьютер до сих пор не создан (по крайней мере, открыто об этом никем не заявлено), имеет смысл говорить лишь о возможных путях его реализации, которые рассматриваются и разрабатываются в различных лабораториях мира, в том числе и в российских. У нас в стране активно этими исследованиями занимаются в Физико-технологическом институте Российской академии наук, возглавляемом академиком РАН К.А. Валиевым, поделившимся с нами своими мыслями по данному поводу.
Теоретических и экспериментальных моделей квантового компьютера предложено достаточно много. Процесс вычислений в них происходит за счет управления квантовой динамикой отдельных атомов (кубитов), осуществляемого подачей на них внешних сигналов.
Одна из моделей — компьютер на ионах в ловушке — основана на использовании так называемых «подвешенных» в вакууме ионов. Кубитом в этом случае служит атом или ион. Его изолируют с помощью электромагнитного поля и «обстреливают» лазерными импульсами. Каждый кубит удален от соседей на несколько микрон, имеет определенное пространственное положение, поэтому на нем не сложно сфокусировать лазерный луч, который подается импульсами и меняет состояние атома. Сегодня ученые
