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

Задача

Предположим, у нас есть крупная база данных из 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.

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

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

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

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

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

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

где

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

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

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

Два отражения всегда соответствуют вращению — преобразование 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

Источник: m.vk.com

Комментарии: