2
$\begingroup$

The Simon's problem is as follows:

Suppose we are given a function $f : \{0, 1\}^n \to \{0, 1\}^m$, with $m \ge n$, and we are promised that either $f$ is 1-to-1, or there exists a non-trivial s such that $\forall x \ne x' (f(x) = f(x') \iff x' = x \oplus s$, where $\oplus$ denotes bitwise exclusive-or. We wish to determine which of these conditions holds for $f$, and, in the second case, to find s.

For this question, we consider a simpler version version where $n = m$.

The original algorithm proposed by Simon involves a quantum sub-routine. It is as follows.

Fourier-twice

Start with a 2n-qubit register.

  1. perform the transformation F described above on the first n-qubits, producing $2^{-\frac{n}{2}} \sum_x |x\rangle $.
  2. compute f(x), copy the answer into the second n-qubits, thus producing $2^{-\frac{n}{2}} \sum_x |(x,f(x))\rangle $. Measure last n-qubits.
  3. perform F on first n-qubits, producing $2^{-n} \sum_y \sum_x (-1)^{x.y}|(y, f(x)) \rangle $ Measure first n-qubits.

I am trying to implement Simon's algorithm for n = 3. The definition of the function is as follows:

$$\begin{matrix} x & f(x) \\ \hline 0 0 0 & \\ 0 0 1 & 0 0 0 \\ 0 1 0 & \\ \hline 0 1 1 & \\ 1 0 0 & 0 1 0 \\ 1 0 1 & \\ \hline 1 1 0 & \\ 1 1 1 & 1 1 1 \end{matrix}$$

In step one I take the Hadamard transformation of a three qubit register and concatenate a 3 ancila qubit register to it. Then the 6-qubit state becomes as follows.

$$\frac{1}{2\sqrt{2}}\left[|000111\rangle - |001111\rangle - |010111\rangle + |011111\rangle - |100111\rangle + |101111\rangle + |110111\rangle -|111111\rangle\right]$$

The vector form of the state is:

$$\left( \begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{2 \sqrt{2}} \\ \end{array} \right)$$

Now I evaluate the function on the first three qubits and store the result on the last three qubits. So, the state becomes:

$$\frac{1}{2\sqrt{2}}\left[|000000\rangle - |001000\rangle - |010000\rangle + |011010\rangle - |100010\rangle + |101010\rangle + |110111\rangle -|111111\rangle\right]$$

The vector form of the state is:

$$\left( \begin{array}{c} \frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2 \sqrt{2}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -\frac{1}{2 \sqrt{2}} \\ \end{array} \right)$$

Then I measure the last three qubits. Then the state of the first three qubits becomes, either $$\left( \begin{array}{c} \frac{1}{\sqrt{3}} \\ -\frac{1}{\sqrt{3}} \\ -\frac{1}{\sqrt{3}} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array} \right)$$ with probability $\frac{3}{8}$

or $$\left( \begin{array}{c} 0 \\ 0 \\ 0 \\ \frac{1}{\sqrt{3}} \\ -\frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{3}} \\ 0 \\ 0 \\ \end{array} \right)$$ with probability $\frac{3}{8}$

or $$\left( \begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \\ \end{array} \right)$$ with probability $\frac{1}{4}$.

As a last step of the algorithm I run Hadamard transformation on these three possible states. I get the following respectively.

$$\left( \begin{array}{c} -\frac{1}{2 \sqrt{6}} \\ \frac{1}{2 \sqrt{6}} \\ \frac{1}{2 \sqrt{6}} \\ \frac{\sqrt{\frac{3}{2}}}{2} \\ -\frac{1}{2 \sqrt{6}} \\ \frac{1}{2 \sqrt{6}} \\ \frac{1}{2 \sqrt{6}} \\ \frac{\sqrt{\frac{3}{2}}}{2} \\ \end{array} \right)$$

,

$$\left( \begin{array}{c} \frac{1}{2 \sqrt{6}} \\ -\frac{\sqrt{\frac{3}{2}}}{2} \\ -\frac{1}{2 \sqrt{6}} \\ -\frac{1}{2 \sqrt{6}} \\ \frac{1}{2 \sqrt{6}} \\ \frac{1}{2 \sqrt{6}} \\ -\frac{1}{2 \sqrt{6}} \\ \frac{\sqrt{\frac{3}{2}}}{2} \\ \end{array} \right)$$

and

$$\left( \begin{array}{c} 0 \\ \frac{1}{2} \\ 0 \\ -\frac{1}{2} \\ 0 \\ -\frac{1}{2} \\ 0 \\ \frac{1}{2} \\ \end{array} \right)$$.

I have to measure them now to get the values of y.

$\endgroup$
  • $\begingroup$ I calculated the result of the first measurement (on the last three qubits) wrong. Just fixed. $\endgroup$ – Omar Shehab Aug 20 '13 at 23:02
2
$\begingroup$

If s is 000, then the function is a bijection. Otherwise, the function is two-to-one. This is the given condition in Simon's problem.

The function you give does not satisfy this condition.

$\endgroup$
  • $\begingroup$ I understand that I am getting inconsistent result. But I failed to find out my error. Could you please help? $\endgroup$ – Omar Shehab Aug 19 '13 at 19:16
  • 1
    $\begingroup$ The problem you give is not an example of Simon's problem. Hence, using Simon's algorithm is not going to get you anywhere. $\endgroup$ – hollow7 Aug 20 '13 at 10:17
  • $\begingroup$ I am a little bit confused here. For reference I have added the definition of Simon's problem at the beginning. I failed to see why my problem is not a Simon's problem. $\endgroup$ – Omar Shehab Aug 20 '13 at 15:33
  • 1
    $\begingroup$ In your given function, f(000) = f(001) = f(010), am I right? Hence, f(000 XOR s) = f(s) implies s = 001 = 010, which is a contradiction. Notice that for nontrivial s, the function must be a two-to-one function. $\endgroup$ – hollow7 Aug 22 '13 at 6:32
  • 1
    $\begingroup$ If s is non-trivial, then for any given x, we can form exactly one x' distinct from x through the (XOR s) operation. If we do the operation on x' again, we're just going to get back x. Therefore, for every pair of x and x', f maps each of them to only one element, namely f(x) = f(x') $\endgroup$ – hollow7 Aug 27 '13 at 16:45

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.