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

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

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

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

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

Задача:

Пусть имеется функция $f: A \rightarrow B$, такая, что $f(x)=xu\pmod2$ с неизвестным $u$. Найти $u$ за минимальное количество обращений к функции $f$.

Пример:

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

$x$	$000$	$001$	$010$	$011$	$100$	$101$	$110$	$111$
$f(x)$	0	1	0	1	0	1	0	1

$u = 101$

Реализация

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

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

Выразим неизвестную: $\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$

Сложность

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

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

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

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

Задача:

Пусть имеется функция $f: A \rightarrow B$, такая, что $f(x+S)=f(x)$ с неизвестным $S$. Найти $S$ за минимальное количество обращений к функции $f$.

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

Пример:

$x$	$000$	$001$	$010$	$011$	$100$	$101$	$110$	$111$
$f(x)$	000	010	001	100	010	000	100	001

$S = 101$

Реализация

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

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

$\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}$

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

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

Сложность

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

Квантовый алгоритм: $O(n)$.

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

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

Задача:

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

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

Реализация

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

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

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

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

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

Сложность

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

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

См.также

• Квантовые гейты
• Алгоритм Гровера
• Алгоритм Шора
• Веб-приложение, использующее WebGL, чтобы имитировать до 22 кубитов на GPU
• Веб-приложение, для написания и визуализации квантовых алгоритмов
• Языки программирования для квантового компьютера

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

• Алгоритм проверки чётности
• Алгоритм Саймона
• Гайнутдинова А. Ф. "Квантовые вычисления"
• Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 1. Квантовые компьютеры"
• Соловьев В. М. "Квантовые компьютеры и квантовые алгоритмы. Часть 2. Квантовые алгоритмы"
• Квантовое преобразование Фурье