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!



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


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


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\pmatrix{1\\1\\0\\0}=\pmatrix{1\\0\\1\\0}\;,\quad H_2\pmatrix{0\\0\\1\\1}=\pmatrix{1\\0\\-1\\0}$$


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.