# Why does Grover's algorithm rotate around $|000…0\rangle$?

In general I understand Grover's algorithm, how we can think of two separated state spaces, a space $$|\alpha\rangle$$ with no solutions and a space $$|\beta\rangle$$ with only solutions, and how the Grover operator rotates the state $$|\psi\rangle$$ into the solution space $$|\beta\rangle$$.

• In the implementation of grover, we use $$|000...0\rangle$$ as the state to reflect about. The math and how the inversion around the mean operator is constructed, this appears to be an easy and elegant way. The math adds up. I'm not clear how to justify the use of this particular state. Can't we use others as axes, and if not, why not?
• every post should contain a single, laser-focused question. Feel free to edit this question to make it more focused, possibly breaking it down into multiple posts – glS Feb 2 at 10:31
• regarding the second question, this post might be related: quantumcomputing.stackexchange.com/a/5256/55. You can do the math using any reference state, the only difference is that it might not be efficient/easy to find a good decomposition for the oracle in the general case. Regarding the first one: summing amplitudes in which basis? E.g. $|10\cdots 0\rangle$ is orthogonal to $|0\cdots 0\rangle$ but its amplitudes in the computational basis are trivially $(1,0,\cdots 0)$, which certainly don't sum up to $1$. More generally, the "sum of amplitudes" is a basis-dependent quantity – glS Feb 2 at 10:35
• Thanks for the comment. I'll sharpen the question and remove the first part. – rhundt Feb 3 at 6:07

## 2 Answers

DaftWullie's answer makes a lot of sense, and just wanted to add a little bit.

First a bit of context: We start by defining $$U|00...0\rangle = |\psi\rangle$$. In the Grover operator you have two reflections - the first reflection is around $$|\alpha\rangle$$ followed by the second reflection (as already stated by DaftWullie) around $$|\psi\rangle$$ (and not $$|00...0\rangle$$).

However it is usually not possible to directly reflect across $$|\psi\rangle$$. On the other hand in most cases we have access to the operator $$U$$ (and $$U^{\dagger}$$). So what is usually done is to rotate to a reference frame where we make the state $$|\psi\rangle \rightarrow |00...0\rangle$$ and to do that we can apply $$U^{\dagger}$$ to the current state. Then you can reflect across $$|00...0\rangle$$ and revert the reference frame back i.e. $$|00...0\rangle \rightarrow |\psi\rangle$$ by applying the $$U$$ operator.

So rotating around $$|00...0\rangle$$ is actually an artifact of not being able to rotate directly around $$|\psi\rangle$$... but it's usually the best we have!

In practice, you're not really rotating about $$|00\ldots 0\rangle$$. Really, you're rotating around $$U|00\ldots 0\rangle$$ which is some superposition of $$|\alpha\rangle$$ and $$|\beta\rangle$$. If you have another method that prepares such a superposition by acting $$V$$ on some state $$|\Psi\rangle$$, that's perfectly fine too.

That said, in a standard search, you don't know what it is you're search for, so you have to allow for it to be any possibility, and hence $$V|\Psi\rangle=\frac{1}{\sqrt{2^n}}\sum_x|x\rangle$$ makes a lot of sense, and the most natural way to implement this is $$(H|0\rangle)^{\otimes n}$$.