Grover algorithm geometric interpretation

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
2 replies · 2K views
Peter_Newman
Messages
155
Reaction score
11
Good day everybody,
I'm currently working on the Grover algorithm. You can also illustrate this process geometrically and that's exactly what I have a question for.

In my literary literature one obtains a uniform superposition by applying the Hadamard transformation to N-qubits. So far that's clear to me, that may look like this:

$$|\psi\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$

In order to imagine the geometrically better one can divide then this vector and exactly that I have a question. So the superposition contains a solution (or solutions) and not solutions, that can be represented as a sum in the form:

$$|\psi\rangle=\frac{1}{\sqrt{N}}\left(\sum_{x \in L}^{'}|x\rangle + \sum_{x \notin L}^{''}|x\rangle\right)$$

Sum over ' means solutions and '' means no solutions

But now in the literature this form came here:

$$|\alpha\rangle \equiv \frac{1}{\sqrt{N-M}}\sum_{x}^{''}|x\rangle$$

$$|\beta\rangle \equiv \frac{1}{\sqrt{M}}\sum_{x}^{'}|x\rangle$$

Why are these states defined, how does one get to this equation?

Then it goes on:
In the book its called "simple algebra shows that the initial state ##|\psi\rangle## may be represented as:"

$$|\psi\rangle=\sqrt{\frac{N-M}{N}}|\alpha\rangle + \sqrt{\frac{M}{N}}|\beta\rangle$$

My question is, how do you get there? I can not quite understand that.

If anyone knows how to get this shape, it would be really nice if someone could help me a bit.
I hope that my question is right here.
 
Last edited:
on Phys.org
##|\alpha \rangle## and ##|\beta \rangle## appear to simply be normalised superpositions, with the sum ##'## running over ##M## terms and the sum ##''## over ##N-M## terms. The rest is simple algebra.
 
Ok, I think I have it now. You would actually believe that the remaining elements are defined as follows:

$$
|\psi\rangle=\frac{1}{\sqrt{N}}\left(M\sum_{x \in L}^{'}|x\rangle + (N-M)\sum_{x \notin L}^{''}|x\rangle\right)
$$

But if you do that, then you ignore the standardization. To normalize this again, you need the root. I think i got it now.