Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 190/264: Quantum Computation Homework 7
Note: Undergraduates should do problems 1-4, and graduate students should do problems 2-5.
1. The function f : {0, 1} n → {0, 1} is defined as f(x) = 0 for every x 6= a, and f(a) = 1, for some n-bit string a. Express the state of the system after five steps of Grover search using the oracle Of .
2. Define |Ψi = H⊗n P |0 · · · 0i. Show that the operations 2|ΨihΨ| − I applied to a general state x αx|xi produces X x [−αx + 2hαi] |xi, where hαi = P x αx/2 n For this reason the operation 2|ΨihΨ| − I is sometimes called inversion about the mean.
3. Give a circuit which will compute (2|0 · · · 0ih0 · · · 0|−I) on n-qubits. 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.
4. Describe what happens in Grover’s algorithm if the function Uf is used where f is the all 0’s function. That is, f(x) = 0 for every n-bit string x.
5. Suppose that a boolean function f : {0, 1} n → {0, 1} has M solutions. That is, the number of x such that f(x) = 1 is M. Prove that any quantum circuit which has the usual black-box access to f requires Ω(p N/M) queries to f in the worst case to find an a such that f(a) = 1 with at least constant probability. 1