31
правка
Изменения
Нет описания правки
{{Определение
|definition='''Квантовый алгоритм''' (англ. ''quantum algorithm'') представляет собой классический алгоритм, который задает последовательность унитарных операций ([[Квантовые гейты|гейтов]] (англ. ''quantum gate''), или вентилей) с указанием, над какими именно кубитами<ref>[https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82 Википедия {{---}} Кубит]</ref> (от англ. ''quantum bit'') их надо совершать.
}}
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: A \rightarrow B </tex>, такая, что <tex>f(x)=xu(mod \bmod 2)</tex> с неизвестным <tex>u</tex>. Найти <tex>u</tex> за минимальное количество обращений к функции <tex>f</tex>.
}}
'''Пример:'''
<tex>\mid -\bigr\rangle = \dfrac{1}{\sqrt{2}}(\mid 0\bigr\rangle - \mid 1\bigr\rangle)</tex>
Выразим неизвестную: <tex>\mid 00...0\ldots0\bigr\rangle\mid -\bigr\rangle\rightarrow\dfrac{1}{2^{n/2}} \Leftrightarrow \sum_\limits{x \mathop \in \{0,1\}^n} \mid x\bigr\rangle\mid-\bigr\rangle\rightarrow\dfrac{1}{2^{n/2}} \Leftrightarrow \sum_\limits{x \mathop \in \{0,1\}^n} (-1)^{xu}\mid x\bigr\rangle\mid-\bigr\rangle\rightarrow\mid u\bigr\rangle\mid-\bigr\rangle</tex>
=== Сложность ===
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: \{0,...\ldots,N-1\} \rightarrow S </tex>, такая, что <tex>f(x+r(mod \bmod N))=f(x)</tex> с неизвестным периодом <tex>r</tex>. Найти <tex>r</tex> за минимальное количество обращений к функции <tex>f</tex>.
}}
[[Файл:Quantumalgorithm.QFT.png|470px|thumb|right|]]
=== Реализация ===
[[Файл:Quantum algorithm. QFT. Graph3.jpg|220px|thumb|left|<tex>r</tex> и <tex>N/r</tex> {{- --}} периоды функций]]Чтобы решить задачу, воспользуемся квантовым преобразованием Фурье<ref>[https://en.wikipedia.org/wiki/Quantum_Fourier_transform Wikipedia {{---}} Quantum Fourier transform]</ref>(англ. ''Quantum Fourier transform''; далее '''''QFT'''''). '''''QFT''''' {{--- }} гейт, который реализует матрицу дискретного преобразования Фурье<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>r</tex>, после '''''QFT''''', получим новую периодическую функцию с периодом <tex>N/r</tex>, где <tex>N</tex> {{- --}} модуль, с которым мы работаем.
<tex> QFT_N = \dfrac{1}{\sqrt{N}}\begin{vmatrix} 1 & 1 & 1 & \cdots & 1
