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

Определение:

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

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

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

Задача:

Пусть имеется функция [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) и получаем все возможные суперпозиции. Суперпозиции передаём в "черный ящик", который реализован в виде вентиля [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]. Такая сложность достигается благодаря квантовым свойствам, а конкретно параллелизму.

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

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

Задача:

Пусть имеется функция [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].

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

• для решения СЛАУ необходим препроцессинг на классическом компьютере;
• алгоритм может допускать ошибку(возможно, какие-то уравнения не будут линейно независимыми и система не будет иметь решений) с вероятностью [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].

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

Реализация

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

Чтобы решить задачу, воспользуемся квантовым преобразованием Фурье(англ. Quantum Fourier transform; далее QFT). QFT — гейт, который реализует матрицу дискретного преобразования Фурье над квантовым состоянием. Идея в следующем: есть периодическая функция с периодом [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]m[/math] — какое-то произвольное (случайное) натуральное число, возникающее из того, что форма рационального числа [math]\dfrac{m}{r}[/math] не единственна в своем роде, [math]N[/math] — модуль, [math]r[/math] — период. Выполнив данный алгоритм [math]n[/math] раз, найдём наибольший общий делитель от [math]n[/math] полученных чисел, который, с некоторой вероятностью, будет искомым периодом [math]r[/math], при этом вероятность ошибки будет экспоненциально падать с каждой попыткой.

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

Сложность

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

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

См.также

• Квантовые гейты

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

• Implementation of a quantum algorithm to solve Bernstein-Vazirani’s parity problem without entanglement on an ensemble quantum computer
• Wikipedia — Simon's problem
• Гайнутдинова А. Ф. "Квантовые вычисления"
• Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 1. Квантовые компьютеры"
• Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 2. Квантовые алгоритмы"
• Wikipedia — Quantum Fourier transform
• Quantum parity algorithms as oracle calls, and application in Grover Database search
• Wikipedia — Shor's algorithm
• Веб-приложение, использующее WebGL, чтобы имитировать до 22 кубитов на GPU
• Веб-приложение, для написания и визуализации квантовых алгоритмов
• Языки программирования для квантового компьютера