Exercise 2 (16 points): Quantum Phase Estimation The phase estimation algorithm is a building block of many other quantum algorithms. Consider a circuit that implements the single-qubit gate U, and a single-qubit state) which is an eigenstate of U. 1. (1 point) Prove you can write U)²) where is a real number between 0 and 1. 1 The phase estimation algorithm is a method to find when a circuit performing U and a qubit in state ) are given. Specifically, we will be performing the following circuit: Superposition Controlled U Operations Measurement 10) H 10) H 间 H QFT 10) Each of the top n qubits will end up containing a digit of the binary floating point decomposition of the real number 9. We can write 20-a+2º5, where a is the nearest integer to 2º0 and 6 is the "rounding error" in the n-bit representation of 6, i.e. [26] ≤ 4. We will assume 5-0 in this homework. Notice the need for controlled U gates, i.e. conditional on a control qubit, perform the gate U on a target qubit 1 times. We also need the Inverse Quantum Fourier Transform for which we know QFT-¹ – QFT↑ (because the QFT is unitary). 2. (1 points) Write down in terms of projectors and U matrices the two-qubit gate Ctrl(U) (the gate that controlled on the first qubit applies the gate U on the second qubit). 3. (3 points) Write down the gates Ctrl(U²) and (Ctrl(U))² and prove they are the same gate. The first gate stands for "conditional on the control qubit perform U² on the target qubit". The second gate stands for repeating twice the operation "conditional on the control qubit perform U on the target qubit/nEach of the top n qubits will end up containing a digit of the binary floating point decomposition of the real number 9. We can write 20-a+2", where a is the nearest integer to 20 and 6 is the "rounding error" in the n-bit representation of 6, i.e. [26] ≤ 4. We will assume 5-0 in this homework. Notice the need for controlled U gates, ie. conditional on a control qubit, perform the gate U on a target qubit 1 times. We also need the Inverse Quantum Fourier Transform for which we know QFT-¹ – QFT↑ (because the QFT is unitary). 2. (1 points) Write down in terms of projectors and U matrices the two-qubit gate Ctrl(U) (the gate that controlled on the first qubit applies the gate U on the second qubit). 3. (3 points) Write down the gates Ctrl(U²) and (Ctrl(U))² and prove they are the same gate. The first gate stands for "conditional on the control qubit perform U² on the target qubit". The second gate stands for repeating twice the operation "conditional on the control qubit perform U on the target qubit 4. (1 point) What is the state of the first n qubits immediately after the H gates? 5. (4 points) What is the state of all qubits just before the inverse QFT? Is the system that started in state) factorizable out or is it entangled with the rest of the qubits? 6. (4 points) What is the state of the top n qubits after the inverse QFT? Answer this question in the basis of bitstrings (ie. the Z basis). 7. (2 points) When we measure the top n qubits in the Z basis, what is the chance of observing the result to be the integer a expressed in binary? 2 Notice that finding the phase to n bits of precision required (2") applications of controlled-U. In other wordsto achieve precision we need (1/c) controlled gates. As a very rough comparison to classical estimation, consider the following nearly equivalent problem: you have a coin that with probability p gives heads, otherwise gives tails; you will need (2) samples to get varience on the order of, Le. error on the order of estimation. Le bits of precision with a classical

Fig: 1

Fig: 2