Práce s kvantovými orákuly a jejich definování

  • Článek

Orákulum O $$je neexponovaná operace, která se používá jako vstup do jiného algoritmu. Tyto operace se často definují pomocí klasické funkce $f: \{0, 1\}^n \to \{0, 1\}^m$, která přijímá $nbitový$ binární vstup a vytváří $m-bit$ binární výstup. Pokud to chcete udělat, zvažte konkrétní binární vstup $x (x_{0}, x_{1}, \dots, x_{n-1}).$= Stavy qubitu můžete označit jako $\ket{\vec{x}}\ket{=x_\ket{\otimes{{0}}x_\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$), takže použití $O$ by 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 nebudete moct vytvořit operaci $adjoint O^\dagger$a orákula musí mít definovaný doplněk.

Definování orákulum jeho účinkem na výpočetní stavy

S oběma těmito problémy se můžete vypořádat zavedením druhého registru $m$ qubitů, který bude obsahovat odpověď. Potom definujte účinek orákulum na všechny výpočetní stavy: pro všechny $stavy x \in \{0, 1\}^n$ a $y \in \{0, 1\}^m$,

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

Nyní $O = ^\dagger$ konstrukce a 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}$ od $\oplus b \oplus b = a$ pro všechny $a, b{\in 0, 1}$.=$ Výsledkem je 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ákulum tímto způsobem pro každý výpočetní základní stav $\ket{x}\ket{y}$ také definuje, jak $O$ funguje pro jakýkoli jiný stav. Toto chování okamžitě vyplývá ze skutečnosti, že $O$, stejně jako všechny kvantové operace, je lineární ve stavu, na který působí. Představte si například hadamarda operaci, která je definována pomocí $H \ket{0}\ket{=+}$ a $H .\ket{1}=\ket{-}$ Pokud chcete vědět, jak $H$ funguje 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{{1} -{1}{0}\ket{\ket{) . =\ket{{0} \end{align} $$

Při definování orákulum $O$ můžete podobně použít, že libovolný stav $\ket{\psi}$ n $+ m$ qubitů lze zapsat jako

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

kde $\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\\&}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ákulum fází

Alternativně můžete f$ zakódovat $do orákulum $O$ použitím fáze založené na vstupu na $O$. O můžete například definovat $$ tak, že\begin{align}$$\begin{O \ket{x}= (-1)^{f(x)}\ket{x.} \end{align} $$

Pokud orákulum fází funguje na začátku registru ve výpočetním stavu $\ket{x}$, je tato fáze globální fází, a proto není pozorovatelná. Takové orákulum ale může být účinným prostředkem, pokud se použije na superpozici nebo jako řízenou operaci. Představte si například orákulum $fází O_f$ 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 tedy $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$$

Obecněji lze obě zobrazení orákula rozšířit tak, aby představovala klasické funkce, které vrací reálná čísla místo jediného bitu.

Volba nejlepšího způsobu implementace orákulum závisí do značné míry na tom, jak se toto orákulum v rámci daného algoritmu použije. Například Deutsch-Jozsův 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 článku Gilyén et al. 1711.00465.

Další kroky