Simon's algorithm for n = 3

Question

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.

Answer 1

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.