Изменения

|definition='''Квантовый алгоритм''' (англ. ''quantum algorithm'') представляет собой классический алгоритм, который задает последовательность унитарных операций ([[Квантовые гейты|гейтов]], или вентилей) с указанием, над какими именно кубитами<ref>[https://neercru.ifmowikipedia.ruorg/wiki/index.php?title=%D0%9A%D0%B2%D0%B0%D0%BD%D1%8283%D0%BEB1%D0%B2%D1%8B%D0%B5_%D0%B3%D0%B5%D0%B9B8%D1%82%D1%8B гейтовВикипедия {{---}} Кубит], или вентилей) с указанием, над какими именно кубитами </ref> их надо совершать.

|definition=Пусть имеется функция <tex> f: A \{0,1\}^n \rightarrow B \{0,1\} </tex>, такая, что <tex>f(x)=xux\cdot u\pmod2 \equiv (mod 2x_1\wedge u_1) \oplus (x_2\wedge u_2)\oplus\ldots\oplus(x_n\wedge u_n)</tex> с неизвестным <tex>u</tex>. Найти <tex>u</tex> за минимальное количество обращений к функции <tex>f</tex>.

[[Файл:Quantumalgorithm.Paritycheck.png|470px|thumb|right|В виде круга изображён [https://neercHadamard gate.ifmo.ru/wiki/index.php?title=%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B3%D0%B5%D0%B9%D1%82%D1%8B гейт Адамара]]]Если

|}то <tex>u = 101</tex>.

Для начала инициализируем начальные <tex>n</tex> кубитов состоянием ноль. Проводим их всех через гейт Адамара (англ. ''Hadamard gate'')<ref>[https://neercen.ifmowikipedia.ruorg/wiki/index.php?title=%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B3%D0%B5%D0%B9%D1%82%D1%8B гейт АдамараHadamard_transform#Quantum_computing_applications Wikipedia {{---}} Hadamard gate] </ref> и получаем все возможные суперпозиции. Суперпозиции передаём в "черный ящик", который реализован в виде вентиля <tex>U_f</tex>. Сам результат опять пропускаем через [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B3%D0%B5%D0%B9%D1%82%D1%8B гейт Адамара]. В конце измеряем результат, который будет являться искомой <tex>u</tex>.

<tex>\mid -\bigr\rangle = \fracdfrac{1}{\sqrt{2}}(\mid 0\bigr\rangle - \mid 1\bigr\rangle)</tex>

Выразим неизвестную: <tex>\mid 00...0\ldots0\bigr\rangle\mid -\bigr\rangle\rightarrow\fracdfrac{1}{2^{n/2}} \Leftrightarrow \sum_\limits{x \mathop \in \{0,1\}^n} \mid x\bigr\rangle\mid-\bigr\rangle\rightarrow\fracdfrac{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>

'''''Квантовый алгоритм:''''' <tex>O(1)</tex>. Такая сложность достигается благодаря квантовым свойствам<ref>[https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80 квантовым свойстваВикипедия {{---}} Квантовый компьютер]</ref>, а конкретно параллелизму<ref>[https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9_%D0%BF%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D0%B8%D0%B7%D0%BC параллелизмуВикипедия {{---}} Квантовый параллелизм]</ref>.

|definition=Пусть имеется функция <tex> f: A \{0,1\}^n \rightarrow B \{0,1\} </tex>, такая, что <tex>f(x+\oplus S)=f(x)</tex> с неизвестным <tex>S\in \{0,1\}^n</tex>. Найти <tex>S</tex> за минимальное количество обращений к функции <tex>f</tex>.

|style="background-color:#FFF;padding:2px 10px"| '''001'''|style="background-color:#FFF;padding:2px 10px"| '''100'''}|style="background-color:#FFF;padding:2px 10px"| '''010'''|style="background-color:#FFF;padding:2px 10px"| '''000'''|style="background-color:#FFF;padding:2px 10px"| '''100'''|style="background-color:#FFF;padding:2px 10px"| '''001'''|}то <tex>S = 101110</tex>.

Задача похожа на задачу нахождения [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A5%D0%B5%D1%88[Хеш-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#.D0.92.D0.B2.D0.B5.D0.B4.D0.B5.D0.BD.D0.B8.D0.B5 таблица|коллизии]], так как необходимо найти два значения, при которых их выходные значения будет одинаковыми, затем вычислить между ними разницу, которая и будет ответом задачи.

Аналогично предыдущему алгоритму вычисляем все возможные суперпозиции передаём в "черный ящик", полученный результатопять пропускаем через гейт Адамара. В конце измеряем полученные значения, который будет которые будут являться некоторой строкой<tex>y</tex>, дающей ноль при скалярном умножении на искомую <tex>S</tex> ноль<tex>((y_1\wedge S_1)+(y_2\wedge S_2)+\ldots+(y_n\wedge S_n))</tex>. После <tex>n - 1</tex> итерации алгоритма получим систему из <tex>n - 1</tex> линейных уравнений; решив эту систему уравнений, найдём искомую <tex>S</tex>.:

\left\{\begin{casesalign} y_{1}^1S_1 + y_{1}^1S_2 + y_1 \dots + y_{n}^1S_n cdot s &= 0,\\ y_{1}^2S_1 + y_{2}^2S_2 + y_2 \dots + y_{n}^2S_n cdot s &= 0,\\ &\,\,\,\dotsvdots \\ y_{1}^{n-1}S_1 + y_{2}^{n-1}S_2 + \dots + y_{n}^{n-1}S_n cdot s &= 0.\\,\end{casesalign}\right.

* для решения СЛАУ <ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D1%85_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B9 СЛАУВикипедия {{---}} Система линейных алгебраических уравнений] </ref> необходим препроцессинг на классическом компьютере; * алгоритм может допускать ошибку(возможно, какие-то уравнения не будут линейно независимыми и система не будет иметь решений) с вероятностью <tex> ε < \fracdfrac{1}{4} </tex> при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для <tex>4m</tex> раз, вероятность будет равна: <tex> ε^{4m} < εe^{-m} </tex>. Например, при <tex> m = 10 </tex> вероятность будет <tex>ε^{40} < \fracdfrac{1}{20000} </tex>.

|definition=Пусть имеется функция <tex> f: \{0,...\ldots,N-1\} \rightarrow S </tex>, такая, что <tex>f((x+r(mod )\pmod N))=f(x)</tex> с неизвестным периодом <tex>r</tex>. Найти <tex>r</tex> за минимальное количество обращений к функции <tex>f</tex>.

'''Перефразируем задачу:''' у нас есть периодичная периодическая функция, для которой необходимо найти её период, путём нахождения [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A5%D0%B5%D1%88[Хеш-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#.D0.92.D0.B2.D0.B5.D0.B4.D0.B5.D0.BD.D0.B8.D0.B5 таблица|коллизии]]. Можно заметить, что алгоритм нахождения периода похож на алгоритм Саймона и фактически является его обобщением.

[[Файл: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>(далее '''''<tex>QFT'''''</tex>). '''''<tex>QFT''''' </tex> {{- --}} гейт, который реализует матрицу дискретного преобразования Фурье<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>QFT</tex> и получаем все возможные равновероятные суперпозиции всех булевых состояний <math>N</math> такие, что: <tex>|0 \rangle |0 \rangle \xrightarrow{QFT_N} \dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x \rangle |0 \rangle</tex> Суперпозиции передаём в гейт <tex>U_f</tex>, который реализует унитарное преобразование<ref>[https://ru.wikipedia.org/wiki/%D0%A3%D0%BD%D0%B8%D1%82%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80 Википедия {{---}} Унитарный оператор]</ref>, которое переводит <tex>|x \rangle |0 \rangle</tex> в <tex>|x \rangle |f(x) \rangle:</tex> <tex>\dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x \rangle |0 \rangle \xrightarrow{U_f} \dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x \rangle |f(x) \rangle</tex> Чтобы получить из этого периодическую суперпозицию, мы измеряем <tex>|f\rangle</tex> и поскольку <tex>f</tex> периодическая, её прообраз это <tex>f(x_0)</tex>, такой что <tex>\{x_0,x_0+r,x_0+2r,\ldots,x_0+(\dfrac{N}{r}-1)r)\}</tex>: <tex>\dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x \rangle |f(x) \rangle \xrightarrow{measure|f\rangle} \sqrt{\dfrac{r}{N}} \sum\limits_{i=0}^{N/r-1} |ir+x_0 \rangle |f(x_0) \rangle</tex> Теперь наш первый регистр находится в периодической суперпозиции, где период такой же, как период функции, но мы не можем сразу его просто измерить, потому что мы можем измерить другое значение <tex>|f\rangle</tex>, ведь мы получили периодическую суперпозицию, которая случайно линейно смещена и мы не получим никакой полезной информации. [[Файл: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> QFT_N = m\frac{1}{\sqrt{N}}\begin{vmatrix} 1 & 1 & 1 & \cdots & 1\\ 1 & ω^2 & w^3 & \cdots & ω^{N-1}\\ 1 & ω^3 & ω^6 & \cdots & ω^{2(N-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & ω^dfrac{N-1} & ω^{2(N-1)} & \cdots & ω^{(N-1)(N-1)}\end{vmatrixr}</tex>, где для некоторого целого <tex>ω = e^{\frac{2πi}{N}} m</tex>.

Так аналогично предыдущему алгоритмуТеперь мы повторяем алгоритм, но пользуясь '''''QFT''''', получаем результат чтобы получить несколько различных кратных <tex>m\fracdfrac{N}{r}</tex>. Выполнив данный алгоритм Как только у нас будет достаточно значений, мы можем вычислить их наибольший общий делитель<tex>n</texref> раз, найдём [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 наибольший Википедия {{---}} Наибольший общий делитель] от <tex>n</texref> полученных чисел, который, с некоторой вероятностью, будет искомым периодом <tex>r</tex>, при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.

''Примечание:'' Алгоритм нахождения периода используется в алгоритме Шора<ref>[https://en.wikipedia.org/wiki/Shor%27s_algorithm алгоритме ШораWikipedia {{---}} Shor's algorithm]</ref>, который позволяет решать задачу [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D1%82%D0%B5%D0%BB%D0%B8_[Разложение на множители (%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8Fфакторизация)#.D0.A3.D0.BB.D1.83.D1.87.D1.88.D0.B5.D0.BD.D0.BD.D0.B0.D1.8F_.D1.80.D0.B5.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.5Bmath.5DO.28.5Csqrt.7Bn.7D.29.5B.2Fmath.5D |факторизации числа]].

* [https://arxiv.org/pdf/quant-ph/0012114v1.pdf Алгоритм проверки чётности]* [https://en.wikipedia.org/wiki/Simon%27s_problem Алгоритм Саймона]* [https://en.wikipedia.org/wiki/Shor%27s_algorithm Алгоритм Шора]* [https://en.wikipedia.org/wiki<references /Grover%27s_algorithm Алгоритм Гровера]>