Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!


share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
Thanks a lot for this! :) However, what is it that you do when you apply the Hadamards to the first two bits? That part has me kind of confused.. – Linus Oct 25 '11 at 19:09
@Linus: I edited the answer in response to your comment. I was under the impression you knew how to apply the Hadamard transform since you'd correctly applied it to the initial state. – joriki Oct 26 '11 at 3:18
Thanks a lot! :) – Linus Oct 26 '11 at 9:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.