HW5 - Problem 4

Problem 4: Simon’s Algorithm Example

The function \(f : \{0, 1\}^3 \rightarrow \{0, 1\}^3\) is defined as follows:

\(f(000) = 110 \;\;\;f(100) = 001\) \(f(001) = 001 \;\;\;f(101) = 110\) \(f(010) = 000 \;\;\;f(110) = 010\) \(f(011) = 010 \;\;\;f(111) = 000\)

  1. The inputs are paired so that for \(x \neq y\), \(f(x) = f(y)\) if and only if \(x = y \oplus s\) for some fixed \(s\). Can you figure out \(s\) by inspection?
  2. In this question, you will simulate Simon’s algorithm for the function \(f\). The unitary operator \(U_f\) maps \(\left|x\right>\left|000\right>\) to \(\left|x\right>\left|000\oplus f(x)\right>\), where \(x\) is a 3-bit string. The operator \(\oplus\) is bit-wise addition, mod 2. Write down the state of the algorithm after each step. Use the \(n\)-qubit Hadamard identity.
  • Start with \(\left|000\right>\left|000\right>\).
  • Apply \(H^{\otimes 3} \otimes I^{\otimes 3}\).
  • Apply \(U_f\).
  1. Based on your answer from the previous problem, what are the possible states we can see if we measure the last three qubits? What are the corresponding probabilities?
  2. Suppose you measured 110 in the previous step. What is the state of the algorithm?
  3. (Continue from 4) Apply \(H^{\otimes 3}\) on the first three qubits. What are the possible measurement outcomes? Use the \(n\)-qubit Hadamard identity.
  4. (Continue from 5) Verify that every string \(x\) that is a possible outcome of the last measurement satisfies \(x \cdot s = 0\) mod 2.