Grover Algorithm Orthogonal vectors

180 Views Asked by At

I'm study the Grover algorithm. About this picture my lecture say that the expression $|s'\rangle$ in the computational basis is $$|s'\rangle = \dfrac{1}{\sqrt{N-1}}\sum_{x\neq w}|x\rangle \tag{$*$}.$$ Why this expression?

I trying using the diagonal state in the computational basis. For example if $N=3$

$$|D\rangle = \dfrac{1}{\sqrt{3}}(|0\rangle+|1\rangle+|2\rangle),$$

Let be $|s'\rangle = |2\rangle/\sqrt{3}$ and $|w\rangle = |1\rangle/\sqrt{3}$ then $$\dfrac{1}{\sqrt{3}}|2\rangle=|D\rangle - \dfrac{1}{\sqrt{3}}(|0\rangle+|1\rangle).$$ But it is not the same expression as $(*)$.

1

There are 1 best solutions below

3
On

First, a notational issue. The vector you call $|w\rangle$ "double u" is actually called "omega" i.e. $|\omega\rangle$ (backslash-omega is the $\rm\TeX$ command).

The vector $|s'\rangle$ is determined as the only (up to an arbitrary overall normalization including the phase) linear combination of $|\omega\rangle$ and $|s\rangle$ – note that you use the symbol $|D\rangle$ for $|s\rangle$ (the equal superposition of all basis vectors) – that is orthogonal to $|\omega\rangle$. We're talking about a 2-dimensional plane here and it's convenient to have an orthonormal basis in that plane; the basis vectors are $|s\rangle$ we started with and $|s'\rangle$ which we add.

Consider a general $$|s'\rangle = A|s\rangle + B |\omega\rangle $$ and demand $\langle \omega|s'\rangle = 0$. Because $\langle \omega|\omega\rangle = 1$ and $\langle \omega|s\rangle=1/\sqrt{N}$, we may see that $B=-A\sqrt{N}$. This gives us $$|s'\rangle = A( |s\rangle -\sqrt{N} |\omega\rangle ) $$ The subtraction of $\sqrt{N}|\omega\rangle$ simply removes the term $|\omega\rangle$ from the sum over the basis that defines $|s\rangle$. So we have a sum over $x\neq \omega$ and the basis vectors are multiplied by $A/\sqrt{N}$. $$ |s'\rangle =\frac{A}{\sqrt N} \sum_{x\neq \omega}|x\rangle$$

The factor $1/\sqrt{N-1}$ is simply added to make $|s'\rangle$ normalized to unity. Any phase could be added, too. We obtain this right factor in front of the $x\neq \omega$ basis vectors for $A=\sqrt{N/(N-1)}$. The coefficient $A$ of this magnitude erases the original $1/\sqrt{N}$ coefficient and replaces it with the new one, $1/\sqrt{N-1}$.