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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|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='''Квантовый алгоритм''' (англ. ''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: A \rightarrow B </tex>, такая, что <tex>f(x)=xu\bmod 2</tex> с неизвестным <tex>u</tex>. Найти <tex>u</tex> за минимальное количество обращений к функции <tex>f</tex>.
 
}}
 
}}
 
'''Пример:'''
 
'''Пример:'''
Строка 37: Строка 37:
 
<tex>\mid -\bigr\rangle = \dfrac{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\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>\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>
  
 
=== Сложность ===  
 
=== Сложность ===  
Строка 98: Строка 98:
 
=== Постановка задачи ===
 
=== Постановка задачи ===
 
{{Задача
 
{{Задача
|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\bmod N)=f(x)</tex> с неизвестным периодом <tex>r</tex>. Найти <tex>r</tex> за минимальное количество обращений к функции <tex>f</tex>.
 
}}
 
}}
  
Строка 104: Строка 104:
 
[[Файл: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> - периоды функций]]
+
[[Файл: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> - модуль, с которым мы работаем.
+
Чтобы решить задачу, воспользуемся квантовым преобразованием Фурье<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
 
<tex> QFT_N = \dfrac{1}{\sqrt{N}}\begin{vmatrix} 1 & 1 & 1 & \cdots & 1

Версия 21:52, 30 октября 2018

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


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

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

Задача:
Пусть имеется функция [math] f: A \rightarrow B [/math], такая, что [math]f(x)=xu\bmod 2[/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) и получаем все возможные суперпозиции. Суперпозиции передаём в "черный ящик", который реализован в виде вентиля [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]. Такая сложность достигается благодаря квантовым свойства[2], а конкретно параллелизму[3].

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

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

Задача:
Пусть имеется функция [math] f: A \rightarrow B [/math], такая, что [math]f(x+S)=f(x)[/math] с неизвестным [math]S[/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] 000 010 001 100 010 000 100 001
[math]S = 101[/math]

Реализация

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

Аналогично предыдущему алгоритму вычисляем результат, который будет являться некоторой строкой, дающей при скалярном умножении на искомую [math]S[/math] ноль. После [math]n - 1[/math] итерации алгоритма получим систему из [math]n - 1[/math] линейных уравнений; решив эту систему уравнений, найдём искомую [math]S[/math].

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

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

  • для решения СЛАУ [4] необходим препроцессинг на классическом компьютере;
  • алгоритм может допускать ошибку(возможно, какие-то уравнения не будут линейно независимыми и система не будет иметь решений) с вероятностью [math] ε \lt \dfrac{1}{4} [/math] при одном цикле прохода алгоритма. Этого можно избежать, если прогнать алгоритм несколько раз, так для [math]4m[/math] раз, вероятность будет равна: [math] ε^{4m} \lt ε^{-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\bmod N)=f(x)[/math] с неизвестным периодом [math]r[/math]. Найти [math]r[/math] за минимальное количество обращений к функции [math]f[/math].


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

Quantumalgorithm.QFT.png

Реализация

[math]r[/math] и [math]N/r[/math] — периоды функций

Чтобы решить задачу, воспользуемся квантовым преобразованием Фурье[5](англ. Quantum Fourier transform; далее QFT). QFT — гейт, который реализует матрицу дискретного преобразования Фурье[6] над квантовым состоянием. Идея в следующем: есть периодическая функция с периодом [math]r[/math], после QFT, получим новую периодическую функцию с периодом [math]N/r[/math], где [math]N[/math] — модуль, с которым мы работаем.

[math] QFT_N = \dfrac{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}[/math], где [math]ω = e^{\dfrac{2πi}{N}} [/math]

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

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

Сложность

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

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

См.также

Примечания

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