Изменения

Перейти к: навигация, поиск

Квантовые алгоритмы

807 байт добавлено, 01:11, 9 ноября 2018
Нет описания правки
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: A \{0,1\}^n \rightarrow B \{0,1\} </tex>, такая, что <tex>f(x)=xux\cdot u\pmod2\equiv (x_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|В виде круга изображён Hadamard gate.]]
Если
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| <tex>x</tex>
|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'''
|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>.
'''''Классический алгоритм:''''' <tex>O(n)</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>.
}}
'''Пример:'''
[[Файл:Quantumalgorithm.Simonalgorithm.png|470px|thumb|right|В виде круга изображён Hadamard gate.]]
'''Пример:'''Если
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| <tex>x</tex>
|-
|style="background-color:#EEE"| <tex>f(x)</tex>
|style="background-color:#FFF;padding:2px 10px"| '''101'''
|style="background-color:#FFF;padding:2px 10px"| '''010'''
|style="background-color:#FFF;padding:2px 10px"| '''000'''
|style="background-color:#FFF;padding:2px 10px"| '''110'''
|style="background-color:#FFF;padding:2px 10px"| '''000'''
|style="background-color:#FFF;padding:2px 10px"| '''110'''
|style="background-color:#FFF;padding:2px 10px"| '''101'''
|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 = 101110</tex>.
=== Реализация ===
Задача похожа на задачу нахождения [[Хеш-таблица|коллизии]], так как необходимо найти два значения, при которых их выходные значения будет одинаковыми, затем вычислить между ними разницу, которая и будет ответом задачи.
Аналогично предыдущему алгоритму вычисляем все возможные суперпозиции передаём в "черный ящик", полученный результатопять пропускаем через гейт Адамара. В конце измеряем полученные значения, который будет которые будут являться некоторой строкой<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>.:
<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.
</tex>
 
где <tex>y_i \cdot s = y_{i1} s_1 + y_{i2} s_2 + \dots + y_{in} s_n</tex>, и <tex>y_{ij}, s_j \in \{0, 1\}</tex>, при <tex>i=1, \dots, n-1</tex> и <tex>j=1, \dots, n</tex>.
'''Особенности алгоритма:'''
* для решения СЛАУ <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> ε < \dfrac{1}{4} </tex> при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для <tex>4m</tex> раз, вероятность будет равна: <tex> ε^{4m} < εe^{-m} </tex>. Например, при <tex> m = 10 </tex> вероятность будет <tex>ε^{40} < \dfrac{1}{20000} </tex>.
=== Сложность ===
=== Постановка задачи ===
{{Задача
|definition=Пусть имеется функция <tex> f: \{0,\ldots,N-1\} \rightarrow S </tex>, такая, что <tex>f((x+r)\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>\dfrac{m}{r}</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://arxiv.org/pdf/quant-ph/0012114v1.pdf Алгоритм проверки чётностиImplementation of a quantum algorithm to solve Bernstein-Vazirani’s parity problem without entanglement on an ensemble quantum computer]* [https://en.wikipedia.org/wiki/Simon%27s_problem Алгоритм СаймонаWikipedia {{---}} Simon's problem]
* [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. Квантовые алгоритмы"]
* [https://en.wikipedia.org/wiki/Quantum_Fourier_transform Квантовое преобразование ФурьеWikipedia {{---}} Quantum Fourier transform]* [https://pdfs.semanticscholar.org/d9dc/64159f94bde3fbe81b172e60369f3ee410f4.pdf Алгоритм ГровераQuantum parity algorithms as oracle calls, and application in Grover Database search]* [https://en.wikipedia.org/wiki/Shor%27s_algorithm Алгоритм ШораWikipedia {{---}} Shor's algorithm]
* [http://www.quantumplayground.net Веб-приложение, использующее WebGL, чтобы имитировать до 22 кубитов на GPU]
* [https://sites.google.com/view/quantum-kit/ Веб-приложение, для написания и визуализации квантовых алгоритмов]
21
правка

Навигация