Wie funktioniert der Grover-Diffusionsoperator und warum ist er optimal?

In dieser Antwort wird der Algorithmus von Grover erklärt. Die Erklärung weist darauf hin, dass der Algorithmus stark vom Grover-Diffusionsoperator abhängt , jedoch keine Details zum Innenleben dieses Operators enthält.

Kurz gesagt, der Grover-Diffusionsoperator erzeugt eine 'Inversion über den Mittelwert', um iterativ die winzigen Unterschiede in früheren Schritten so groß zu machen, dass sie messbar sind.

Die Fragen sind jetzt:

1. Wie erreicht der Grover-Diffusionsoperator dies?
2. Warum ist das resultierende $O(\sqrt{n})$in der Gesamtzeit, um eine ungeordnete Datenbank optimal zu durchsuchen?

$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\braket}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}\newcommand{\proj}[1]{\left|#1\right>\left<#1\right|}$ Da es sich bei der ursprünglichen Frage um eine Laienbeschreibung handelte, biete ich eine etwas andere Lösung an, die auf der Grundlage einer kontinuierlichen zeitlichen Entwicklung möglicherweise leichter zu verstehen ist (abhängig vom Hintergrund). (Ich behaupte jedoch nicht, dass es für einen Laien geeignet ist.)

Wir gehen von einem Anfangszustand , die eine gleichmäßige Überlagerung aller Staaten ist, und wir streben einen Zustand finden| x⟩die als die richtige Antwort erkannt werden kann (vorausgesetztes ist genau ein solcher Zustand, obwohl dies verallgemeinert werden kann). Dazu entwickeln wir uns im Laufe der Zeit unter der Wirkung eines Hamiltonschen H=| x⟩⟨x| +| & psgr;⟩⟨& psgr;| . Das wirklich schöne Merkmal von Grovers Suche ist, dass wir zu diesem Zeitpunkt die Mathematik auf einen Unterraum von nur zwei Zuständen reduzieren können

$$\ket{\psi}=\frac{1}{\sqrt{2^n}}\sum_{y\in\{0,1\}^n}\ket{y}$$ $\ket{x}$ $$H=\proj{x}+\proj{\psi}.$$ , anstatt alle erfordern 2 n . Es ist einfacher zu beschreiben, ob wir aus diesen Zuständen eine orthonormale Basis bilden, { | x ⟩ , | & psgr; ⊥ ⟩ } wo | & psgr; ⊥ ⟩ = $\{\ket{x},\ket{\psi}\}$$2^n$$\{\ket{x},\ket{\psi^\perp}\}$ Auf dieser Basis kann die Zeitentwicklunge-iHt| & psgr;⟩kann geschrieben werden e-it(I+2-nZ+ $$\ket{\psi^{\perp}}=\frac{1}{\sqrt{2^n-1}}\sum_{y\in\{0,1\}^n:y\neq x}\ket{y}.$$ $e^{-iHt}\ket{\psi}$ wobeiXundZdie Standard-Pauli-Matrizen sind. Dies kann umgeschrieben werden als e-it(Icos( $$e^{-it\left(\mathbb{I}+2^{-n}Z+\frac{\sqrt{2^n-1}}{2^{n}}X\right)}\cdot\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right),$$ $X$$Z$ Wenn wir uns also für eine Zeit entwickeln, istt= $$e^{-it}\left(\mathbb{I}\cos\left(\frac{t}{2^{n/2}}\right)-i\frac{1}{2^{n/2}}\sin\left(\frac{t}{2^{n/2}}\right)\left(Z+X\sqrt{2^n-1}\right)\right)\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right).$$ $t=\frac{\pi}{2}2^{n/2}$ $$\frac{1}{2^{n/2}}\left(Z+X\sqrt{2^n-1}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right)=\left(\begin{array}{c}\frac{1}{2^n} \\ -\frac{\sqrt{2^n-1}}{2^n} \end{array}\right)+\left(\begin{array}{c} 1-\frac{1}{2^n} \\ \frac{\sqrt{2^n-1}}{2^n}\end{array}\right)=\left(\begin{array}{c} 1 \\ 0 \end{array}\right).$$ In other words, with probability 1, we get the state $\ket{x}$ that we were searching for. The usual circuit-based description of Grover's search is really just this continuous time evolution broken into discrete steps, with the slight disadvantage that you usually can't get exactly probability 1 for your outcome, just very close to it.

One caveat is the following: you could redefine $\tilde H=5H$, and evolve using $\tilde H$ and the evolution time would be 5 times shorter. If you wanted to be really radical, replace the 5 with $2^{n/2}$, and Grover's search runs in constant time! But you're not allowed to do this arbitrarily. Any given experiment would have a fixed maximum coupling strength (i.e. a fixed multiplier). So, different experiments have different running times, but their scaling is the same, $2^{n/2}$. It's just like saying that the gate cost in the circuit model is constant, rather than assuming that if we use a circuit of depth $k$ each gate can be made to run in time $1/k$.

The optimality proof essentially involves showing that if you made detection of one possible marked state $\ket{x}$ any quicker, it would make detection of a different marked state, $\ket{y}$, slower. Since the algorithm should work equally well whichever state is marked, this solution is the best one.

One way of defining the diffusion operator is¹ $D = -H^{\otimes n}U_0H^{\otimes n}$, where $U_0$ is the phase oracle

$$U_0\left|0^{\otimes n}\right> = -\left|0^{\otimes n}\right>,\,U_0\left|x\right> = \left|x\right>\,\text{for} \left|x\right>\neq\left|0^{\otimes n}\right>.$$

This shows that $U_0$ can also be written as $U_0 = I-2\left|0^{\otimes n}\rangle\langle0^{\otimes n}\right|$, giving

$$D= 2\left|+\rangle\langle+\right| - I,$$ where $\left|+\right> = 2^{-n/2}\left(\left|0\right> + \left|1\right>\right)^{\otimes n}$.

Writing a state $\left|\psi\right> = \alpha\left|+\right> + \beta\left|+^\perp\right>$ where $\left|+^\perp\right>$ is orthogonal to $\left|+\right>$ (i.e. $\left<+^\perp\mid+\right> =0)$ gives that $D\left|\psi\right> = \alpha\left|+\right> - \beta\left|+^\perp\right>$.

This gives² that the diffusion operator is a reflection about $\left|+\right>$

As the other part of Grover's algorithm is also a reflection, these combine to rotate the current state closer to the 'searched-for' value $x_0$. This angle decreases linearly with the number of rotations (until it overshoots the searched-for value), giving that the probability of correctly measuring the correct value increases quadratically.

Bennet et. al. showed that this is optimal. By taking a classical solution to an NP-problem, Grover's algorithm can be used to quadratically speed this up. However, taking a language $\mathcal L_A = \left\lbrace y:\exists x\, A\left(x\right) = y\right\rbrace$ for a length preserving function $A$ (here, an oracle), any bounded-error oracle based quantum turing machine cannot accept this language in a time $T\left(n\right)=\mathcal o\left(2^{n/2}\right)$.

This is achieved by taking a set of oracles where $\left|1\right>^{\otimes n}$ has no inverse (so is not contained in the language). However, this is contained in some new language $\mathcal L_{A_y}$ by definition. The difference in probabilities of a machine accepting $\mathcal L_A$ and a different machine accepting $\mathcal L_{A_y}$ in time $T\left(n\right)$ is then less than $1/3$ and so neither language is accepted and Grover's algorithm is indeed asymptotically optimal.³

Zalka later showed that Grover's algorithm is exactly optimal.

---

^{1 In Grover's algorithm, minus signs can be moved round, so where the minus sign is, is somewhat arbitrary and doesn't necessarily have to be in the definition of the diffusion operator}

^{2 alternatively, defining the diffusion operator without the minus sign gives a reflection about $\left|+^\perp\right>$}

^{3 Defining the machine using the oracle $A$ as $M^A$ and the machine using oracle $A_y$ as $M^{A_y}$, this is a due to the fact that there is a set $S$ of bit strings, where the states of $M^A$ and $M^{A_y}$ at a time $t$ are $\epsilon$-close4, with a cardinality $<2T^2/\epsilon^2$. Each oracle where $M^A$ correctly decides if $\left|1\right>^{\otimes n}$ is in $\mathcal L_A$ can be mapped to $2^n - \text{Card}\left(S\right)$ oracles where $M^A$ fails to correctly decide if $\left|1\right>^{\otimes n}$ is in that oracle's language. However, it must give one of the other $2^n-1$ potential answers and so if $T\left(n\right)=\mathcal o\left(2^{n/2}\right)$, the machine is unable to determine membership of $\mathcal L_A$.}

^{4 Using the Euclidean distance, twice the trace distance}