Квантовые алгоритмы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|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='''Квантовый алгоритм''' (англ. ''quantum algorithm'') представляет собой классический алгоритм, который задает последовательность унитарных операций ([[Квантовые гейты|гейтов]], или вентилей) с указанием, над какими именно кубитами<ref>[https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82 Википедия {{---}} Кубит]</ref> их надо совершать.
 
}}
 
}}
  
Строка 6: Строка 6:
 
=== Постановка задачи ===
 
=== Постановка задачи ===
 
{{Задача
 
{{Задача
|definition=Пусть имеется функция <tex> f: A \rightarrow B </tex>, такая, что <tex>f(x)=xu(mod 2)</tex> с неизвестным <tex>u</tex>. Найти <tex>u</tex> за минимальное количество обращений к функции <tex>f</tex>.
+
|definition=Пусть имеется функция <tex> f: \{0,1\}^n \rightarrow \{0,1\} </tex>, такая, что <tex>f(x)=x\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|В виде круга изображён [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 гейт Адамара]]]
+
[[Файл:Quantumalgorithm.Paritycheck.png|470px|thumb|right|В виде круга изображён Hadamard gate.]]
 +
Если
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| <tex>x</tex>
 
!style="background-color:#EEE"| <tex>x</tex>
Строка 30: Строка 31:
 
|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"| '''0'''
|}<tex>u = 101</tex>
+
|}
 +
то <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>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>\mid -\bigr\rangle = \frac{1}{\sqrt{2}}(\mid 0\bigr\rangle - \mid 1\bigr\rangle)</tex>
+
<tex>\mid -\bigr\rangle = \dfrac{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>\mid 00\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>
  
 
=== Сложность ===  
 
=== Сложность ===  
 
'''''Классический алгоритм:''''' <tex>O(n)</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 параллелизму].
+
'''''Квантовый алгоритм:''''' <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 \rightarrow B </tex>, такая, что <tex>f(x+S)=f(x)</tex> с неизвестным <tex>S</tex>. Найти <tex>S</tex> за минимальное количество обращений к функции <tex>f</tex>.
+
|definition=Пусть имеется функция <tex> f: \{0,1\}^n \rightarrow \{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|В виде круга изображён [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 гейт Адамара]]]
 
 
'''Пример:'''
 
'''Пример:'''
 +
[[Файл:Quantumalgorithm.Simonalgorithm.png|470px|thumb|right|В виде круга изображён Hadamard gate.]]
 +
Если
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| <tex>x</tex>
 
!style="background-color:#EEE"| <tex>x</tex>
Строка 63: Строка 66:
 
|-
 
|-
 
|style="background-color:#EEE"| <tex>f(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"| '''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"| '''010'''
|style="background-color:#FFF;padding:2px 10px"| '''001'''
+
|}
|style="background-color:#FFF;padding:2px 10px"| '''100'''
+
то <tex>S = 110</tex>.
|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>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>
 
