Алгоритм Гровера - квантовые вычисления

Задача

Предположим, у нас есть крупная база данных из N элементов. Мы хотим найти один из элементов, например p, по ID, скажем w. Используя классические вычисления, нужно было бы проверить около N/2 элементов, чтобы найти совпадение с w, а в худшем случае и все N. Однако, используя алгоритм Гровера, можно найти w за √N шагов, а это квадратичное ускорение.

Оракул

Один из способов найти w — создать функцию f, возвращающую 0, если ID не совпадает с w, и 1, если совпадает. Далее определяем матрицу оракула U_f (где _ означает нижний индекс), чтобы действовать на основании состояний |x⟩:

Таким образом, когда f(x) возвращает 0 (что означает, x не совпадает с w), -1 для f(x) становится 1. Когда f(x) возвращает 1 (что означает, x совпадает с w), -1 для f(x) становится -1. Следовательно, если x не является p, оракул ничего не делает. Если x равен w, он отображает |w⟩ в -|w⟩. Геометрически эта унитарная матрица соответствует отражению исходной для элемента w в N-мерном векторном пространстве. 

Амплитудное усиление

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

Если в любой точке x будет измерен, в соответствии с пятым принципом квантовой механики (известным также как правило Борна) суперпозиция коллапсирует до одного из базовых состояний с одинаковой вероятностью 1/N.

Амплитудное усиление, как видно из названия, усиливает вероятность выбранных элементов, соответственно ослабляя вероятность других (сумма квадратов всех вероятностей должна добавляться к 1). 

Два пути визуализации процесса 

Процесс как вероятности

Шаг 1: Процедура начинается в равномерной суперпозиции |s⟩. Пунктирная линия — это средняя амплитуда. Розовый блок — это p. Диаграмма в случае N = 4.

IBM Qiskit

Шаг 2: Применяем отражение оракула U_f к состоянию |s⟩, перевернув его отрицательно. Заметьте, что средняя амплитуда уменьшилась. 

IBM Qiskit

Шаг 3: Применяем отражение приближённо к состоянию |s⟩ (средняя амплитуда). Это завершает преобразование, увеличивая P и соответственно уменьшая остальные элементы. 

IBM Qiskit

Затем повторяем шаги 2 и 3 до тех пор, пока другие амплитуды не достигнут 0, то есть примерно √N циклов.

Процессы как векторы

Другой (более математически строгий) метод объяснения алгоритма Гровера — это использование векторов. 

Шаг 1. Инициализировать вектор |s⟩. Его положение формируется на графике с перпендикулярными осями |w⟩ и |s’⟩ (|s⟩ без |w⟩), что позволяет выразить вектор начального состояния |s⟩ как комбинацию осей |w⟩ и |s’⟩:

где

IBM Qiskit

Шаг 2: Применяем отражение оракула U_f к состоянию |s⟩.

На диаграмме вектор |s⟩ (представляющий среднее для всех элементов) опускается. Красный вектор представляет вероятность правильного элемента, отражённого отрицательно. Геометрически оракул является отражением состояния |s⟩ вокруг |s’⟩.

IBM Qiskit

Шаг 3: Применяем отражение U_s к состоянию |s⟩, где U_s=2|s⟩⟨s|−1. Это отображает состояние на U_sU_f|s⟩ и завершает преобразование; поднимает красный вектор ближе к |w⟩, в то же время опуская |s⟩.

IBM Qiskit

Два отражения всегда соответствуют вращению — преобразование U_sU_f поворачивает начальное состояние |s⟩ ближе к |w⟩.

Поскольку при первом отражении средняя амплитуда снижается, преобразование увеличивает отрицательную амплитуду |w⟩ примерно в 3 раза относительно исходного значения, в то же время уменьшая остальные амплитуды. 

Время выполнения

После t шагов мы окажемся в состоянии |ψ.t⟩ = (U.sU.f)^t |s⟩. Вращение нужно применять √N раз, что можно понять, посмотрев на амплитуду состояния |ψ⟩.

Амплитуда |w⟩ растёт линейно с числом приложений — около tN^(—1/2). Тем не менее вероятность попадает в квадратный корень. 

Кроме того, если существует несколько решений M, сработают примерно √(N/M) вращений.

Пример с двумя кубитами 

Нахождение количества вращений и применение вращения 

В случае N = 4 (00, 01, 10, 11) мы можем найти значение теты: 

После t шагов применяются вращения:

где

Чтобы найти |w⟩, необходимо найти θ_t=π/2. Со значением теты (θ=π/6) решение уравнения будет t = 1, то есть после t = 1 вращений искомый элемент найден. 

Оракулы

Оракулы разные для каждого из N = 4 возможных элементов (|00⟩,|01⟩,|10⟩,|11⟩).

Оракул для |w⟩=|11⟩

Оракул U_f действует на |11⟩ следующим образом. Видно, что состояние |11⟩ перевёрнуто отрицательно. 

Оракул, способный выполнять эту функцию, является контролируемым квантовым вентилем CZ:

Он переворачивает кубит 11 отрицательно.

Оракул для |w⟩=|00⟩

Оракул U_f действует на |00⟩ следующим образом. Состояние|00⟩ перевёрнуто отрицательно.

Суммирующая схема:

Оракул для |w⟩=|01⟩ и |w⟩=|10⟩

Оракулы для|w⟩ = |01⟩ (слева) и |w⟩ = |10⟩ (справа)

Отражение

Чтобы закончить суммирующую схему, нужно применить дополнительное отражение Us=2|s⟩⟨s|−1, которое ведёт себя так:

Один из способов записи этого отражения в суммирующей схеме:

Полная схема для |w⟩ = |00⟩

После реализации в симуляторе IBM Qiskit:

…первый кубит и второй кубит возвращают 0 100% времени.

Применяем суммирующую схему на реальном квантовом компьютере IBM:

Есть некоторые ошибки из-за ошибок вычислений вентиля, но подавляющее большинство по-прежнему 00.

Алгоритм Гровера можно расширить на несколько кубитов. Для числа кубитов n общее количество элементов, которое сможет поддерживать алгоритм, будет 2 к n.

Надеюсь, вам понравилась эта статья! Чтобы поэкспериметировать, зайдите на IBM Quantum Experience для создания суммирующих схем и реализации квантовых алгоритмов. 

---

Перевод статьи Andre Ye: Grover’s Algorithm — Quantum Computing