31
правка
Изменения
Нет описания правки
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: A \rightarrow B </tex>, такая, что <tex>f(x)=xu\bmod 2pmod2</tex> с неизвестным <tex>u</tex>. Найти <tex>u</tex> за минимальное количество обращений к функции <tex>f</tex>.
}}
'''Пример:'''
[[Файл:Quantumalgorithm.Paritycheck.png|470px|thumb|right|В виде круга изображён [[Квантовые гейты|Hadamard gate]].]]
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| <tex>x</tex>
|style="background-color:#FFF;padding:2px 10px"| '''0'''
|style="background-color:#FFF;padding:2px 10px"| '''1'''
|style="background-color:#FFF;padding:2px 10px"| '''0'''
|style="background-color:#FFF;padding:2px 10px"| '''1'''
|style="background-color:#FFF;padding:2px 10px"| '''0'''
|style="background-color:#FFF;padding:2px 10px"| '''1'''
|}<tex>u = 101</tex>
=== Реализация ===
Для начала инициализируем начальные <tex>n</tex> кубитов состоянием ноль. Проводим их всех через [[Квантовые гейты|гейт Адамара (англ. ''Hadamard gate'')<ref>[https://en.wikipedia.org/wiki/Hadamard_transform#Quantum_computing_applications Wikipedia {{---}} Hadamard gate]] </ref> и получаем все возможные суперпозиции. Суперпозиции передаём в "черный ящик", который реализован в виде вентиля <tex>U_f</tex>. Сам результат опять пропускаем через [[Квантовые гейты|гейт Адамара]]. В конце измеряем результат, который будет являться искомой <tex>u</tex>.
В качестве бита, который будет содержать ответ, будет использоваться суперпозиция:
|definition=Пусть имеется функция <tex> f: A \rightarrow B </tex>, такая, что <tex>f(x+S)=f(x)</tex> с неизвестным <tex>S</tex>. Найти <tex>S</tex> за минимальное количество обращений к функции <tex>f</tex>.
}}
[[Файл:Quantumalgorithm.Simonalgorithm.png|470px|thumb|right|В виде круга изображён [[Квантовые гейты|Hadamard gate]].]]
'''Пример:'''
{| style="background-color:#CCC;margin:0.5px"
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: \{0,\ldots,N-1\} \rightarrow S </tex>, такая, что <tex>f(x+r\bmod pmod N)=f(x)</tex> с неизвестным периодом <tex>r</tex>. Найти <tex>r</tex> за минимальное количество обращений к функции <tex>f</tex>.
}}
\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>, который позволяет решать задачу [[Разложение на множители (факторизация)|факторизации числа]].
