Квантовый алгоритм

Квантовый алгоритм — алгоритм, предназначенный для выполнения на квантовом компьютере.

Основные принципы

Квантовый алгоритм представляет собой классический алгоритм, который задает последовательность унитарных операций (гейтов, или вентилей) с указанием, над какими именно кубитами их надо совершать. Квантовый алгоритм задается либо в виде словесного описания таких команд, либо с помощью их графической записи в виде системы вентилей (quantum gate array).

Результат работы квантового алгоритма носит вероятностный характер. За счёт небольшого увеличения количества операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице.

Множества задач, допускающих решение на квантовом компьютере и на классическом, совпадают. Квантовый компьютер, таким образом, не увеличивает число алгоритмически разрешимых задач. Весь смысл применения квантового компьютера в том, что некоторые задачи он способен решить существенно быстрее, чем любой из классических. Для этого квантовый алгоритм должен по ходу вычисления генерировать и использовать запутанные квантовые состояния (см. Квантовая суперпозиция и Квантовая сцепленность).

Любая задача, решаемая квантовым алгоритмом, может быть решена и классическим компьютером путём прямого вычисления унитарных матриц экспоненциальной размерности, получения явного вида квантовых состояний. В частности, проблемы, неразрешимые на классических компьютерах (например, проблема остановки), остаются неразрешимыми и на квантовых. Но такое прямое моделирование требует экспоненциального времени, и потому возникает возможность, используя квантовый параллелизм, ускорять на квантовом компьютере некоторые классические алгоритмы.

Ускорение на квантовом компьютере не связано с тактовой частотой процессора. Оно основано на квантовом параллелизме. Один шаг квантового вычисления совершает гораздо большую работу, чем один шаг классического. Однако было бы ошибкой приравнивать квантовое вычисление к распараллеленному классическому. Например, квантовый компьютер не может решить задачу перебора быстрее, чем за ${\sqrt {T_{class}}}$ где $T_{class}$ — время работы детерминированного классического алгоритма перебора (см.), в то время как недетерминированный классический алгоритм решает её за время $log(T_{class})$. Но недетерминированный классический алгоритм требует экспоненциального ресурса памяти, то есть не является физически осуществимым, тогда как квантовый алгоритм не противоречит известным законам природы.

Квантовое вычисление является процессом особого рода. Оно использует особый физический ресурс: квантовые запутанные состояния, что позволяет в некоторых случаях достигнуть поразительного выигрыша во времени. Такие случаи называются квантовым ускорением классических вычислений.

Случаи квантового ускорения, на фоне общей массы классических алгоритмов, очень редки (см.). Однако, это не умаляет принципиального значения квантовых вычислений, потому что они способны принципиально ускорить выполнение задач переборного типа.

Основные схемы квантового ускорения

Главный тип задач, которые ускоряются квантовыми алгоритмами, являются задачи типа перебора. Их можно разделить на 2 основные группы:

1. Задачи моделирования динамики сложных систем (первоначальная идея Фейнмана) и
2. Математические задачи, сводящиеся к перебору вариантов:
   1. Общий случай перебора: схема Гровера и её варианты, а также
   2. Задачи поиска скрытых периодов: схема Шора использования быстрого квантового преобразования Фурье и её аналоги.

Тип 1) представлен алгоритмом Залки — Визнера моделирования унитарной динамики квантовых систем $n$ частиц за почти реальное время и с линейной от $n$ памятью. Этот алгоритм использует схему Шора квантового преобразования Фурье.

Тип 2) представлен:

• алгоритмом Гровера общей задачи перебора и его непрерывным и адиабатическим вариантами, а также алгоритмами, использующими схему Гровера: структурного поиска (Фари, Гутман), алгоритмом поиска экстремума (Хойер и др.) и поиска совпадающих строк в базе данных (Амбайнис),
• алгоритмом Шора факторизации целых чисел, алгоритмом Абрамса — Ллойда выявления периода, алгоритмом Китаева определения скрытых подгрупп и др.

Тип 1) представляет наибольший интерес с точки зрения дальнейших приложений квантового компьютера.

Классификация

Классификация квантовых алгоритмов может проводиться по типу квантовых преобразований, используемых алгоритмом. Среди часто используемых преобразований можно отметить: en:phase kick-back, phase estimation, en:quantum Fourier transform, en:quantum walk, en:amplitude amplification, en:topological quantum field theory. Также возможна группировка квантовых алгоритмов по типу проблем, решаемых ими.

Широко известные алгоритмы

• Алгоритм Шора
• Алгоритм Гровера
• Алгоритм Дойча — Йожи
• Алгоритм Залки — Визнера
• Алгоритм Регева

См. также

• Квантовый компьютер
• Квантовое программирование
• Хронология квантовых вычислений
• Квантовое распределение ключей
• Список алгоритмов
• Класс BQP
• Квантовые нейронные сети

Ссылки

• Stephen Jordan, Algebraic and Number Theoretic Algorithms — comprehensive catalog of quantum algorithms, NIST, 2013