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