Поделиться через

Основные сведения о квантовых оракулах

Oracle, $O$, представляет собой неэкспонированную операцию, которая используется в качестве входных данных для другого алгоритма. Часто такие операции определяются с помощью классической функции $f : \{0, 1\}^n \to \{0, 1\}^m$, которая принимает двоичный вход размером в $n-бит и создает $m-разрядные двоичные выходные данные$. Для этого рассмотрим определенные двоичные входные данные $x = (x_{0}, x_{1}, \dots, x_{n-1})$. Вы можете пометить состояния кубита как $\ket{\vec{x}}=\ket{x_{{0}}\otimes\ket{x_{1}}\otimes\cdots\otimes\ket{x_{n-1.}}$

Вы можете сначала попытаться определить $O$, так чтобы $O\ket{x}=f(x)\ket{, но этот метод имеет несколько проблем. Во-первых, $f$ может иметь другой размер входных и выходных данных ($n \ne m$), чтобы применение $O$ изменило количество кубитов в регистре. Во-вторых, даже если $n = m$, функция может быть невертимой: если $f(x) = f(y)$ для некоторых $x \ne y$, то $O\ket{x}= O\ket{y}$, но $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$. Это означает, что вы не можете создать сопряжённую операцию $O^\dagger$, и для оракулов должно быть определено сопряженное.

Определение оракула по его влиянию на базисные вычислительные состояния

Вы можете справиться с обеими этими проблемами, введя второй реестр $кубитов для$ хранения ответа. Затем определите эффект оракула во всех вычислительных состояниях: для всех $x \in \{0, 1\}^n$ и $y \in \{0, 1\}^m$,

$$ \begin{ \begin{align} O(\ket{x}\otimes\ket{y}) =\ket{x}\otimes\ket{y \oplus f(x)}. \end{align} $$

Теперь $O = ^\dagger$ путем строительства и вы разрешили обе предыдущие проблемы.

Совет

Чтобы понять, что $O = O^{\dagger}$, учтите, что $O^2 =\mathbf{1}$, так как $a \oplus b \oplus b = a$ для всех $a, b \in{0, 1}$. В результате $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$.

Важно, что определение оракула таким образом для каждого базисного вычислительного состояния $\ket{x}\ket{y}$ также определяет, как $O$ ведет себя для любого другого состояния. Это поведение следует немедленно от того факта, что $O$, как и все квантовые операции, линейна в состоянии, на которое он действует. Рассмотрим операцию Hadamard, например, определяемую $H \ket{0}=\ket{+}$ и $H \ket{1}=\ket{-}$. Если вы хотите знать, как $H$ действует на $\ket{+}$, вы можете использовать тот факт, что $H$ является линейным.

$$ \begin{align}H\ket{+}& =\frac{1}{\sqrt{{2}} H(\ket{0} + \ket{{-}) {1}= (H\frac{1}{\sqrt{ + {2}} H\ket{0}) \ket{1}\\& =\frac{1}{\sqrt{2}} (\ket{+} + \ket{{-}) =\frac12 (\ket{{0} + \ket{{1} + \ket{{0} - \ket{{1}) =\ket{{0}. \end{align} $$

При определении oracle $O$ можно аналогично использовать любое состояние $\ket{\psi}$ на $n + m$ кубитах, которое можно записать как

$$ \begin{ \begin{align} \ket{\psi} & _x \0, 1\=^n, y \sum \{\in0, 1\{^m}\in(x, y) {x}}y.\alpha\ket{}\ket{} \end{align} $$

Здесь: $\alpha \{0, 1\}^n \times \{0, 1\}^m\to\mathbb{ C}$ представляет коэффициенты состояния$\ket{\psi}$. Таким образом,

$$ \begin{ \begin{align} O \ket{\psi}& = O \sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y}\\& =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) O \ket{x}\ket{y}\\& =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y \oplus f(x). \end{align} $$

Фазовые оракулы

Кроме того, можно закодировать $f$ в оракул $O$, применяя фазу, основанную на входных данных для $O$. Например, можно определить $O$ так, что $$\begin{\begin{align}O\ket{x}=(-1)^{f(x)}\ket{x}. \end{align} $$

Если фазовый оракул работает с регистром изначально в базисном вычислительном состоянии $\ket{x}$, то эта фаза является глобальной и поэтому ненаблюдаемой. Но такой оракул может быть мощным ресурсом, если применяется к суперпозиции или как управляемая операция. Например, рассмотрим фазовый оракул $O_f$ для функции с одним кубитом $f$. Затем O_f$$\begin{align}\ket{ + }& amp; = O_f (\ket{0} + \ket{{1}) / \sqrt{{2}\\& amp; = ((-1)^{f(0) + (-1)^\ket{0}f(1)}\ket{1}) / \sqrt{2}\\& amp; = (-1)^{f(0) (\ket{{0} + (-1)^{f(1) - f(0)}\ket{{1}) / \sqrt{{2}\\& amp; = (-1)^{f(0)} Z^{f(0) - f(1)}\ket{ +}. \end{align} $$

Примечание.

Обратите внимание, что $Z^{-1}=Z^{\dagger}=Z$, следовательно $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$

В целом оба представления оракулов можно расширить для представления классических функций, которые возвращают реальные числа вместо одного бита.

Выбор лучшего способа реализации oracle сильно зависит от того, как этот оракул будет использоваться в рамках заданного алгоритма. Например, алгоритм Дойча — Йожи полагается на первую реализацию оракула, тогда как алгоритм Гровера использует вторую реализацию оракула.

Дополнительные сведения см. в обсуждении в Gilyén 1711.00465.

Связанный контент