2
$\begingroup$

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?
$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$
    – glS
    Feb 2 at 10:31
  • $\begingroup$ 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 $\endgroup$
    – glS
    Feb 2 at 10:35
  • $\begingroup$ Thanks for the comment. I'll sharpen the question and remove the first part. $\endgroup$
    – rhundt
    Feb 3 at 6:07
  • $\begingroup$ The initial state is $| 0 \rangle^{\otimes n}$ because in quantum computing, we want to begin from a reference, easy to prepare, quantum state and then perform all computation (this also allows us to informally compare resource requirements for each protocol). The "actual" initial state in the Grover search is $\frac{1}{\sqrt{N}} \sum\limits_{j=0}^{N-1} | j \rangle$, which simply represents each outcome $| j \rangle$ being equally likely (since this is an unstructured search). $\endgroup$ Jun 30 at 10:11
2
$\begingroup$

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 reflecting about $|00...0\rangle$ is actually an artifact of not being able to reflect directly about $|\psi\rangle$... but it's usually the best we have!

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.