4
$\begingroup$

I'm trying to wrap my head around Simon's Algorithm (the quantum computing one), and all I can find on the internet is the formal defition: nobody actually ever does it with real input. However, I do need to be able to do this for my course, so I'd be very happy if someone could walk me through an example.

This is the input I've been given:

Let $F : \{0,1\}^2 \to \{0,1\}^2$ be defined as follows:

$f(00) = f(01) = 00$ $f(10) = f(11) = 01$

Apply Simon's algorithm to determine a linear dependency for the digits of $s = 01$. (Give a possible scenario).

Now I've gotten this far:

Start out with $|0^n0^n\rangle$ with $n = 2$. So, $|0000\rangle$.

Then, apply Hadamards to the first $n$ bits: $(1/\sqrt{4})(|0000\rangle + |0100\rangle + |1000\rangle + |1100\rangle)$

Then, apply $f$: $(1/\sqrt{4})(|0001\rangle + |0100\rangle + |1011\rangle + |1110\rangle)$

Now, I have to apply Hadamards to the first $n$ bits again, but I'm not quite sure how to continue...

If anyone could help me, I'd be really grateful!

Linus

1 Answers 1

5

You made a mistake in applying $f$. The definition $f(00)=f(01)=00$ doesn't mean that $00$ is mapped to $01$ and $01$ to $00$, but that both $00$ and $01$ are mapped to $00$. Thus, applying $f$ yields

$\def\ket#1#2#3#4{|#1#2#3#4\rangle}\frac1{\sqrt4}\left(\ket0000+\ket0100+\ket1001+\ket1101\right)\;.$

Then applying Hadamards to the first $n$ bits again yields

$\frac1{\sqrt4}\left(\ket0000+\ket1000+\ket0001-\ket1001\right)\;.$

Now measuring the first two bits results in one of the strings $00$ or $10$ with probability $1/2$ each, and each of these strings yields a constraint $00\cdot s=0$ or $10\cdot s=0$, respectively, as desired.

[Edit in response to the comment:]

To apply Hadamard transforms to the first two bits, I used this formula from page 3 of these lecture notes on Simon's algorithm:

$H^{\otimes n}|x\rangle=\frac1{\sqrt{2^n}}\sum_{y\in\{0,1\}^n}(-1)^{x\cdot y}|y\rangle\;.\tag1$

We can factor out common states for the last two bits:

$ \begin{eqnarray} \ket0000+\ket0100+\ket1001+\ket1101 &=& \def\k#1#2{|#1#2\rangle} \def\ke#1#2#3#4{\k#1#2\k#3#4} \ke0000+\ke0100+\ke1001+\ke1101 \\ &=& \left(\k00+\k01\right)\k00+\left(\k10+\k11\right)\k01\;. \end{eqnarray}$

Now if $|y\rangle$ has a $1$ in the second bit, the opposite signs in $(1)$ lead to cancellation and there is no contribution proportional to $|y\rangle$; whereas if $|y\rangle$ has a $0$ in the second bit, there's no cancellation and we get a contribution proportional to $|y\rangle$, with the sign determined by the product of the first bits of $x$ and $y$.

Alternatively, you can also write the states as column vectors with respect to the basis $\k00,\k01,\k10,\k11$ and apply the Hadamard matrix $H_2$ for two dimensions given in the Wikipedia article:

$H_2=\frac12\left(\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}\right)\;,$

$H_2\pmatrix{1\\1\\0\\0}=\pmatrix{1\\0\\1\\0}\;,\quad H_2\pmatrix{0\\0\\1\\1}=\pmatrix{1\\0\\-1\\0}$