# Simon's algorithm for n = 3

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.

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

## 1 Answer

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.

• I understand that I am getting inconsistent result. But I failed to find out my error. Could you please help? – Omar Shehab Aug 19 '13 at 19:16
• The problem you give is not an example of Simon's problem. Hence, using Simon's algorithm is not going to get you anywhere. – hollow7 Aug 20 '13 at 10:17
• 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. – Omar Shehab Aug 20 '13 at 15:33
• 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. – hollow7 Aug 22 '13 at 6:32
• 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') – hollow7 Aug 27 '13 at 16:45