HW6 - Problem 1

Problem 1: Grover’s Algorithm Example

Suppose we have a function \(f_S\) associated with an array \(S\) with length \(n\). The function takes as input an \(n\) bit string \(x\), and adds up values \(S_i\) where \(x_i = 1\). In other ones, the input bit string tells us which indices to focus on, and then the function sums up the values in those indices.

In the examples below, we consider an instance where \(n = 4\) using the set \(S = [-2, 3, 4, 1]\).

  1. What is \(f_S(1, 0, 1, 0)\)?
  2. There is exactly one input where \(f_S(x) = 1\). Which string is it? Call this string \(a\).
  3. What is the overlap between \(\left|a\right>\) and \(\left|\psi\right> = H^{\otimes n}\left|0000\right>\)? What is the probability that we see \(\left|a\right>\)?
  4. Write down the state \(\left|e\right>\), which is what we get after we remove the \(\left|a\right>\) component from \(\left|\psi\right>\).
  5. Draw \(\left|\psi\right>\) in the \(\left|e\right>\) (x-axis), \(\left|a\right>\) (y-axis) plane. What is the angle between \(\left|e\right>\) and \(\left|\psi\right>\)?
  6. Design the 5-qubit circuit that reflects an input state \(\left|v\right>\) over the vector \(\left|e\right>\).
  7. Design the 5-qubit circuit that reflects an input state \(\left|v\right>\) over the vector \(\left|\psi\right>\).
  8. Write down the resulting state after applying the circuits from problem 6 and then problem 7 on the state \(\left|\psi\right>\). What is the probability that we see \(\left|a\right>\) if we measure this state?