CS 190/264: Quantum Computation Homework 8
Note: Undergraduates should do problems 1-5, and graduate students should do problems 3-6.
1. Suppose you are given black box access to a function f : {0, 1} 12 → {0, 1} via the usual unitary Uf . The number of distinct 12-bit strings x such that f(x) = 1 is 57. Suppose you use Grover’s Algorithm to find a specific 12-bit string x such that f(x) = 1.
(a) What is the optimal number of iterations of Grover’s Algorithm in this case?
(b) If you iterate Grover’s Algorithm for the optimal number of iterations, then what is the probability that the string you measure causes f to evaluate to 1?
2. Suppose that you use the approximate counting algorithm presented in class to estimate |{x | f(x) = 1}| for some function f : {0, 1} 20 → {0, 1}. The number of auxiliary bits m = 12. At the end of the algorithm you measure the string 000001111101. What is your best guess for |{x | f(x) = 1}|?
3. Suppose that you use the approximate counting algorithm presented in class to estimate M = |{x | f(x) = 1}| for some function f : {0, 1} n → {0, 1}. The number of auxiliary bits is m. Consider the idealized case in which sin(πφ) = p M/2 n and φ = j/2 m for some integer j. When the m bits are measured at the end of the quantum circuit, what are the possible outcomes and the probabilities of each outcome? You may need the fact that the eigenvectors of the matrix cos 2θ − sin 2θ sin 2θ cos 2θ . are |v1i = i 1 |v2i = −i 1 .
4. Give a quantum circuit that on input |000i outputs √ 1 2 (|010i − |101i). You should only require the typical gates used in class: H, X, Z, CNOT, Fredken (controlled swap).
5. Give a quantum circuit that computes I(1,2,3) − 2(|10ih10| ⊗ I(3)). I(1,2,3) is the identity operator on qubits 1, 2, and 3. I(3) is the identity operator on qubit 3. You should only require the typical gates used in class: H, X, Z, CNOT, Fredken (controlled swap). You can use auxiliary qubits if you need to but these should be initialized to |0i and reset back to |0i at the output of the circuit.
6. Prove that at the end of the phase estimation algorithm, with at least constant probability, the measured outcome is an integer j such that |j/2 m − φ| ≤ 2 −(m+1) .