Question about the Simon's algorithm

Question

This comes from trying to understand the "Simon's algorithm".

So we have a set of 2ドル^n$ kets $|x_i \rangle$ one each for $i \in \{0,1\}^n$. Each $x_j \in \{0,1\}^n$. And we have the further constraint that $x_i = x_j$ iff $i = j + s \pmod{2} = j \oplus s$ (bitwise addition modulo 2ドル$) for a certain $s \in \{0,1\}^n$. (so every $|x_k\rangle$ is guaranteed to have a second copy)

Now one has this state given as $\psi_a = \frac{1}{\sqrt{2^n}}\sum_{i \in \{0,1\}^n} |i\rangle|x_i\rangle $ So this is a state of some 2 qubit system.

• Given this I want to understand why a measurement on the second qubit would necessarily collapse this to the state, $\psi_b = \frac{1}{\sqrt{2}} ( |j\rangle + |j \oplus s\rangle)|x_j\rangle$ for some $j \in \{0,1\}^n$?

---

• Is this measurement of the second qubit state trying to measure some observable/Hermitian operator whose eigenstates are precisely these $\psi_b$s? Then it would make some sense that the only things one sees are these $\psi_b$ states.

But this would still not clarify the weird probability addition that is happening here as shown below.

---

One notes that the state $\psi_b$ will be obtained with a probability of $(\bar{\psi_b} \psi_a)^2 = (\frac{ 2}{ \sqrt{2^{n+1} }})^2 = 1/2^{n-1}$. These $\psi_b$s obviously do not span the entire 2ドル^{2n}$ dimensional Hilbert space available to these two qubits. They are not a basis.

• But the probabilities don't add up rightly either $\sum_b ( \bar{\psi_b} \psi_a )^2 = 2$. Wonder is the interpretation of the fact that the probabilites over all these possibilities seem to add up to 2ドル$!

• Some explanations I found say that these states $\psi_b$ being the only possibilities is forced because of the fact that the second qubit is being measured in the "computational basis". This argument is not clear to me.

• Yuval Filmus: In the future, use \rangle instead of > (and \langle instead of <).

Answer 1

I'm not sure I get all your questions. I'll try to answer according to my interpretation of what you are asking, and you can clarify if I got you wrong.

• Given this I want to understand why a measurement on the second qubit would necessarily collapse this to the state, $\psi_b = \frac{1}{\sqrt{2}} ( |j\rangle + |j \oplus s\rangle)|x_j\rangle$ for some $j \in \{0,1\}^n$?

First, there is no second qubit, but a second system (of $n$ qubits). Next, consider $\psi_a,ドル and recall that for any $f(x_j)$ there are only two preimages $j$ and $j\oplus s,ドル then if you measure $f(x_j)$ at the second system, the first system must either be $j$ or $j\oplus s$.

• Is this measurement of the second qubit state trying to measure some observable/Hermitian operator whose eigenstates are precisely these $\psi_b$s? Then it would make some sense that the only things one sees are these $\psi_b$ states.

Kind of. However, you don't measure $\vert\psi_a\rangle$ directly. There is another hadamard gate which is missing there. I.e., you measure $$(H\otimes I) \left\vert\psi_a\right\rangle = \frac1{2^n}\sum_x\sum_i (-1)^{i\cdot x}\left\vert i\right\rangle\left\vert f(x)\right\rangle$$

Now if you re-arrange it properly, it should give \begin{align*} \frac1{2^n}\sum_{x\in\{0,1\}^n}\sum_i (-1)^{i\cdot x}\left\vert i\right\rangle\left\vert f(x)\right\rangle &= \frac1{2^n}\sum_{j\in XS}\sum_i (-1)^{i\cdot j}\left\vert i\right\rangle\left\vert f(j)\right\rangle + (-1)^{i\cdot (j\oplus s)}\left\vert f(j\oplus s)\right\rangle \\ &= \frac1{2^n}\sum_{j\in XS}\sum_i \left ((-1)^{i\cdot j}+(-1)^{i\cdot j}(-1)^{i\cdot s}\right)\left\vert i\right\rangle\left\vert f(j)\right\rangle \\ &= \frac1{2^n}\sum_{j\in XS}\sum_i (-1)^{i\cdot j}\left(1+(-1)^{i\cdot s}\right)\left\vert i\right\rangle\left\vert f(j)\right\rangle \end{align*} Where $XS\subseteq \{0,1\}^n$ is the largest subset such that if $j\in XS$ then $\forall j'\in XS, f(j)\ne f(j')$; so that the sum over $j$ is only over half the space and we don't count twice $x=j$ and $x=j\oplus s$. But note that $f(j)=f(j\oplus s)$ which we use in the second transition.

The above shows that for any $i$ for which $s\cdot i=1 \mod 2$ there is a destructive interference that cancels these terms, and you are left with only $i$'s for which $s\cdot i=0 \mod 2$. Thus, any $i$ you will measure (at the first system) must satisfy $s\cdot i=0 \mod 2$.

• user6818: Is there a $\vert x \rangle$ missing in your second equation? So are you basically saying that in that $(H \otimes I) \vert \psi_a \rangle \propto \sum_b \vert \psi_b \rangle$ ?
• Ran G.: no, but the sum should be over $i$ not over $x$. I edited the answer.
• Ran G.: up to the missing (and very important) phases!!!
• user6818: Why do you think the phases are important here? It seems to me that what Simon's algorithms is relying on is the fact that $\vert <\psi_b \vert H \otimes I \vert \psi_a \rangle \vert ^2 $ is the same for all $b$ - right?
• Ran G.: I mis-read you. Note that $\vert \psi_a \rangle = \sum_j \vert \psi_b(j)>$. But then you perform hadmard, and then the phases get into play. They are very important since they cause (or rather, explain) the destructive interference.