31
правка
Изменения
Нет описания правки
\end{vmatrix}</tex>, где <tex>ω = e^{\dfrac{2πi}{N}} </tex>
Так аналогично предыдущему алгоритму, но используя '''''QFT''''', получаем результат вида <tex>m\dfrac{N}{r}</tex>, где <tex>m</tex> {{- --}} какое-то натуральное число, возникающее в ходе алгоритма, мешающее нам сразу найти период, <tex>N</tex> {{--- }} модуль, <tex>r</tex> {{--- }} период. Выполнив данный алгоритм <tex>n</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>, при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.
''Примечание:'' Алгоритм нахождения периода используется в алгоритме Шора<ref>[https://en.wikipedia.org/wiki/Shor%27s_algorithm Wikipedia {{---}} Shor's algorithm]</ref>, который позволяет решать задачу [[Разложение на множители (факторизация)|факторизации числа]].
== См.также ==
* [[Квантовые гейты]]
==Примечания==
* [https://cyberleninka.ru/article/v/kvantovye-kompyutery-i-kvantovye-algoritmy-chast-2-kvantovye-algoritmy Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 2. Квантовые алгоритмы"]
* [https://en.wikipedia.org/wiki/Quantum_Fourier_transform Квантовое преобразование Фурье]
* [https://pdfs.semanticscholar.org/d9dc/64159f94bde3fbe81b172e60369f3ee410f4.pdf Алгоритм Гровера]
* [https://en.wikipedia.org/wiki/Shor%27s_algorithm Алгоритм Шора]
* [http://www.quantumplayground.net Веб-приложение, использующее WebGL, чтобы имитировать до 22 кубитов на GPU]
* [https://sites.google.com/view/quantum-kit/ Веб-приложение, для написания и визуализации квантовых алгоритмов]
* [https://habr.com/company/mailru/blog/350208/ Языки программирования для квантового компьютера]
[[Категория: Дискретная математика и алгоритмы]]
