Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
Квантовые алгоритмы 139
4.1.6 Заключительные замечания
Экспериментальные и теоретические исследования квантовых вычислений в настоящее время привлекают все возрастающее внимание, как со стороны академических исследователей, так и со стороны индустрии по всему миру. Идея о том, что природу можно контролировать и манипулировать ей на квантовом уровне является мощным стимулом для воображения физиков и инженеров. Почти ежедневно происходит прогресс в разработке все более обещающих технологий, реализующих квантовые вычисления, и новых квантовых алгоритмов, имеющих различные преимущества по сравнению со своими классическими аналогами. Здесь есть потенциал для действительно революционных инноваций.
Эта статья является переработанной версией вводной статьи по квантовым вычислениям, которая появилась в мартовском выпуске за 1998 год в журнале Physics World [128].
4.2 Квантовые алгоритмы
Р. Джозса
4.2.1 Введение
Квантовый алгоритм - это любой физический процесс, использующий характерные квантовые эффекты для выполнения полезных вычислительных задач. Удобно формализовать описание этих квантовых вычислительных процессов в терминах модели, выстраивающей параллель с формализмом классических вычислений. По сути, в квантовом случае элементы памяти в компьютере - это кубиты, а не биты, а логические операции - это унитарные преобразования, а не булевы операции классического вычисления. Можно утверждать [124], что модели такого рода достаточно, чтобы описать любой квантовый процесс. От любого компьютера требуется, чтобы он оперировал «конечными средствами», то есть, чтобы он имел возможность использовать только некоторый конечный набор базовых унитарных операций. Любая другая операция, которая может нам понадобиться в алгоритме, должна быть построена (или аппроксимирована с достаточной точностью) из этих базовых строительных блоков соединением их действия на выбранные кубиты. Можно показать [129, 130], что достаточно использовать различные маленькие наборы унитарных операций (так называемые «универсальные наборы») чтобы аппроксимировать любую унитарную операцию над любым числом кубитов с произвольной точностью.
Одно из наиболее полезных и важных следствий из этого форма-
140 Концепция квантовых вычислений
лизма состоит в том, что он дает способ оценить сложность вычислительной задачи (опять-таки, выстраивая параллель понятиям классической теории сложности). Нас будет особенно интересовать временная сложность, то есть, оценка числа элементарных операций, необходимых для решения вычислительной задачи, как функция объема входных данных.
Если два компьютера А и В обладают разными (универсальными) наборами базовых операций, то временная сложность для произвольной вычислительной задачи будет, в общем случае, различной. Однако, можно сперва запрограммировать в В выполнение каждой из базовых операций А с помощью его собственного набора, а затем запустить любую программу, написанную на языке набора операций А. Пусть к обозначает максимальное число операций, необходимых В, чтобы воспроизвести любую из базовых операций Л. Тогда временная сложность на В будет, самое большее, в к раз больше сложности на А, то есть смена набора базовых операций приводит, самое большее, к равномерному замедлению (независимо от размера входа) для любой вычислительной задачи. В теории сложности вычислений нас, в целом, интересует не точное число шагов в вычислении, а только характерный темп роста числа шагов при увеличении объема входных данных. В целом, мы интересуемся только тем, ограничено ли число шагов полиномиальной функцией от объема входных данных (приводя к так называемым полиномиальным по времени, или эффективным, алгоритмам) или же оно растет экспоненциально (или сверх-полиномиаль-но) с их объемом. Согласно сделанным выше замечаниям, это различие не зависит от выбора компьютера, оно является внутренним свойством самой вычислительной задачи.
Наш основной интерес при изучении квантовых алгоритмов вызывает возможность найти полиномиальные по времени алгоритмы для таких задач, для которых не известно классических полиномиальных по времени алгоритмов. То есть, мы хотим продемонстрировать, что квантовые эффекты могут привести к экспоненциальному ускорению, по сравнению с классической обработкой информации. Мы опишем различные ситуации, в которых это происходит - алгоритмы Дойча, Саймона и Шора. Мы также опишем квантовый алгоритм поиска Гровера, который дает, по сравнению с любым классическим алгоритмом, ускорение в квадратный корень из числа шагов, а не экспоненциальное ускорение. Тем не менее, он представляет большой практический интерес. Алгоритм Гровера представляет также и большой теоретический интерес благодаря своей связи с классическим классом сложности, называемым NP [131,132].
Мы увидим в главе 5, что возможное применение любого доста-
Квантовые алгоритмы 141
точно большого квантового алгоритма в настоящее время представляет собой чрезвычайно сложную экспериментальную задачу. Тем не менее, существование интересных квантовых алгоритмов, хотя бы на уровне теоретических построений, очень важно само по себе, поскольку оно указывает на новые существенные отличия в коренной структуре между классической и квантовой физикой. С точки зрения переработки информации, временная эволюция в квантовой физике, похоже, сложнее, чем классическая эволюция во времени, причем это отличие можно описать в рамках теории сложности вычислений.
