31
правка
Изменения
→Алгоритм нахождения периода
[[Файл:Quantum algorithm. QFT. Graph3.jpg|270px|thumb|right|]]Поэтому вместо этого мы применим <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>.
