Dela via

Förstå kvantorakel

  • Artikel

Ett orakel, $O$, är en oexponerad åtgärd som används som indata till en annan algoritm. Sådana åtgärder definieras ofta med en klassisk funktion $f : \{0, 1\}^n \to \{0, 1\}^m$, som tar en $n-bit$ binär indata och genererar en $m-bitars$ binär utdata. För att göra det bör du överväga ett visst binärt indata $x = (x_{0}, x_{1}, \dots, x_{n-1})$. Du kan märka qubittillstånd som $\ket{\vec{x}}\ket{=x_\ket{\otimes{{0}}x_\otimes{1}}\otimes\ket{\cdotsx_{n-1.}}$

Du kan först försöka definiera $O$ så att $O\ket{x=}\ket{f(x)}$, men den här metoden har ett par problem. $För det första kan f$ ha en annan storlek på indata och utdata ($n \ne m$), så att tillämpning $av O$ skulle ändra antalet kvantbitar i registret. För det andra, även om n m, kanske funktionen inte är inverterbar: om $f(x) f(y) =$ för vissa $x \ne y$, då $O\ket{x}= O\ket{y}$ men $O^\dagger O\ket{x}\ne O^\dagger O\ket{y.}$$=$ Det innebär att du inte kommer att kunna konstruera den angränsande åtgärden $O^\dagger$, och orakel måste ha en angränsande definierad för dem.

Definiera ett orakel med dess effekt på beräkningsbastillstånd

Du kan hantera båda dessa problem genom att införa ett andra register med $m$ qubits för att hålla svaret. Definiera sedan effekten av oraklet på alla beräkningsbastillstånd: för alla x \0, 1\}^n$ och $y \in \{0, 1\}^m$,{\in$

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

Nu $O = O^\dagger$ genom konstruktion och du har löst båda de tidigare problemen.

Dricks

Om du vill se O^, observera att $O^2\mathbf{1}$=sedan $en \oplus b \oplus b = a$ för alla $a, b{\in 0, 1}$.{\dagger}$=$ Det innebär att $O \ket{x}\ket{y \oplus f(x)\ket{}=x}\ket{y \oplus f(x) \oplus f(x)}\ket{=x}\ket{y.}$

Viktigt är att definiera ett orakel på det här sättet för varje beräkningsbastillstånd $\ket{x}\ket{y}$ definierar också hur $O$ agerar för andra tillstånd. Det här beteendet följer omedelbart från det faktum att $O$, liksom alla kvantåtgärder, är linjärt i det tillstånd som det agerar på. Överväg till exempel Hadamard-åtgärden som definieras av $H \ket{0}\ket{=+}$ och $H .\ket{1}=\ket{-}$ Om du vill veta hur $H$ fungerar på $\ket{+}$kan du använda att $H$ är linjärt,

$$\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{ +{1}\ket{+ \ket{{0} -{1}\ket{ ) . =\ket{{0} \end{align} $$

När du definierar oraklet $O$ kan du på samma sätt använda att alla tillstånd $\ket{\psi}$ på $n + m$ qubits kan skrivas som

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

där $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ representerar koefficienterna för tillståndet $\ket{\psi}$. Sålunda

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

Fasorakel

Du kan också koda $f$ till ett orakel $O$ genom att tillämpa en fas baserat på indata till $O$. Du kan till exempel definiera $O$ så att $$\begin{align}\begin{O \ket{x}= (-1)^{f(x)}\ket{x}. \end{align} $$

Om ett fasorakel agerar på ett register som ursprungligen är i beräkningsbastillstånd $\ket{x}$, är den här fasen en global fas och därmed inte observerbar. Men ett sådant orakel kan vara en kraftfull resurs om det tillämpas på en superposition eller som en kontrollerad åtgärd. Överväg till exempel ett fasorakel $O_f$ för en enkel qubit-funktion $f$. $$\begin{align} Sedan 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} $$

Kommentar

Observera att $Z^{-1}=Z^{\dagger}=Z$ och därför $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$

Mer allmänt kan båda vyerna av orakel breddas för att representera klassiska funktioner, som returnerar verkliga tal i stället för bara en enda bit.

Att välja det bästa sättet att implementera ett orakel beror mycket på hur det här oraklet ska användas inom en viss algoritm. Deutsch-Jozsa-algoritmen förlitar sig till exempel på oraklet som implementeras på det första sättet, medan Grover-algoritmen förlitar sig på oraklet som implementeras på det andra sättet.

Mer information finns i diskussionen i Gilyén et al. 1711.00465.

Relaterat innehåll