31
правка
Изменения
Новая страница: «{{Определение |definition='''Квантовый алгоритм''' представляет собой классический алгоритм, ко…»
{{Определение
|definition='''Квантовый алгоритм''' представляет собой классический алгоритм, который задает последовательность унитарных операций ([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 гейтов], или вентилей) с указанием, над какими именно кубитами их надо совершать.
}}
== Алгоритм проверки чётности ==
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: A \rightarrow B </tex>, такая, что <tex>f(x)=xu(mod 2)</tex> с неизвестным <tex>u</tex>. Найти <tex>u</tex> за минимальное количество обращений к функции <tex>f</tex>.
}}
=== Реализация ===
'''Пример:'''
[[Файл:Quantumalgorithm.Paritycheck.png|470px|thumb|right|В виде круга изображён [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 гейт Адамара]]]
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| <tex>x</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>000</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>001</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>010</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>011</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>100</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>101</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>110</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>111</tex>
|-
|style="background-color:#EEE"| <tex>f(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"| '''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'''
|}<tex>u = 101</tex>
Для начала инициализируем начальные <tex>n</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_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 = \frac{1}{\sqrt{2}}(\mid 0\bigr\rangle - \mid 1\bigr\rangle)</tex>
Выразим неизвестную: <tex>\mid 00...0\bigr\rangle\mid -\bigr\rangle\rightarrow\frac{1}{2^{n/2}} \Leftrightarrow \sum_\limits{x \mathop \in \{0,1\}^n} \mid x\bigr\rangle\mid-\bigr\rangle\rightarrow\frac{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(n)</tex>.
'''''Квантовый алгоритм:''''' <tex>O(1)</tex>. Такая сложность достигается благодаря [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 квантовым свойства], а конкретно [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 параллелизму].
== Алгоритм Саймона ==
=== Постановка задачи ===
{{Задача
|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|В виде круга изображён [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 гейт Адамара]]]
'''Пример:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| <tex>x</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>000</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>001</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>010</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>011</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>100</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>101</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>110</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>111</tex>
|-
|style="background-color:#EEE"| <tex>f(x)</tex>
|style="background-color:#FFF;padding:2px 10px"| '''000'''
|style="background-color:#FFF;padding:2px 10px"| '''010'''
|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 = 101</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>S</tex> ноль. После <tex>n - 1</tex> итерации алгоритма получим систему из <tex>n - 1</tex> линейных уравнений; решив эту систему уравнений, найдём искомую <tex>S</tex>.
<tex>
\begin{cases}
y_{1}^1S_1 + y_{1}^1S_2 + \dots + y_{n}^1S_n = 0,\\
y_{1}^2S_1 + y_{2}^2S_2 + \dots + y_{n}^2S_n = 0,\\
\dots\\
y_{1}^{n-1}S_1 + y_{2}^{n-1}S_2 + \dots + y_{n}^{n-1}S_n = 0.\\
\end{cases}
</tex>
'''Особенности алгоритма:'''
* для решения [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 СЛАУ] необходим препроцессинг на классическом компьютере;
* алгоритм может допускать ошибку(возможно, какие-то уравнения не будут линейно независимыми и система не будет иметь решений) с вероятностью <tex> ε < \frac{1}{4} </tex> при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для <tex>4m</tex> раз, вероятность будет равна: <tex> ε^{4m} < ε^{-m} </tex>. Например, при <tex> m = 10 </tex> вероятность будет <tex>ε^{40} < \frac{1}{20000} </tex>.
=== Сложность ===
'''''Классический алгоритм:''''' <tex>O(2^{n/2})</tex>.
'''''Квантовый алгоритм:''''' <tex>O(n)</tex>.
== Алгоритм нахождения периода ==
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: \{0,...,N-1\} \rightarrow S </tex>, такая, что <tex>f(x+r(mod 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 коллизии].
[[Файл:Quantumalgorithm.QFT.png|470px|thumb|right|]]
=== Реализация ===
[[Файл:Quantum algorithm. QFT. Graph3.jpg|220px|thumb|left|<tex>r</tex> и <tex>N/r</tex> - периоды функций]]
Чтобы решить задачу, воспользуемся [https://en.wikipedia.org/wiki/Quantum_Fourier_transform квантовым преобразованием Фурье](англ. ''Quantum Fourier transform''; далее '''''QFT'''''). '''''QFT''''' - гейт, который реализует матрицу [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 дискретного преобразования Фурье] над квантовым состоянием. Идея в следующем: есть периодическая функция с периодом <tex>r</tex>, после '''''QFT''''', получим новую периодическую функцию с периодом <tex>N/r</tex>, где <tex>N</tex> - модуль, с которым мы работаем.
<tex> QFT_N = \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 & ω^{N-1} & ω^{2(N-1)} & \cdots & ω^{(N-1)(N-1)}
\end{vmatrix}</tex>, где <tex>ω = e^{\frac{2πi}{N}} </tex>
Так аналогично предыдущему алгоритму, но пользуясь '''''QFT''''', получаем результат <tex>m\frac{N}{r}</tex>. Выполнив данный алгоритм <tex>n</tex> раз, найдём [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</tex> полученных чисел, который, с некоторой вероятностью, будет искомым периодом <tex>r</tex>, при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.
''Примечание:'' Алгоритм нахождения периода используется в [https://en.wikipedia.org/wiki/Shor%27s_algorithm алгоритме Шора], который позволяет решать задачу [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 факторизации числа].
=== Сложность ===
'''''Классический алгоритм:''''' <tex>O(r)</tex>.
'''''Квантовый алгоритм:''''' <tex>O(\log N)</tex>.
== См.также ==
* [http://www.quantumplayground.net Веб-приложение Chrome, использующее WebGL, чтобы имитировать до 22 кубитов на GPU]
* [[Квантовые гейты]]
* [https://pdfs.semanticscholar.org/d9dc/64159f94bde3fbe81b172e60369f3ee410f4.pdf Алгоритм Гровера]
==Примечания==
* [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/Grover%27s_algorithm Алгоритм Гровера]
== Источники информации ==
* [http://old.kpfu.ru/eng/departments/ktk/RESOURCE/posobie.pdf Гайнутдинова А. Ф. "Квантовые вычисления"]
* [http://mmi.sgu.ru/sites/mmi.sgu.ru/files/462-477solovyev.pdf Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 1. Квантовые компьютеры"]
* [https://cyberleninka.ru/article/v/kvantovye-kompyutery-i-kvantovye-algoritmy-chast-2-kvantovye-algoritmy Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 2. Квантовые алгоритмы"]
[[Категория: Дискретная математика и алгоритмы]]
|definition='''Квантовый алгоритм''' представляет собой классический алгоритм, который задает последовательность унитарных операций ([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 гейтов], или вентилей) с указанием, над какими именно кубитами их надо совершать.
}}
== Алгоритм проверки чётности ==
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: A \rightarrow B </tex>, такая, что <tex>f(x)=xu(mod 2)</tex> с неизвестным <tex>u</tex>. Найти <tex>u</tex> за минимальное количество обращений к функции <tex>f</tex>.
}}
=== Реализация ===
'''Пример:'''
[[Файл:Quantumalgorithm.Paritycheck.png|470px|thumb|right|В виде круга изображён [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 гейт Адамара]]]
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| <tex>x</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>000</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>001</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>010</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>011</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>100</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>101</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>110</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>111</tex>
|-
|style="background-color:#EEE"| <tex>f(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"| '''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'''
|}<tex>u = 101</tex>
Для начала инициализируем начальные <tex>n</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_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 = \frac{1}{\sqrt{2}}(\mid 0\bigr\rangle - \mid 1\bigr\rangle)</tex>
Выразим неизвестную: <tex>\mid 00...0\bigr\rangle\mid -\bigr\rangle\rightarrow\frac{1}{2^{n/2}} \Leftrightarrow \sum_\limits{x \mathop \in \{0,1\}^n} \mid x\bigr\rangle\mid-\bigr\rangle\rightarrow\frac{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(n)</tex>.
'''''Квантовый алгоритм:''''' <tex>O(1)</tex>. Такая сложность достигается благодаря [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 квантовым свойства], а конкретно [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 параллелизму].
== Алгоритм Саймона ==
=== Постановка задачи ===
{{Задача
|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|В виде круга изображён [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 гейт Адамара]]]
'''Пример:'''
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| <tex>x</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>000</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>001</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>010</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>011</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>100</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>101</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>110</tex>
!style="background-color:#FFF;padding:2px 10px"| <tex>111</tex>
|-
|style="background-color:#EEE"| <tex>f(x)</tex>
|style="background-color:#FFF;padding:2px 10px"| '''000'''
|style="background-color:#FFF;padding:2px 10px"| '''010'''
|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 = 101</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>S</tex> ноль. После <tex>n - 1</tex> итерации алгоритма получим систему из <tex>n - 1</tex> линейных уравнений; решив эту систему уравнений, найдём искомую <tex>S</tex>.
<tex>
\begin{cases}
y_{1}^1S_1 + y_{1}^1S_2 + \dots + y_{n}^1S_n = 0,\\
y_{1}^2S_1 + y_{2}^2S_2 + \dots + y_{n}^2S_n = 0,\\
\dots\\
y_{1}^{n-1}S_1 + y_{2}^{n-1}S_2 + \dots + y_{n}^{n-1}S_n = 0.\\
\end{cases}
</tex>
'''Особенности алгоритма:'''
* для решения [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 СЛАУ] необходим препроцессинг на классическом компьютере;
* алгоритм может допускать ошибку(возможно, какие-то уравнения не будут линейно независимыми и система не будет иметь решений) с вероятностью <tex> ε < \frac{1}{4} </tex> при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для <tex>4m</tex> раз, вероятность будет равна: <tex> ε^{4m} < ε^{-m} </tex>. Например, при <tex> m = 10 </tex> вероятность будет <tex>ε^{40} < \frac{1}{20000} </tex>.
=== Сложность ===
'''''Классический алгоритм:''''' <tex>O(2^{n/2})</tex>.
'''''Квантовый алгоритм:''''' <tex>O(n)</tex>.
== Алгоритм нахождения периода ==
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: \{0,...,N-1\} \rightarrow S </tex>, такая, что <tex>f(x+r(mod 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 коллизии].
[[Файл:Quantumalgorithm.QFT.png|470px|thumb|right|]]
=== Реализация ===
[[Файл:Quantum algorithm. QFT. Graph3.jpg|220px|thumb|left|<tex>r</tex> и <tex>N/r</tex> - периоды функций]]
Чтобы решить задачу, воспользуемся [https://en.wikipedia.org/wiki/Quantum_Fourier_transform квантовым преобразованием Фурье](англ. ''Quantum Fourier transform''; далее '''''QFT'''''). '''''QFT''''' - гейт, который реализует матрицу [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 дискретного преобразования Фурье] над квантовым состоянием. Идея в следующем: есть периодическая функция с периодом <tex>r</tex>, после '''''QFT''''', получим новую периодическую функцию с периодом <tex>N/r</tex>, где <tex>N</tex> - модуль, с которым мы работаем.
<tex> QFT_N = \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 & ω^{N-1} & ω^{2(N-1)} & \cdots & ω^{(N-1)(N-1)}
\end{vmatrix}</tex>, где <tex>ω = e^{\frac{2πi}{N}} </tex>
Так аналогично предыдущему алгоритму, но пользуясь '''''QFT''''', получаем результат <tex>m\frac{N}{r}</tex>. Выполнив данный алгоритм <tex>n</tex> раз, найдём [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</tex> полученных чисел, который, с некоторой вероятностью, будет искомым периодом <tex>r</tex>, при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.
''Примечание:'' Алгоритм нахождения периода используется в [https://en.wikipedia.org/wiki/Shor%27s_algorithm алгоритме Шора], который позволяет решать задачу [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 факторизации числа].
=== Сложность ===
'''''Классический алгоритм:''''' <tex>O(r)</tex>.
'''''Квантовый алгоритм:''''' <tex>O(\log N)</tex>.
== См.также ==
* [http://www.quantumplayground.net Веб-приложение Chrome, использующее WebGL, чтобы имитировать до 22 кубитов на GPU]
* [[Квантовые гейты]]
* [https://pdfs.semanticscholar.org/d9dc/64159f94bde3fbe81b172e60369f3ee410f4.pdf Алгоритм Гровера]
==Примечания==
* [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/Grover%27s_algorithm Алгоритм Гровера]
== Источники информации ==
* [http://old.kpfu.ru/eng/departments/ktk/RESOURCE/posobie.pdf Гайнутдинова А. Ф. "Квантовые вычисления"]
* [http://mmi.sgu.ru/sites/mmi.sgu.ru/files/462-477solovyev.pdf Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 1. Квантовые компьютеры"]
* [https://cyberleninka.ru/article/v/kvantovye-kompyutery-i-kvantovye-algoritmy-chast-2-kvantovye-algoritmy Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 2. Квантовые алгоритмы"]
[[Категория: Дискретная математика и алгоритмы]]
