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?
  • 1
    $\begingroup$ Just a comment on the second question. There are works to show that the track of the state in Grover's algorithm follows exactly the geodesic connecting the initial state of the algorithm and the destination state. So it's optimal. $\endgroup$ – XXDD Oct 30 '18 at 7:12

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

| improve this answer | |
  • $\begingroup$ Do you still need the $e^{-it}$ term when you are rewriting the time evolution in terms of sin and cos? $\endgroup$ – Attila Kun Jul 13 at 4:13
  • 1
    $\begingroup$ @AttilaKun You don't need it because of equivalence of global phases. Although if you want lines to follow from each other in an absolute mathematical sense, you should have it there. $\endgroup$ – DaftWullie Jul 13 at 7:12
  • 1
    $\begingroup$ Question 1: You haven't lost anything. $\cos(t)I-i\sin(t)I=(\cos(t)-i\sin(t))I=e^{-it}I$. This is perhaps more obvious directly if you go to the Taylor expansion of $e^{-iIt}$. $\endgroup$ – DaftWullie Jul 14 at 6:55
  • 1
    $\begingroup$ Question 2: you're working under the wrong assumption. $|x\rangle$ and $|\psi\rangle$ are not orthogonal so you shouldn't be representing them as orthogonal vectors. What you want is $|x\rangle\equiv (1,0)^T$ and $|\psi\rangle\equiv(1/\sqrt{2^n},\sqrt{1-1/2^n})^T$. $\endgroup$ – DaftWullie Jul 14 at 6:57
  • 1
    $\begingroup$ That's why we give credit to the smart person who invented the algorithm. Grover in this case. $\endgroup$ – DaftWullie Jul 15 at 7:15

One way of defining the diffusion operator is1 $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 gives2 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.3

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.