- Алгоритм Гровера
-
Алгоритм Гровера (англ. Grover search algorithm, GSA) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения
где
есть булева функция от n переменных.[1]
Предполагается, что функция
задана в виде чёрного ящика, или оракула, то есть в ходе решения мы можем только задавать оракулу вопрос типа: «чему равна
на данном
», и после получения ответа использовать его в дальнейших вычислениях. То есть задача решения уравнения (1) является общей формой задачи перебора; здесь требуется отыскать «пароль к устройству
», что классически требует прямого перебора всех
вариантов.
GSA находит какой-нибудь корень уравнения, используя
обращений к функции
, с использованием
кубитов.[2] Алгоритм был открыт американским математиком Ловом Гровером в 1996 году.
Содержание
Свойства
Если уравнение (1) имеет l корней, по схеме Гровера можно найти один из них на квантовом компьютере за время
(даже если l не известно заранее), то есть снова квантовая сложность является квадратным корнем из классической.
Классический алгоритм решения такой задачи (линейный поиск), очевидно требует
обращений к
. Алгоритм Гровера позволяет решить задачу поиска за время порядка квадратного корня из классического, что является огромным ускорением. Доказано, что GSA является оптимальным в следующих отношениях:
- Константу
нельзя улучшить более чем на 3 % [3].
- Большего квантового ускорения, чем квадратичное, нельзя получить для неисчезающей доли всех возможных черных ящиков
[4].
GSA есть пример массовой задачи, зависящей от оракула. Для более частных задач удается получить большее квантовое ускорение. Например, алгоритм факторизации Шора дает экспоненциальный выигрыш по сравнению с соответствующими классическими алгоритмами.
То, что f задана в виде черного ящика, никак не влияет в общем случае на сложность как квантовых, так и классических алгоритмов. Знание «устройства» функции f (например, знание задающей ее схемы из функциональных элементов) в общем случае никак не может помочь в решении уравнения (1). Поиск в базе данных соотносится с обращением функции, которая принимает определенное значение, если аргумент x соответствует искомой записи в базе данных.
Пусть
есть унитарный оператор, зеркально отражающий гильбертово пространство относительно гиперплоскости, перпендикулярной вектору
,
— состояние, соответствующее корню уравнения (1),
— равномерная суперпозиция всех состояний. Тогда GSA состоит в применении оператора
к состоянию
число раз, равное целой части
. Результат будет почти совпадать с состоянием
.
Алгоритмы, использующие схему Гровера
- Алгоритм поиска экстремума целочисленной функции (P. Hoyer и др.). Ищется наибольшее значение функции
. Квантовый алгоритм находит максимум за
обращений к f.
- Алгоритм структурного поиска (Farhi, Gutman). Ищется решение уравнения (1) при дополнительном условии
где
разбиение строки
на две строки одинаковой длины. Алгоритм имеет сложность порядка квадратного корня из классического времени.
- Алгоритм поиска совпадающих строк в базе данных (Амбайнис). Ищется пара разных аргументов
на которых функция
принимает одно и то же значение. Алгоритм требует
обращений к f.
Непрерывные версии алгоритма Гровера
- Пусть гамильтониан квантовой системы имеет вид
, где
и
представляют собой операторы
и
соответственно. Тогда непрерывная унитарная эволюция с гамильтонианом
, стартуя с
, естественно приводит к
. Сложность такого непрерывного аналога GSA точно та же, что и для дискретного случая.
- Адиабатический вариант GSA. Медленная эволюция основного состояния типа
под действием гамильтониана, зависящего от f, согласно адиабатической теореме, за время порядка
ведет к состоянию
.
Применение
Смысл GSA состоит в «подскоке амплитуды» (amplitude amplification) целевого состояния за счет убывания амплитуды всех других состояний. Геометрически GSA заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность GSA). Каждый шаг дает вращение на угол
, где угол между
и
составляет
. Дальнейшее продолжение итераций оператора G даст продолжение обхода окружности в вещественной плоскости, порождённой данными векторами.
Гроверовский «подскок амплитуды» является, по-видимому, фундаментальным физическим феноменом в квантовой теории многих тел. Например, его учет необходим для оценки вероятностей событий, которые кажутся «редкими». Процесс, реализующий схему GSA, приводит к взрывному росту первоначально пренебрежимо малой амплитуды, что способно быстро довести ее до реально наблюдаемых величин.
Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путем исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.
См. также
Примечания
- ↑ Иногда GSA неточно называют поиском в базе данных.
- ↑ Сложность работы алгоритма, для задачи с оракулом называемая еще временем его работы, определяется числом обращений к оракулу.
- ↑ Christof Zalka, Grover’s quantum searching algorithm is optimal, Phys.Rev. A60 (1999) 2746—2751 [1]
- ↑ Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc.Roy.Soc.Lond. A455 (1999) 2165—2172 [2]
Ссылки
- Гровер Л. К. Квантовая механика помогает найти иголку в стоге сена (для скачивания)
- Квантовый алгоритм Гровера Логинов О. В. и Цыганов А. В., Санкт-Петербургский Государственный Университет
- Исходные тексты симулятора квантового компьютера на C++ и реализации алгоритма Гровера
Квантовые алгоритмы Алгоритм Шора • Алгоритм Гровера • Алгоритм Дойча — Джоза • Задача Фейнмана Категории:- Квантовый компьютер
- Квантовые алгоритмы
Wikimedia Foundation. 2010.