Изменения

'''Перефразируем задачу:''' у нас есть периодичная функция, для которой необходимо найти её период, путём нахождения [[Хеш-таблица|коллизии]]. Так, можно заметить, что алгоритм нахождения периода похож на алгоритм Саймона и фактически является его обобщением.

[[Файл:Quantum algorithm. QFT. Graph3.jpg|220px|thumb|left|<tex>r</tex> и <tex>N/r</tex> {{---}} периоды функций]]Чтобы решить задачу, воспользуемся квантовым преобразованием Фурье<ref>[https://en.wikipedia.org/wiki/Quantum_Fourier_transform Wikipedia {{---}} Quantum Fourier transform]</ref>(англ. ''Quantum Fourier transform''; далее '''''<tex>QFT'''''</tex>). '''''<tex>QFT''''' </tex> {{---}} гейт, который реализует матрицу дискретного преобразования Фурье<ref>[https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Википедия {{---}} Дискретное преобразование Фурье]</ref> над квантовым состоянием. Идея в следующем: есть периодическая функция с периодом Для начала инициализируем начальные кубиты состоянием ноль. Проводим их всех через гейт <tex>r</tex>, после '''''QFT''''', получим новую периодическую функцию с периодом <tex>N/r</tex>, где и получаем все возможные равновероятные суперпозиции всех булевых состояний <texmath>N</texmath> {{---}} модультакие, с которым мы работаем.что:

<tex> |0 \rangle |0 \rangle \xrightarrow{QFT_N = } \dfrac{1}{\sqrt{N}}\begin{vmatrix} 1 & 1 & 1 & sum\cdots & 1\\ 1 & ω^2 & w^3 & \cdots & ω^limits_{N-1x=0}\\ 1 & ω^3 & ω^6 & \cdots & ω^{2(N-1)}|x \rangle |0 \ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & ω^{N-1} & ω^{2(N-1)} & \cdots & ω^{(N-1)(N-1)}\end{vmatrix}</tex>, где <tex>ω = e^{\dfrac{2πi}{N}} rangle</tex>

Так аналогично предыдущему алгоритмуСуперпозиции передаём в гейт <tex>U_f</tex>, но используя '''''QFT'''''который реализует унитарное преобразование<ref>[https://ru.wikipedia.org/wiki/%D0%A3%D0%BD%D0%B8%D1%82%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80 Википедия {{---}} Унитарный оператор]</ref>, получаем результат вида которое переводит <tex>|x \rangle |0 \rangle</tex> в <tex>m|x \rangle |f(x) \rangle:</tex> <tex>\dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x \rangle |0 \rangle \xrightarrow{U_f} \dfrac{1}{\sqrt{N}} \sum\limits_{rx=0}^{N-1}|x \rangle |f(x) \rangle</tex> Чтобы получить из этого периодическую суперпозицию, где мы измеряем <tex>|f\rangle</tex> и поскольку <tex>f</tex> периодическая, её прообраз это <tex>mf(x_0)</tex> , такой что <tex>\{x_0,x_0+r,x_0+2r,\ldots,x_0+(\dfrac{N}{r}-1)r)\}</tex>: <tex>\dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N--1} |x \rangle |f(x) \rangle \xrightarrow{measure|f\rangle} \sqrt{\dfrac{r}{N}} какое\sum\limits_{i=0}^{N/r-то произвольное 1} |ir+x_0 \rangle |f(случайноеx_0) натуральное число\rangle</tex> Теперь наш первый регистр находится в периодической суперпозиции, где период такой же, как период функции, возникающее из тогоно мы не можем сразу его просто измерить, потому что форма рационального числа мы можем измерить другое значение <tex>|f\dfrac{m}{r}rangle</tex> , ведь мы получили периодическую суперпозицию, которая случайно линейно смещена и мы не единственна получим никакой полезной информации. [[Файл:Quantum algorithm. QFT. Graph3.jpg|201px|thumb|left|]]Поэтому вместо этого мы применим <tex>QFT</tex> и будем полагаться на его свойства, чтобы получить информацию, которая нам нужна. Идея в своем родеследующем: есть периодическая функция с периодом <tex>r</tex>, после применения <tex>QFT</tex>, получим новую периодическую функцию с периодом <tex>N/r</tex>, где <tex>N</tex> {{---}} модуль, с которым мы работаем: <tex>\sqrt{\dfrac{r}{N}} \sum\limits_{i=0}^{N/r-1} |ir+x_0 \rangle \xrightarrow{QFT_N} \dfrac{1}{\sqrt{r}} \sum\limits_{i=0}^{r-1} |i\dfrac{N}{r} \rangle φ_i</tex>, где <tex>φ_i</tex> - некоторый неважный период, возникающий из линейного сдвига <tex>x_0</tex>. Так мы уже можем измерить и извлечь <tex>m\dfrac{N}{---r}} период</tex>, для некоторого целого <tex>m</tex>. Выполнив данный  Теперь мы повторяем алгоритм , чтобы получить несколько различных кратных <tex>n\dfrac{N}{r}</tex> раз. Как только у нас будет достаточно значений, найдём мы можем вычислить их наибольший общий делитель<ref>[https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C Википедия {{---}} Наибольший общий делитель]</ref> от <tex>n</tex> полученных чисел, который, с некоторой вероятностью, будет искомым периодом <tex>r</tex>, при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.