<tex>
\begin{cases}
+
\left\{
    y_{1}^1S_1 + y_{1}^1S_2 + \dots + y_{n}^1S_n = 0,\\
+
\begin{align}
    y_{1}^2S_1 + y_{2}^2S_2 + \dots + y_{n}^2S_n = 0,\\
+
y_1 \cdot s &= 0, \\
    \dots\\
+
y_2 \cdot s &= 0, \\
    y_{1}^{n-1}S_1 + y_{2}^{n-1}S_2 + \dots + y_{n}^{n-1}S_n = 0.\\
+
&\,\,\,\vdots \\
\end{cases}
+
y_{n-1} \cdot s &= 0,
 +
\end{align}
 +
\right.
 
</tex>
 
</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>.
  
 
'''Особенности алгоритма:'''
 
'''Особенности алгоритма:'''
* для решения [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>[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> ε < \frac{1}{4} </tex> при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для <tex>4m</tex> раз, вероятность будет равна: <tex> ε^{4m} < ε^{-m} </tex>. Например, при <tex> m = 10 </tex> вероятность будет <tex>ε^{40} < \frac{1}{20000} </tex>.
+
* алгоритм может допускать ошибку(возможно, какие-то уравнения не будут линейно независимыми и система не будет иметь решений) с вероятностью <tex> ε < \dfrac{1}{4} </tex> при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для <tex>4m</tex> раз, вероятность будет равна: <tex> ε^{4m} < e^{-m} </tex>. Например, при <tex> m = 10 </tex> вероятность будет <tex>ε^{40} < \dfrac{1}{20000} </tex>.
  
 
=== Сложность ===  
 
=== Сложность ===  
Строка 98: Строка 106:
 
=== Постановка задачи ===
 
=== Постановка задачи ===
 
{{Задача
 
{{Задача
|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>.
+
|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>.
 
}}
 
}}
  
'''Перефразируем задачу:''' у нас есть периодичная функция, для которой необходимо найти её период, путём нахождения [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|]]
 
[[Файл: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>(далее <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> такие, что:
Чтобы решить задачу, воспользуемся [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>|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> QFT_N = \frac{1}{\sqrt{N}}\begin{vmatrix} 1 & 1 & 1 & \cdots & 1
+
<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>.
\\ 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>, при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.
+
Так мы уже можем измерить и извлечь <tex>m\dfrac{N}{r}</tex>, для некоторого целого <tex>m</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>\dfrac{N}{r}</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>r</tex>, при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.
 +
 
 +
''Примечание:'' Алгоритм нахождения периода используется в алгоритме Шора<ref>[https://en.wikipedia.org/wiki/Shor%27s_algorithm Wikipedia {{---}} Shor's algorithm]</ref>, который позволяет решать задачу [[Разложение на множители (факторизация)|факторизации числа]].
  
 
=== Сложность ===  
 
=== Сложность ===  
Строка 122: Строка 140:
  
 
'''''Квантовый алгоритм:''''' <tex>O(\log N)</tex>.
 
'''''Квантовый алгоритм:''''' <tex>O(\log N)</tex>.
 +
 
== См.также ==
 
== См.также ==
 
* [[Квантовые гейты]]
 
* [[Квантовые гейты]]
* [https://pdfs.semanticscholar.org/d9dc/64159f94bde3fbe81b172e60369f3ee410f4.pdf Алгоритм Гровера]
 
* [http://www.quantumplayground.net Веб-приложение, использующее WebGL, чтобы имитировать до 22 кубитов на GPU]
 
* [https://sites.google.com/view/quantum-kit/ Веб-приложение, для написания и визуализации квантовых алгоритмов]
 
* [https://habr.com/company/mailru/blog/350208/ Языки программирования для квантового компьютера]
 
  
 
==Примечания==
 
==Примечания==
* [https://arxiv.org/pdf/quant-ph/0012114v1.pdf Алгоритм проверки чётности]
+
 
* [https://en.wikipedia.org/wiki/Simon%27s_problem Алгоритм Саймона]
+
<references />
* [https://en.wikipedia.org/wiki/Shor%27s_algorithm Алгоритм Шора]
 
* [https://en.wikipedia.org/wiki/Grover%27s_algorithm Алгоритм Гровера]
 
  
 
== Источники информации ==
 
== Источники информации ==
 +
* [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://old.kpfu.ru/eng/departments/ktk/RESOURCE/posobie.pdf Гайнутдинова А. Ф. "Квантовые вычисления"]
 
* [http://mmi.sgu.ru/sites/mmi.sgu.ru/files/462-477solovyev.pdf Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 1. Квантовые компьютеры"]
 
* [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://cyberleninka.ru/article/v/kvantovye-kompyutery-i-kvantovye-algoritmy-chast-2-kvantovye-algoritmy Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 2. Квантовые алгоритмы"]
* [https://en.wikipedia.org/wiki/Quantum_Fourier_transform Квантовое преобразование Фурье]
+
* [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/ Веб-приложение, для написания и визуализации квантовых алгоритмов]
 +
* [https://habr.com/company/mailru/blog/350208/ Языки программирования для квантового компьютера]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Схемы из функциональных элементов]]

Текущая версия на 19:32, 4 сентября 2022

Определение:
Квантовый алгоритм (англ. quantum algorithm) представляет собой классический алгоритм, который задает последовательность унитарных операций (гейтов, или вентилей) с указанием, над какими именно кубитами[1] их надо совершать.


Алгоритм проверки чётности

Постановка задачи

Задача:
Пусть имеется функция [math] f: \{0,1\}^n \rightarrow \{0,1\} [/math], такая, что [math]f(x)=x\cdot u\pmod2 \equiv (x_1\wedge u_1) \oplus (x_2\wedge u_2)\oplus\ldots\oplus(x_n\wedge u_n)[/math]с неизвестным [math]u[/math]. Найти [math]u[/math] за минимальное количество обращений к функции [math]f[/math].

Пример:

В виде круга изображён Hadamard gate.

Если

[math]x[/math] [math]000[/math] [math]001[/math] [math]010[/math] [math]011[/math] [math]100[/math] [math]101[/math] [math]110[/math] [math]111[/math]
[math]f(x)[/math] 0 1 0 1 1 0 1 0

то [math]u = 101[/math].

Реализация

Для начала инициализируем начальные [math]n[/math] кубитов состоянием ноль. Проводим их всех через гейт Адамара (англ. Hadamard gate)[2] и получаем все возможные суперпозиции. Суперпозиции передаём в "черный ящик", который реализован в виде вентиля [math]U_f[/math]. Сам результат опять пропускаем через гейт Адамара. В конце измеряем результат, который будет являться искомой [math]u[/math].

В качестве бита, который будет содержать ответ, будет использоваться суперпозиция: [math]\mid -\bigr\rangle = \dfrac{1}{\sqrt{2}}(\mid 0\bigr\rangle - \mid 1\bigr\rangle)[/math]

Выразим неизвестную: [math]\mid 00\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[/math]

Сложность

Классический алгоритм: [math]O(n)[/math].

Квантовый алгоритм: [math]O(1)[/math]. Такая сложность достигается благодаря квантовым свойствам[3], а конкретно параллелизму[4].

Алгоритм Саймона

Постановка задачи

Задача:
Пусть имеется функция [math] f: \{0,1\}^n \rightarrow \{0,1\} [/math], такая, что [math]f(x\oplus S)=f(x)[/math] с неизвестным [math]S \in \{0,1\}^n[/math]. Найти [math]S[/math] за минимальное количество обращений к функции [math]f[/math].

Пример:

В виде круга изображён Hadamard gate.

Если

[math]x[/math] [math]000[/math] [math]001[/math] [math]010[/math] [math]011[/math] [math]100[/math] [math]101[/math] [math]110[/math] [math]111[/math]
[math]f(x)[/math] 101 010 000 110 000 110 101 010

то [math]S = 110[/math].

Реализация

Задача похожа на задачу нахождения коллизии, так как необходимо найти два значения, при которых их выходные значения будет одинаковыми, затем вычислить между ними разницу, которая и будет ответом задачи.

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

[math] \left\{ \begin{align} y_1 \cdot s &= 0, \\ y_2 \cdot s &= 0, \\ &\,\,\,\vdots \\ y_{n-1} \cdot s &= 0, \end{align} \right. [/math]

где [math]y_i \cdot s = y_{i1} s_1 + y_{i2} s_2 + \dots + y_{in} s_n[/math], и [math]y_{ij}, s_j \in \{0, 1\}[/math], при [math]i=1, \dots, n-1[/math] и [math]j=1, \dots, n[/math].

Особенности алгоритма:

  • для решения СЛАУ [5] необходим препроцессинг на классическом компьютере;
  • алгоритм может допускать ошибку(возможно, какие-то уравнения не будут линейно независимыми и система не будет иметь решений) с вероятностью [math] ε \lt \dfrac{1}{4} [/math] при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для [math]4m[/math] раз, вероятность будет равна: [math] ε^{4m} \lt e^{-m} [/math]. Например, при [math] m = 10 [/math] вероятность будет [math]ε^{40} \lt \dfrac{1}{20000} [/math].

Сложность

Классический алгоритм: [math]O(2^{n/2})[/math].

Квантовый алгоритм: [math]O(n)[/math].

Алгоритм нахождения периода

Постановка задачи

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


Перефразируем задачу: у нас есть периодическая функция, для которой необходимо найти период путём нахождения коллизии. Можно заметить, что алгоритм нахождения периода похож на алгоритм Саймона и фактически является его обобщением.

Quantumalgorithm.QFT.png

Реализация

Чтобы решить задачу, воспользуемся квантовым преобразованием Фурье[6](далее [math]QFT[/math]). [math]QFT[/math] — гейт, который реализует матрицу дискретного преобразования Фурье[7] над квантовым состоянием. Для начала инициализируем начальные кубиты состоянием ноль. Проводим их всех через гейт [math]QFT[/math] и получаем все возможные равновероятные суперпозиции всех булевых состояний [math]N[/math] такие, что:

[math]|0 \rangle |0 \rangle \xrightarrow{QFT_N} \dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x \rangle |0 \rangle[/math]

Суперпозиции передаём в гейт [math]U_f[/math], который реализует унитарное преобразование[8], которое переводит [math]|x \rangle |0 \rangle[/math] в [math]|x \rangle |f(x) \rangle:[/math]

[math]\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[/math]

Чтобы получить из этого периодическую суперпозицию, мы измеряем [math]|f\rangle[/math] и поскольку [math]f[/math] периодическая, её прообраз это [math]f(x_0)[/math], такой что [math]\{x_0,x_0+r,x_0+2r,\ldots,x_0+(\dfrac{N}{r}-1)r)\}[/math]:

[math]\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[/math]

Теперь наш первый регистр находится в периодической суперпозиции, где период такой же, как период функции, но мы не можем сразу его просто измерить, потому что мы можем измерить другое значение [math]|f\rangle[/math], ведь мы получили периодическую суперпозицию, которая случайно линейно смещена и мы не получим никакой полезной информации.

Quantum algorithm. QFT. Graph3.jpg
Поэтому вместо этого мы применим [math]QFT[/math] и будем полагаться на его свойства, чтобы получить информацию, которая нам нужна. Идея в следующем: есть периодическая функция с периодом [math]r[/math], после применения [math]QFT[/math], получим новую периодическую функцию с периодом [math]N/r[/math], где [math]N[/math] — модуль, с которым мы работаем:

[math]\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[/math], где [math]φ_i[/math] — некоторый неважный период, возникающий из линейного сдвига [math]x_0[/math].

Так мы уже можем измерить и извлечь [math]m\dfrac{N}{r}[/math], для некоторого целого [math]m[/math].

Теперь мы повторяем алгоритм, чтобы получить несколько различных кратных [math]\dfrac{N}{r}[/math]. Как только у нас будет достаточно значений, мы можем вычислить их наибольший общий делитель[9], который, с некоторой вероятностью, будет искомым периодом [math]r[/math], при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.

Примечание: Алгоритм нахождения периода используется в алгоритме Шора[10], который позволяет решать задачу факторизации числа.

Сложность

Классический алгоритм: [math]O(r)[/math].

Квантовый алгоритм: [math]O(\log N)[/math].

См.также

Примечания

Источники информации