HW5 - Problem 3

Problem 3: Deutsch-Jozsa Example

Let \(f\) be a function that takes 3 bits as inputs and outputs a single bit. The function takes the three bits it received, adds them all together, and outputs the answer mod 2. Given oracle access to this function, we construct the following circuit to run Deutsch-Jozsa.

  1. (Definition check) Is this function constant or balanced?
  2. (Particular instance) What is \(U_f \left|101\right>\left|-\right>\)? What about \(U_f \left|010\right>\left|-\right>\)?
  3. Now let’s analyze the full algorithm. Starting from \(\left|000\right>\left|-\right>\) as we have in the diagram, what is the state of the algorithm after the \(H\) gates? Use the \(n\)-qubit Hadamard identity.
  4. (Continue from 3) What is the state of the algorithm after the \(U_f\) gate is applied?
  5. (Continue from 4) What is the state of the algorithm after the second layer of \(H\) gates? Don’t use summation notation, and explicitly write out the coefficients.
  6. (Continue from 5) What are the possible measurement results and their corresponding probabilities?
  7. (Continue from 6) What do we conclude based on this outcome? Does this match what we predicted in the first part of the problem?