2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the future, use \rangle instead of > (and \langle instead of <). $\endgroup$ – Yuval Filmus Jul 12 '15 at 19:55
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – user6818 Jul 12 '15 at 21:37
  • $\begingroup$ no, but the sum should be over $i$ not over $x$. I edited the answer. $\endgroup$ – Ran G. Jul 12 '15 at 21:55
  • $\begingroup$ up to the missing (and very important) phases!!! $\endgroup$ – Ran G. Jul 12 '15 at 21:55
  • $\begingroup$ 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? $\endgroup$ – user6818 Jul 12 '15 at 21:59
  • $\begingroup$ 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. $\endgroup$ – Ran G. Jul 12 '15 at 22:04

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.