How does the Grover diffusion operator work and why is it optimal?

Question

In this answer, Grover's algorithm is explained. The explanation indicates that the algorithm relies heavily on the Grover Diffusion Operator, but does not give details on the inner workings of this operator.

Briefly, the Grover Diffusion Operator creates an 'inversion about the mean' to iteratively make the tiny differences in earlier steps large enough to be measurable.

The questions are now:

1. How does the Grover diffusion operator achieve this?
2. Why is the resulting $O(\sqrt{n})$ in total time to search an unordered database optimal?

Answer 1

$\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|}$ Since the original question was about a layman's description, I offer a slightly different solution which is perhaps easier to understand (background dependent), based on a continuous time evolution. (I make no pretense that it is suitable for a layman, however.)

We start from an initial state which is a uniform superposition of all states, $$ \ket{\psi}=\frac{1}{\sqrt{2^n}}\sum_{y\in\{0,1\}^n}\ket{y} $$ and we are aiming to find a state $\ket{x}$ that can be recognised as the correct answer (assuming there is exactly one such state, although this can be generalised). To do this, we evolve in time under the action of a Hamiltonian $$ H=\proj{x}+\proj{\psi}. $$ The really beautiful feature of Grover's search is that at this point, we can reduce the maths to a subspace of just two states $\{\ket{x},\ket{\psi}\}$, rather than requiring all $2^n$. It's easier to describe if we make an orthonormal basis from these states, $\{\ket{x},\ket{\psi^\perp}\}$ where $$ \ket{\psi^{\perp}}=\frac{1}{\sqrt{2^n-1}}\sum_{y\in\{0,1\}^n:y\neq x}\ket{y}. $$ Using this basis, the time evolution $e^{-iHt}\ket{\psi}$ can be written as $$ 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), $$ where $X$ and $Z$ are the standard Pauli matrices. This can be rewritten as $$ 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). $$ So, if we evolve for a time $t=\frac{\pi}{2}2^{n/2}$, and ignoring global phases, the final state is $$ \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.

Answer 2

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}