Let $\vert s\rangle = \frac{1}{\sqrt{N}}\sum_{i=1}^N\vert x_i\rangle$ be an equal superposition over states from which we need to find one solution state $\vert w\rangle$.

The phase flip operator in Grover's search is $I - 2\vert w\rangle\langle w\vert$. Next, one inverts about the mean with the operator $2\vert s\rangle\langle s\vert - I$. We do this, say $\sqrt{N}$ times and then measure the state.

My question is why flip about the mean? What other options would one have that is still unitary and why are they less optimal than choosing the mean?


It doesn't have to be an inversion about the mean.

Let $R$ be the "reflect-a-vector operator", meaning

$$R(v) = I - 2 |v\rangle \langle v|$$

Grover's algorithm works by starting in some state $|d\rangle$ and then alternating two reflection operations, $R(s)$ and $R(d)$, where $s$ is the solution vector and $d$ is a "diffusion vector". The choice of $d$ affects the speed of the algorithm. Basically, the more $d$ aligns with $s$ (the closer they are to parallel), the faster you will go. The problem is that you don't know what $s$ is, so you need to pick a $d$ that works okay for any possible $s$.

The simplest $d$ that works equally well for every possible $s$, and the $d$ that Grover happened to use, is the normalized sum of each possible $s$. That is to say, you set $d= \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} |k\rangle = |+\rangle^{\otimes \lg N}$. This $d$ is the average of all the solutions, so it inverts about the average.

Another perfectly acceptable choice of $d$ is $d = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} (-1)^{\text{HammingWeight}(k)} |k\rangle = |-\rangle^{\otimes \lg N}$. For example, this is the state used in Quirk's example Grover circuit. Yet another perfectly acceptable choice of $d$ is the Fourier transform of any $|k\rangle$, e.g. $d = \text{QFT} \cdot |1\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{i k / N} |k\rangle$.

More generally, any $d$ that can be written in the form $\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{i \theta_k}|k\rangle$ will work. As long as $|\langle d|k \rangle|^2 = 1/N$ for all $k$, you're good to go ... except that not all choices have a nice compact circuit. For that reason, you should stick to values of $\theta_k$ that factor across the qubits, i.e. states that can be factorized into the form $\otimes_{q=0}^{\lg N - 1} Z^{\phi_q}|+\rangle$.

  • $\begingroup$ Thank you for answering - I sort of follow but could you clarify by adding a simple example to your answer? For ease of proof even if it's unrealistic, assume we know we are looking for the state |0> out of some equal superposition of |0>, |1>, |2>, |3>... |N>. In this case, what would you invert about since you know the state you want and you don't care that the solution has to work well for "any possible |s>"? If I understand you correctly, you need fewer iterations than $\sqrt{N}$ but it's not obvious to me how. $\endgroup$ – user1936752 Oct 15 '18 at 10:52
  • $\begingroup$ @user1936752 You just invert about |d> for whatever d you picked. Grover picked a d corresponding to the mean. The best values of d take O(sqrt(N)) iterations. $\endgroup$ – Craig Gidney Oct 16 '18 at 19:31
  • $\begingroup$ interesting perspective. Essentially, one wants to invert about any element of a basis that is mutually unbiased with respect to the computational one, but not necessarily all of these reflections can be performed efficiently. Do you know of places where the reflection about the "Hamming base" is used, or did you just pick it as something that came to mind? $\endgroup$ – glS Oct 18 '18 at 11:43
  • $\begingroup$ @gIS I'm not aware of anyone else using it. It just seemed like the compact choice to me, given that the -1 eigenvector of the X gate is $|-\rangle$ and it would be weird if exactly one of the qubits conditioned on $|-\rangle$ while the others conditioned on $|+\rangle$. $\endgroup$ – Craig Gidney Oct 18 '18 at 18:04

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.