Udostępnij za pośrednictwem

Omówienie wyroczni kwantowych

Wyrocznia, $O$, jest nieeksponowaną operacją używaną jako dane wejściowe do innego algorytmu. Często takie operacje są definiowane przy użyciu klasycznej funkcji $f : \{0, 1\}^n \to \{0, 1\}^m$, która przyjmuje $n-bitowe$ dane wejściowe binarne i generuje $dane wyjściowe binarne m-bitowe$. W tym celu należy rozważyć konkretne binarne dane wejściowe $x = (x_{0}, x_{1}, \ldots, x_{n-1})$. Stany kubitów można oznaczyć jako $\ket{\vec{x}}=\ket{x_{{0}}\otimes\ket{x_{1}}\otimes\cdots\otimes\ket{x_{n-1}}$.

Możesz najpierw spróbować zdefiniować $O$ , aby $O\ket{x}=\ket{f(x)}$, ale ta metoda ma kilka problemów. Po pierwsze, $f$ może mieć inny rozmiar danych wejściowych i wyjściowych ($n \ne m$), tak aby zastosowanie $systemu O$ zmieniło liczbę kubitów w rejestrze. Po drugie, nawet jeśli $n = m$, funkcja może nie być odwracalna: jeśli $f(x) = f(y)$ dla niektórych $x \ne y$, to $O\ket{x}= O\ket{y}$ ale $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$. Oznacza to, że nie można skonstruować operacji sprzężonej $O^\dagger$, a wyrocznie muszą mieć zdefiniowane sprzężenie.

Definiowanie wyroczni przez jej wpływ na stany bazowe obliczeń

Oba te problemy można rozwiązać, wprowadzając drugi rejestr $kubitów m$ do przechowywania odpowiedzi. Następnie zdefiniuj wpływ wyroczni na wszystkie stany obliczeniowe: dla wszystkich $x \in \{0, 1\}^n$ i $y \in \{0, 1\}^m$,

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

$O = O^\dagger$ przez konstrukcję, rozwiązano oba wcześniejsze problemy. Teraz.

Napiwek

Aby zobaczyć, że $O = O^{\dagger}$, należy zauważyć, że $O^2 =\mathbf{1}$ ponieważ $a \oplus b \oplus b = a$ dla wszystkich $a, b\in = 0, 1{}$. W rezultacie $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$.

Co ważne, zdefiniowanie wyroczni w ten sposób dla każdego stanu $\ket{podstawy obliczeniowej x}\ket{y}$ definiuje również sposób $działania O$ dla dowolnego innego stanu. To zachowanie wynika bezpośrednio z faktu, że $O$, podobnie jak wszystkie operacje kwantowe, jest liniowy w stanie, na który działa. Rozważmy na przykład operację Hadamard, która jest zdefiniowana przez $H \ket{0}=\ket{+}$ i $H .\ket{1}=\ket{-}$ Jeśli chcesz wiedzieć, jak $H$ działa na $\ket{+}$, możesz skorzystać z tego, że $H$ jest liniowy.

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

Podczas definiowania wyroczni $O$ można również stosować, że dowolny stan $\ket{\psi}$ na $n + m$ kubitów można zapisać jako

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

Tutaj: $\alpha \{0, 1\}^n \times \{0, 1\}^m\to\mathbb{ C}$ reprezentuje współczynniki stanu $\ket{\psi}$. Tak więc,

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

Wyrocznie fazowe

Alternatywnie możesz zakodować $f$ w wyroczni $O$, stosując fazę opartą na danych wejściowych do $O$. Można na przykład zdefiniować $O$ tak, że $$\begin{\begin{align} O\ket{x}= (-1)^{f(x)}\ket{x}. \end{align} $$

Jeśli wyrocznia fazowa działa na rejestrze, który początkowo znajduje się w stanie obliczeniowym $\ket{ x }$, to ta faza jest globalna i dlatego nie jest zauważalna. Jednak taka wyrocznia może być potężnym zasobem, jeśli zostanie zastosowana do superpozycji lub jako operacja kontrolowana. Rozważmy na przykład wyrocznię fazową $O_f$ dla jedno-kubitowej funkcji $f$. $$ \begin{align} Następnie O_f \ket{+}& = O_f (\ket{0} +\ket{{1} ) /\sqrt{{2}\\& amp; = ((-1)^{f(0)}\ket{0} + (-1)^{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} $$

Uwaga

Należy pamiętać, że $Z^{-1}=Z^{\dagger}=Z$, a w związku z tym $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$

Ogólnie rzecz biorąc, oba podejścia do wyroczni można rozszerzyć tak, by reprezentowały funkcje klasyczne, które zwracają liczby rzeczywiste zamiast tylko jednego bitu.

Wybór najlepszego sposobu implementacji wyroczni zależy w dużym stopniu od tego, jak ta wyrocznia ma być używana w ramach danego algorytmu. Na przykład algorytm Deutsch-Jozsa opiera się na wyroczni zaimplementowanej w pierwszy sposób, podczas gdy algorytm Grovera opiera się na wyroczni zaimplementowanej w drugi sposób.

Aby uzyskać więcej informacji, zobacz dyskusję w Gilyén 1711.00465.

Powiązana zawartość