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

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

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

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

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

Задача:

Пусть имеется функция $f: \{0,1\}^n \rightarrow \{0,1\}$, такая, что $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)$с неизвестным $u$. Найти $u$ за минимальное количество обращений к функции $f$.

Пример:

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

Если

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

то $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: \{0,1\}^n \rightarrow \{0,1\}$, такая, что $f(x\oplus S)=f(x)$ с неизвестным $S \in \{0,1\}^n$. Найти $S$ за минимальное количество обращений к функции $f$.

Пример:

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

Если

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

то $S = 110$.

Реализация

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

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

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

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

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

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

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

Реализация

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

$|0 \rangle |0 \rangle \xrightarrow{QFT_N} \dfrac{1}{\sqrt{N}} \sum\limits_{x=0}^{N-1} |x \rangle |0 \rangle$

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

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

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

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

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

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

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

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

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

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

Сложность

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

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

См.также

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

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

• 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
• Веб-приложение, для написания и визуализации квантовых алгоритмов
• Языки программирования для квантового компьютера