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

в 13:32, , рубрики: Без рубрики

Добрый вечер, хабросообщество!
Цель данной статьи рассказать об одном из чудес квантовой информатики, а именно — алгоритм Гровера, который позволяет достичь квадратичное ускорение в сравнении с классическими алгоритмами перебора.
Небольшое знание линейной алгебры желательно.
image

Классический алгоритм перебора

Пусть дана функция Квантовый алгоритм Гровера — булева функция. Цель: найти хотя бы один корень уравнения f(x) = 1. На классическом компьютере, если f — произвольна(например, некоторый черный ящик, оракул), нам понадобиться O(N) операций, где Квантовый алгоритм Гровера, то есть, полный перебор. Если f в конъюнктивой нормальной форме — то данная задача является NP-полной. Проблема о равенстве/неравенстве P и NP является открытой и по сей день.

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

К сожалению, или к счастью, не известен квантовый(а классический тем более) для решения данной задачи за полиномиальное время. Но алгоритм Гровера позволяет получить квадратичное ускорение для полного перебора — за Квантовый алгоритм Гровера.

Краткое описание алгоритма

Используя n+1 кубит, мы приготавливаем первые n кубитов в суперпозицию всех возможных состояний, а последний в суперпозицию «нуля» и «единицы», но со «знаком минус» у «единицы». Тогда действуя Квантовый алгоритм Гровера раз оператором поворота, мы получаем состояние, при измерении которого с очень высокой вероятностью получаем решение уравнения.

Небольшой экскурс в терминологию.

Дираковские обозначения — |x> — обозначает вектор(столбец), а <x| — двойственный к нему вектор(строку). Тогда <x|x> будет скалярным произведением. А |x><x| — будет матрицей, обычное умножение вектор-столбца на вектор-строку. Квантовый алгоритм Гровера — обозначает тензорное произведение векторов, чаще записывают кратко: |x,y>.

Пример: |0> и |1> — в двумерном случае обозначают вектора (1,0) и (0,1) соответственно.
|0><0| — матричная единица, где 1 стоит на позиции (1,1).
В двумерном случае: |0><0| = Квантовый алгоритм Гровера

Суперпозиция — линейная комбинация базисных состояний.

Кубит — наименьший элемент для хранения информации на квантовом компьютере. В отличие от классического бита, который может принимать только 1 и 0, квантовый бит может находится в суперпозиции двух состояний: |0> и |1>, которые «отвечают» за 0 и 1 соответственно.
image
Элемент Адамара(обозначаемый как H) — действует следующим образом: Квантовый алгоритм Гровера
H = Квантовый алгоритм Гровера
— матричное представление

Элемент Уолша-Адамара(обозначаемый как WH,W) — Тензорная степень H.
Квантовый алгоритм Гровера

Квантовое состояние системы из n кубитов:
image, где Квантовый алгоритм Гровера — некоторый коэффициент(амплитуда), комплексное число, а Квантовый алгоритм Гровера — вектор, с единицей на i позиции.
Классическое состоянии системы из n битов будет одним из N вариантов(например, числом от 0 до N-1), то квантовое будет линейной комбинацией всех этих состояний с некоторым комплексным коэффициентом.
А получить какое-то состояние можно измерением. Тогда мы получим результат Квантовый алгоритм Гровера с вероятностью Квантовый алгоритм Гровера.

Ancilla — вспомогательные кубиты, которые нужны при вычислении.

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

Зеркальное отражение относительно гиперплоскости — оператор, действующий следующим образом:
Квантовый алгоритм Гровера
На произвольный вектор распространяется по линейности.

Алгоритм

image
Пусть нам известно, что у f(x) = 1 есть L решений( L << N, в обратном случае мы сможет просто случайно выбирать x и с большой вероятностью наткнемся на решение).
Тогда пусть искомый вектор имеет вид:
Квантовый алгоритм ГровераКвантовый алгоритм Гровера, где Квантовый алгоритм Гровера — некоторое решение. При измерении такого состояния мы получим одно из решений.
Пусть начальное состояние Квантовый алгоритм Гровера — суперпозиция всех возможных состояний(базисных векторов), полученная действием элемента Уолша-Адамара на |0>.
Тогда для решения потребуется n+1 кубит, где первые n займет |X>, а последний — ancilla.
Установим анциллу в состояние Квантовый алгоритм Гровера, что получается действием элемента Адамара на |1>.
Тогдa, очевидно, что Квантовый алгоритм Гровера, где |X> некоторый вектор состояния для n кубитов. (Что следует из тензорного произведения векторов и того, что Квантовый алгоритм Гровера).
То есть, Quf — задало зеркальное отражение относительно гиперплоскости, перпендикулярной вектору решений!

Зададим еще один оператор, который производит зеркальное отражение относительно вектора Квантовый алгоритм Гровера:
Квантовый алгоритм Гровера, где I — единичная матрица. Не сложно проверить, что это верно определенный оператор.

Тогда пусть Квантовый алгоритм Гровера — произведение(композиция) двух операторов. Тогда G задает поворот на некоторый угол Квантовый алгоритм Гровера.
Не сложно проверить, что этот угол равен Квантовый алгоритм Гровера = Квантовый алгоритм Гровера Квантовый алгоритм Гровера.
Что следует из разложения арксинуса в ряд Тейлора при условии, что L << N.
Тогда G, действуя на |X>, поворачивает его на угол Квантовый алгоритм Гровера в сторону Квантовый алгоритм Гровера!

А так как уголКвантовый алгоритм Гровера, то повторив операцию Квантовый алгоритм Гровера раз, мы получим почти вектор Квантовый алгоритм Гровера!
Вероятность ошибки составит Perr = L/N, что при L << N дает гарантированный результат почти во всех случаях!

Заключение

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

Заранее приношу свои извинения за возможные ошибки/неточности в терминологии и описании алгоритма.
О всех подобных и орфографических ошибках прошу уведомлять в личку, чему буду рад, если оные найдутся!
Замечания приветствуются!

Автор: TakeOver

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js