1632
правки
Изменения
м
rollbackEdits.php mass rollback
}}
'''Перефразируем задачу:''' у нас есть периодичная периодическая функция, для которой необходимо найти её период, путём нахождения [[Хеш-таблица|коллизии]]. Так, можно Можно заметить, что алгоритм нахождения периода похож на алгоритм Саймона и фактически является его обобщением.
[[Файл:Quantumalgorithm.QFT.png|470px|thumb|right|]]
=== Реализация ===
Чтобы решить задачу, воспользуемся квантовым преобразованием Фурье<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>QFT</tex> и получаем все возможные равновероятные суперпозиции всех булевых состояний <math>N</math> такие, что:
<tex>|0 \rangle |0 \rangle \xrightarrow{QFT_N} \dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x \rangle |0 \rangle</tex>
Теперь наш первый регистр находится в периодической суперпозиции, где период такой же, как период функции, но мы не можем сразу его просто измерить, потому что мы можем измерить другое значение <tex>|f\rangle</tex>, ведь мы получили периодическую суперпозицию, которая случайно линейно смещена и мы не получим никакой полезной информации.
[[Файл:Quantum algorithm. QFT. Graph3.jpg|201px270px|thumb|leftright|]]Поэтому вместо этого мы применим <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>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов]]
