Изучаем Q#. Не будь зашоренным…

Алгориитм Шора — квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число M за время O((logM)^3) используя O(log M) логических кубитов.

Алгоритм Шора был разработан Питером Шором в 1994 году. Семь лет спустя, в 2001 году, его работоспособность была продемонстрирована группой специалистов IBM. Число 15 было разложено на множители 3 и 5 при помощи квантового компьютера с 7 кубитами.

Алгоритм Шора состоит из 2-х частей — квантовых и классических вычислений.

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

Практически, схема этого алгоритма полностью повторяет схему алгоритма Саймона, с отличием в последнем шаге — вместо применения оператора Адамара перед измерением входного регистра, используется оператор преобразования Фурье.

А какие есть ещё варианты определить период функции используя квантовые вычисления?

Когда-то ранее я писал статьи про способы сравнения (поиска фрагмента) изображений, поиска частоты сердечных сокращений с использованием операции вычисления скалярного произведения, которую я делал с помощью свёртки на основе БФП.

а так же начал повторять эту технологию при квантовых вычислениях

Изучаем Q#. Алгоритм Гровера. Не будите спящего Цезаря

Так почему бы не повторить успешный успех и, заодно, обобщить теорию вопроса?

Начнём …

Пусть у нас есть функция f: {0,1}^n to {0,1}^m.
Очевидно, что мы можем её так же записать, и как f: {0,1}^n to Z и как f: {0,1}^n to [0,1) без потери общности рассуждений (то есть {0,1}^m можно рассматривать и как двоичное представление целого числа, и как рациональную дробь полученную делением целого числа на 2^m)

Вычисление скалярного произведения через инверсию и свёрку

Пусть у нас есть кольцо с операцией op и пара функций a и b, отображающих кольцо в поле, например комплексных чисел

Операцией свёрки a и b мы будем называть функцию c = a x b, такую что c(i) = SUM a(ix)b(iy)|i=ix op iy

Пусть у нас есть кольцо с операцией op и функция f, отображающих кольцо в поле, например комплексных чисел (но здесь, если вы заметите, я использую только отображение в действительные числа)

Операцией инверсией аргумента назовём функцию inv f , такую что (inv f)(i) = f( -i ), где i op -i == 0

Скалярным произведением a и b называют (a,b) = SUM a(i)b(i) (=(a,b)(0) где (a,b)(i) = SUM a(ix)b(iy)|i=ix-iy)

Легко убедиться самостоятельно, что (a,b) = a x (inv b)

Пусть для регистров кубитов a и b

a = SUM A(i)|i>
b = SUM B(i)|i>

Тогда, если op:

xor: (a,b)(i) = a xor X(b) = SUM A(ix)B(iy)|i>|i=ix xor ~iy
add: (a,b)(i) = a sub b = a add X(b) add |1> = SUM A(ix)B(iy)|i>|i=ix-iy

Что даёт нам вычисление функции-скалярного произведения a и b?

Ответ — если A(i)~=B(i op k) для всех i и распределения отличны от тривиальных, то значение (a,b)(k) является максимальным (по модулю) среди других значений этой функции
А значит, если мы имеем пару регистров кубитов, содержащих частотные характеристики двух последовательностей, то

вычисление свёртки этих двух регистров,
измерение результата,
даст нам наиболее вероятное значение |k>

И, соответственно, если мы работаем с одной функцией, и F(i)~=F(i (op k)^j), то

вычисление свёртки функции самой с собой
измерение результата
с большой вероятностью даст нам значение 0 (op k)^j — то есть один из периодов функции

И как это применить?

Предположим, что мы можем сформировать состояние квантового регистра по правилу SUM SQRT(f(x))|x> (что, собственно, предполагает и алгоритм Шора).

Тогда, применив вышеизложенные рассуждения по свёртке функции f самой с собой, мы получим значения — кандидатуры на период функции f.

Таким образом, мы получили ещё один из вариантов для квантовой части алгоритма Шора — то есть алгоритм поиска периода функции, ~~со своим бэк-джеком и шл…~~ и без использования Фурье-трансформаций.

А как выглядит трансформация для вычисления свёртки?

Да весьма просто — это либо реализация операции арифметического вычитания в кольце 2^n, но реализованная на регистрах из кубитов, либо операция исключающего или над векторами длины n, реализованная на регистрах кубитов.

Схема алгоритма поиска периода с использованием свёртки

или другой вариант тех же рассуждений

где Uf отвечает за перераспределение вероятностей в соответствии со значениями функции f

В чём квантовое превосходство по сравнению с классическими вычислениями?

Если функция f (или пара функций) задана на множестве мощности N (обычно N=2^n) то при вычислении свёртки «в лоб» требуется O(N^2) операций, но благодаря «быстрым преобразованиям» таким, как БФП, преобразования Адамара и так далее, вычисление свёртки удаётся реализовать за O(NlogN) операций. При этом алгоритм обычно выглядит следующим образом:

Применяем «прямое быстрое преобразование» к функции (паре функций)
Поэлементно умножаем элементы (второй множитель берётся сопряжённым)
Выполняется «обратное быстрое преобразование» от полученного произведения

При использовании квантовых вычислений — вычисление свёртки происходит за один «шаг» то есть за одну не сложную трансформацию.

Вот и всё …

И бонусом — как реализовать SUM SQRT(f(x))|x>, используя базисные гейты?

Если погуглить, то можно найти разные способы решения этой задачи, например Decomposing unitary matrix into Q# quantum gates.

Но мы не ищем лёгких путей!!!

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

Изучаем Q#. Орёл или решка?

И таки да — мы не занимаемся экономией кубитов — в данных рассуждениях потребовалось ещё (m+1)2^n дополнительных кубитов, только для того, чтобы задать коэффициенты с нужным значением вероятности у регистра из n кубитов (но и сам алгорим Шора не отвечает на вопрос как задать требуемое состояние регистра кубитов).

Ссылки

Ранее

ссылка на оригинал статьи https://habr.com/ru/articles/773074/