Poznámka
Přístup k této stránce vyžaduje autorizaci. Můžete se zkusit přihlásit nebo změnit adresáře.
Přístup k této stránce vyžaduje autorizaci. Můžete zkusit změnit adresáře.
Orákulum $, O$, je nevyexponovaná operace, která se používá jako vstup do jiného algoritmu. Tyto operace jsou často definovány pomocí klasické funkce $f: \{0, 1\}^n \to \{0, 1\}^m$, která přebírá $n-bit$ binární vstup a vytváří $binární výstup m-bit$. Chcete-li to provést, zvažte konkrétní binární vstup $x (x_=, x_{0}, \tečky, x_{1}n-1{)}$. Stavy qubitů můžete označovat jako $\ket{\vec{x}}=\ket{x_{{0}}\otimes\ket{x_{1}}\otimes\cdots\otimes\ket{x_{n-1.}}$
Můžete se nejprve pokusit definovat $O$ tak, aby $O\ket{x}=\ket{f(x)}$, ale tato metoda má několik problémů. Za prvé, $f$ může mít jinou velikost vstupu a výstupu ($n \ne m$), aby použití $O$ změnilo počet qubitů v registru. Za druhé, i když $n = m$, nemusí být funkce invertovatelná: pokud $f(x) = f(y)$ pro některé $x \ne y$, pak $O\ket{x}= O\ket{y}$, ale $O^\dagger O\ket{x}\ne O^\dagger O\ket{y.}$ To znamená, že nelze vytvořit sdruženou operaci $O^\dagger$ a že orákula musí mít definované sdružené operace.
Definujte orákulum podle jeho účinku na výpočetní základní stavy
Oba tyto problémy můžete vyřešit zavedením druhého registru $qubitů m$ pro uložení odpovědi. Potom definujte účinek orákula na všechny výpočetní báze: pro všechny $x \in \{0, 1\}^n$ a $y \in \{0, 1\}^m$,
$$ \begin{ \begin{align}O(\ket{x}\otimes\ket{y})=\ket{ x}\otimes\ket{y \oplus f(x).} \end{align} $$
Nyní $O = O^\dagger$ díky konstrukci jste vyřešili oba předchozí problémy.
Tip
Pokud chcete vidět, že $O= O^{\dagger}$, všimněte si, že $O^2 =\mathbf{1}$ protože $a \oplus b \oplus b = a$ pro všechny $a, b\in{ 0, 1}$. Výsledkem je, že $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y.}$
Důležité je, že definování orákula tímto způsobem pro každý výpočet základní stav $\ket{x}\ket{y}$ také definuje, jak $O$ funguje pro jakýkoli jiný stav. Toto chování bezprostředně následuje od skutečnosti, že $O$, podobně jako všechny kvantové operace, je lineární ve stavu, na který působí. Představte si například operaci Hadamard, která je definována $H \ket{0}=\ket{+}$ a $H \ket{1}=\ket{-}$. Pokud chcete vědět, jak $H$ působí na $\ket{+}$, můžete použít, že $H$ je lineární,
$$ \begin{align}H\ket{+}& =\frac{1}{\sqrt{{2}} H(\ket{0} + \ket{{1}) =\frac{1}{\sqrt{{2}}(H\ket{0} + H\ket{1}) \\& =\frac{1}{\sqrt{2}} (\ket{+} + \ket{{-}) =\frac12 (\ket{{0} + \ket{{1} + \ket{{0} - \ket{{1}) =\ket{{0} \end{align} $$
Při definování orákula $O$ můžete podobně použít to, že jakýkoli stav na $n + m$ qubitů lze zapsat 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} $$
Zde: $\alpha \{0, 1\}^n \times \{0, 1\}^m\to\mathbb{ C}$ představuje koeficienty stavu $\ket{\psi}$. Tedy,
$$ \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} $$
Orákula fází
Alternativně můžete zakódovat $f$ do orákula $O$ použitím fáze na základě vstupu do $O$. Můžete například definovat $O$ tak, aby$$\begin{\begin{align}O \ket{x}= (-1)^{f(x)}\ket{x.} \end{align} $$
Pokud fázové orákulum působí na registr zpočátku ve stavu $\ket{x}$ ve výpočetním základu, pak tato fáze je globální, a proto není pozorovatelná. Taková věštba však může být mocným prostředkem, pokud se použije na superpozici nebo jako řízená operace. Například si představte fázové orákulum $O_f$ pro funkci s jedním qubitem $f$. Pak$$\begin{align} O_f \ket{+}& = O_f (\ket{0} + \ket{{1}) / \sqrt{{2}\\& = ((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}) / \sqrt{2}\\& = (-1)^{f(0)} (\ket{{0} + (-1)^{f(1) - f(0)}\ket{{1}) / \sqrt{{2}\\& = (-1)^{f(0)} Z^{f(0) - f(1)}\ket{+}. \end{align} $$
Poznámka:
Všimněte si, že $Z^{-1}=Z^{\dagger}=Z$, a proto $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$
Obecněji platí, že obě zobrazení orákulumů lze rozšířit tak, aby představovala klasické funkce, které vracejí reálná čísla místo jen jednoho bitu.
Volba nejlepšího způsobu implementace orákula silně závisí na tom, jak se má toto orákulum používat v daném algoritmu. Například Deutsch-Jozsa algoritmus spoléhá na orákulum implementovaný prvním způsobem, zatímco Groverův algoritmus spoléhá na orákulum implementovaný druhým způsobem.
Další informace najdete v diskuzi v Gilyénu 1711.00465.