31
правка
Изменения
→Алгоритм нахождения периода
}}
'''Перефразируем задачу:''' у нас есть периодичная периодическая функция, для которой необходимо найти её период, путём нахождения [[Хеш-таблица|коллизии]]. Так, можно Можно заметить, что алгоритм нахождения периода похож на алгоритм Саймона и фактически является его обобщением.
[[Файл:Quantumalgorithm.QFT.png|470px|thumb|right|]]
=== Реализация ===
Теперь наш первый регистр находится в периодической суперпозиции, где период такой же, как период функции, но мы не можем сразу его просто измерить, потому что мы можем измерить другое значение <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>.
