Principy kvantových orákula
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_{0}, x_{1}, \tečky, x_{n-1})$=. Stavy qubitů můžete označovat jako $\ket{\vec{x=\ket{}}x_{0}}\ket{{\otimesx_\otimes{1}}\otimes\ket{\cdotsx_{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\dagger O\ket{x\ne} O\ket{y.}$$= $ To znamená, že nelze vytvořit operaci $adjoint O^\dagger$ a orákula musí mít pro ně definována adjoint.
Definujte orákulum jeho účinkem na výpočetní 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í stavy: pro všechny x \0, 1\}^n$ a $y \in \{0, 1\}^m$,{\in $
$$\begin{\begin{align}O(\ket{x}\ket{\otimesy})\ket{= x\otimes}\ket{y \oplus f(x).} \end{align} $$
Nyní $O = O^\dagger$ konstrukce a vy jste vyřešili oba předchozí problémy.
Tip
Pokud chcete zjistit, že O^, všimněte si, že $O^2 =\mathbf{1}$ od $\oplus b \oplus b a =$ pro všechny $a, b{\in 0, 1.}${\dagger}$= $ 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}) ={2}}\frac{1}{\sqrt{(H\ket{0} + H\ket{1}) \\& =\frac{1}{\sqrt{2}} (\ket{++ \ket{{-}} ) =\frac12 ({0}\ket{ + + \ket{\ket{{0}{1} -{1}\ket{ ) . =\ket{{0} \end{align} $$
Při definování orákula $O$ můžete podobně použít jakýkoli stav $\ket{\psi}$ na $n + m$ qubity, které lze zapsat jako
$$\begin{\begin{align}\ket{\psi}&zesilovač; =\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\mathbb{\to 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\\&}amp; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) O \ket{x}\ket{y\\&}amp; =\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 f zakódovat $$ do orákulum $O$ použitím fáze na základě vstupu do $O$. Můžete například definovat $O$ tak, aby\begin{align} $$\begin{O \ket{x}= (-1)^{f(x)}\ket{x.} \end{align} $$
Pokud orákulum fáze funguje na registru zpočátku ve stavu $\ket{výpočetního základu x}$, pak tato fáze je globální fáze, a proto není pozorovatelná. Takový orákulum ale může být výkonným prostředkem, pokud se použije na superpozici nebo jako řízenou operaci. Představte si například O_f fáze orákulum $pro funkci $s jedním qubitem f$.$ $$\begin{align} Pak O_f \ket{+}& = O_f (\ket{0} +{1}\ket{ ) /\\&\sqrt{{2} amp; = ((-1)^{f(0)}\ket{0} + (-1)^{f(1)\ket{1}}) /&\sqrt{2}\\ amp; = (-1)^{f(0)} ({0}\ket{ + (-1)^{f(1) - f(0){1}\ket{}) /\\{2}&\sqrt{ amp; = (-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ákulum závisí silně na tom, jak se má tento orákulum používat v rámci daného 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.