С тех пор, как Ричард Фейнман высказал идею о
возможности построения компьютера, принцип работы которого основан на квантовой механике, прошло
20 лет и все давно привыкли к словосочетаниям "квантовый компьютер", "квантовые вычисления" и
"квантовая криптография". Однако на сегодняшний день известно не так много задач, в решении которых
квантовый компьютер сможет продемонстировать свое преимущество в сравнении с компьютерами
классическими. На вопрос, почему это так, попытался ответить разработчик, пожалуй, наиболее
известного квантового алгоритма - Питер Шор.
Было предложено много различных способов "воплощения в железе" квантового компьютера,
основными из которых являются использование ядерного магнитного резонанса (ЯМР) в жидких и
твердых средах, ионов и молекул в ловушках (см., например, нашу новость "Квантовый регистр из нейтральных
атомов" ),), переходов Джозефсона и др. Несмотря на все усилия и затраты на реализацию
квантового компьютера, самым "мощным" на сегодняшний день остается 7-кубитовый ЯМР компьютер,
созданный в лаборатории IBM's Almaden Research Center. Но даже если предположить, что завтра
полноценный многокубитовый компьютер будет создан, то возникает вполне оправданный вопрос, что с
его помощью можно делать? Сейчас любой школьник знает, что для работы компьютера необходимо
программное обеспечение, реализующее определенные алгоритмы, и квантовый компьютер не является
исключением. В прошлом 2004 году минуло 10 лет с момента появления первого квантового алгоритма,
разработанного Питером Шором (Peter Shor) и показавшего превосходство квантовых алгоритмов над
классическими в определении простых множителей больших чисел - квантовый алгоритм факторизации.
Немногим позже Лов Гровер (Lov Grover) предложил остроумный алгоритм для поиска в случайной базе
данных. И пока, кажется, все! Но почему? На этот вопрос и пытается ответить Питер Шор в своей статье
"Прогресс в квантовых алгоритмах" [1].
По мнению Питера Шора существует две причины отсутствия новых квантовых алгоритмов. Во-
первых, вполне возможно, что существует только несколько проблем, для которых квантовый компьютер
показывает существенное уменьшение времени вычислений по сравнению с классическими
компьютерами, и большинство из них уже найдено. Во-вторых, это может быть связано с тем, что весь
наш пятидесятилетний опыт в построении классических алгоритмов непригоден для нахождения
квантовых алгоритмов, так как поведение квантовых систем коренным образом отличается от работы
более нам понятных классических. Кроме того, пока не ясно какой тип проблем может быть решен с
использованием квантовых компьютеров. Автор справедливо замечает, что даже в классических
вычислениях ответ на вопрос о классе проблем, которые могут быть решены за полиномиальное время на
обычном цифровом компьютере, не найден, и выбор метода (линейное программирование, динамическое
программирование, методы Монте-Карло и др.) и способа его применения для решения того или иного
класса проблем является больше искусством, чем наукой. Питер Шор считает, что проблемы, которые
могут быть решены с помощью квантового компьютера за время меньшее, чем экспоненциальное, не
должны принадлежать ни классу NP-трудных, ни к классу P-трудных задач. Такими проблемами,
например, являются изоморфизм графов и нахождение короткого вектора в геометрической решетке.
Несмотря на отсутствие явного прогресса в квантовых алгоритмах, некоторые положительные
результаты все же достигнуты. Например, показана возможность использования Фурье преобразования в
нахождении иррационального периода функции. Комбинирование алгоритма Гровера и алгоритма
"случайных блужданий" - квантовый алгоритм случайных блужданий - может позволить решать
некоторый класс задач намного быстрее, чем с использованием классических алгоритмов. Например,
используя такой алгоритм можно проверить за почти оптимальное время отличаются ли два элемента
базы данных друг от друга. Шором отмечается появление адиабатического квантового вычисления -
эвристические попытки найти основное состояние гамильтониана путем отслеживания его эволюции с
помощью квантового компьютера.
1. P.W. Shor. Quant. Inf. Proc., v.3, p. 1-5, 2004