Usare e definire oracoli quantistici

  • Articolo

Un oracle, $O$, è un'operazione non esposta utilizzata come input a un altro algoritmo. Spesso, tali operazioni vengono definite usando una funzione $classica f : \0, 1\^n \to \{{0, 1\}}^m$, che accetta un input binario n$ bit e produce un $$output binario m-bit.$ A tale scopo, prendere in considerazione un particolare input binario $x = (x_{0}, x_{1}, \dots, x_{n-1})$. È possibile etichettare gli stati qubit come $\ket{\vec{x=}}\ket{x_{\otimes{0}}\ket{x_x_\otimes{1}}\otimes\ket{\cdots{n-1.}}$

È possibile provare a definire $O$ in modo che $O\ket{x}=\ket{f(x)}$, ma questo metodo presenta alcuni problemi. In primo luogo, $f$ può avere dimensioni diverse di input e output ($n \ne m$), per cui l'applicazione di $O$ modificherebbe il numero di qubit nel registro. In secondo luogo, anche se $n = m$, la funzione potrebbe non essere invertibile: se $f(x) = f(y)$ per alcuni $x \ne y$, allora $O\ket{x}= O\ket{y}$ ma $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$. Ciò significa che non sarà possibile costruire l'operazione $adiacente O^\dagger$e gli oracle devono avere un oggetto adiacente definito per loro.

Definire un oracolo in base al relativo effetto sugli stati di base computazionale

È possibile gestire entrambi questi problemi introducendo un secondo registro di $qubit$ m per contenere la risposta. Definire quindi l'effetto dell'oracle su tutti gli stati di calcolo: per tutti i x \\in0, 1\}^n$ e $y \in \{{0, 1\}^m$,$

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

Ora $O^ =\dagger$ per costruzione e hai risolto entrambi i problemi precedenti.

Suggerimento

Per vedere che $O = O^{\dagger}$, si noti che $O^2 =\mathbf{1}$ giacché $a \oplus b \oplus b = a$ per ogni $a, b \in{0, 1}$. Di conseguenza, $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$.

È importante notare che la definizione di un oracolo in questo modo per ogni stato di base computazionale $\ket{x}\ket{y}$ definisce anche il modo in cui $O$ agisce per qualsiasi altro stato. Questo comportamento segue immediatamente dal fatto che $O$, come tutte le operazioni quantistice, è lineare nello stato in cui agisce. Si consideri l'operazione Hadamard, ad esempio, definita da $H +}$ e $H \ket{1}\ket{0}\ket{-}$=\ket{=. Se si vuole sapere come $H$ agisce su $\ket{+}$, è possibile usare tale $H$ è lineare,

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

Quando si definisce oracle $O$, è possibile usare in modo analogo qualsiasi stato $\ket{\psi}$ in $n + m$ qubits come

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

dove $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ rappresenta i coefficienti dello stato $\ket{\psi}$. Pertanto

$$\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 \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y \in \oplus f(x)}. \end{align} $$

Oracoli di fase

In alternativa, è possibile codificare $f$ in un oracle $O$ applicando una fase in base all'input a $O$. Ad esempio, è possibile definire $O$ in modo che\begin{$$\begin{align} O \ket{x=} (-1)^{f(x)}\ket{x.} \end{align} $$

Se un oracolo di fase agisce inizialmente su un registro in uno stato di base computazionale $\ket{x}$, questa fase è una fase globale e quindi non osservabile. Ma tale oracle può essere una risorsa potente se applicata a una sovrapposizione o come operazione controllata. Si consideri, ad esempio, un oracolo di fase $O_f$ per una funzione a qubit singolo $f$. Quindi, $$\begin{align} 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)} (\ket{{0} + (-1)^f(1) - f(0{1}\ket{})) /&\sqrt{{2}\\ amp; = (-1)^{{f(0}) Z^{f(0) - f(1}\ket{)+.} \end{align} $$

Nota

Si noti che $Z^{-1}=Z^{\dagger}=Z$, pertanto $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$

Più in generale, entrambe le visualizzazioni degli oracle possono essere ampliate per rappresentare le funzioni classiche, che restituiscono numeri reali anziché un solo bit.

La scelta del modo migliore per implementare un oracle dipende fortemente dal modo in cui questo oracle deve essere usato all'interno di un determinato algoritmo. Ad esempio, l'algoritmo Deutsch-Jozsa si basa sull'oracolo implementato nel primo modo, mentre l'algoritmo di Grover si basa sull'oracolo implementato nel secondo modo.

Per altre informazioni, vedere la discussione in Gilyén et al. 1711.00465.

Passaggi successivi