Неудивительно, что алгоритм Шора стал довольно удачной рекламной акцией. С подачи американского математика «раскрутка» нового метода пошла столь успешно, что 1994 год стал началом великого бума на квантовые компьютеры. Исследовательские группы из США, Европы, Японии и специально созданные подразделения крупнейших IT-корпораций начали активную работу сразу в нескольких направлениях. Одни ученые занялись поиском способов практической реализации «компьютера будущего», другие продолжили поиски новых областей применения, отличных от решения чисто квантовых задач и дешифровки секретных сообщений.
Спасти коммивояжераПомимо задачи факторизации Шора, в которой достигается колоссальный выигрыш во времени, имеются и другие примеры «ускоренного» решения хорошо известных задач. Одна из них — так называемая «универсальная задача перебора». Предположим, необходимо отыскать номер телефона, записанный произвольным образом на одном из 10 000 лежащих в аккуратной стопке листов. Чтобы найти нужный, возможно, потребуется последовательно пересмотреть всю стопку, то есть произвести 10 000 операций. Один из простейших квантовых алгоритмов — алгоритм американского математика Лова Гровера, предложенный в 1997 году, позволяет справиться с этим вопросом с гораздо меньшими затратами: нужное количество операций оказывается пропорционально всего лишь квадратному корню из числа возможных вариантов. Если вариантов 10 000, то потребуется 100 попыток.
Аналогичным образом можно ускорить решение еще одной довольно трудоемкой задачи — о коммивояжере, состоящей в отыскании кратчайшего маршрута неутомимого ходока, последовательно посещающего ряд городов. Кстати, квантовый алгоритм Гровера позволяет не только ускорить процесс, но и примерно вдвое увеличить число параметров, учитываемых при выборе оптимального решения. Решение этой задачи имеет самое непосредственное отношение к нашей жизни и стоимости товаров массового потребления, поскольку в конечную цену входят и транспортные расходы по доставке в магазин. Минимизация транспортных издержек — классическая задача коммивояжера.
Достаточно быстро появились и обещанные Фейнманом квантовые алгоритмы для моделирования поведения квантовомеханических систем, главная сфера приложения которых — квантовая химия и непосредственно расчет свойств химических и биохимических соединений и молекул.
Перспективы применения квантовых вычислений часто связывают и с так называемой NP-полной проблемой, очерчивающей круг задач, для которых очень трудно найти решение, но достаточно просто проверить его правильность. Такие задачи часто относятся к классу невычислимых в том смысле, что они не могут быть решены на классических компьютерах за время, пропорциональное некоторой степени числа битов, представляющих задачу. Сегодня невозможно точно определить круг всех вопросов, решение которых может быть получено с помощью квантовых алгоритмов и компьютеров. И это связано не только с отсутствием последних, но и с тем, что квантовая информатика находится в самом начале своего развития.
Системные суперпозицииЗа счет чего же столь эффективны квантовые вычисления? Как известно, в классических компьютерах мы имеем дело с ячейками памяти и элементами логики, которые содержат бит информации, находящийся в одном из двух состояний — «0» или «1». Соответствовать этим состояниям может, к примеру, низкое или высокое напряжение на выходе транзистора. Вычислительный регистр классического компьютера в каждый момент времени описывается только одной комбинацией из N битов, причем состояние каждого бита однозначно определено: «0» или «1».