Problem 1: Combined QFT (40 points)
The goal of this problem is to construct a quantum circuit for the QFT on a larger Hilbert space using two QFTs on smaller spaces (and another operation). That is, for some compu-tational basis state |x in a pq-dimensional Hilbert space, we wish to take
1
pq−1
|x →
e2πixy/pq|y
√
pq
y=0
for relatively prime p and q using a QFT mod p and a QFT mod q.
(a) Show that the sets A := {p · 0 mod q, p · 1 mod q, . . . , p · (q − 1) mod q} and B := {0, 1, . . . , q − 1} are equal. That is, construct a bijection f : A → B. You must prove that f is indeed a 1–1 mapping. [Hint: Use the facts that p and q are relatively prime. This is in fact not true if they are not coprime; think of 2 and 4 as a counterexample.]
[Hint: You are being asked to show that the map x → p · x is injective, which means that p · x = p · y mod q is true if and only if x = y mod q. After you show this it is sufficient to check thatA and B have an equal number of elements.]
Given some 0 ≤ x < pq, we can decompose x into x = x1p + x2 where 0 ≤ x1 < q and
0 ≤ x2 < p. Similarly for 0 ≤ y < pq − 1 we can write y = y1q + y2 for 0 ≤ y2 < q and
0 ≤ y1 < p.
Now we can rewrite our computational basis state:
|x = |x1p + x2 = |x1 |x2
where x1 = x1p mod q.
(b) Fill in the blanks:
1
(i)
|x is an
-dimensional vector.
(ii)
|x1 is an
-dimensional vector.
(iii)
|x2 is an
-dimensional vector.
(c) Show that e2πixy/pq = e2πix1y2/qe2πix2y1/pe2πix2y2/pq.
1
q−1
2πix1y2
/q
(d) Consider the function Ua
x1
=
√q
y2=0 e
y2
. What is Ua?
|
1
p−1
2πix2y1
/p
|
(e) Consider the function Ub
x2
=
√p
y1=0 e
y1
. What is Ub?
|
|
Assume that we have a phase operator:
ϕpq |y2 |x2 = e2πix2y2/pq |y2 |x2
It will be useful to extend the above functions to the full pq-dimensional Hilbert space:
Ua := Ua ⊗ Ip, Ub := Iq ⊗ Ub
.
(f) Combine the above arguments and operators to construct U = QF Tpq:
1
pq−1
U|x =
e2πixy/pq|y
√
pq
y=0
You may need to re-index your summations when composing the operators.
Problem 2: Quantum phase estimation (20 points)
Consider U to be a unitary operator with eigenvector |ψ such that U |ψ = e2πiθ |ψ . This means:
U2j |ψ = U2j −1U |ψ = U2j −1e2πiθ |ψ = · · · = e2πi2j θ |ψ
As we showed in class, quantum phase estimation involves a circuit in which applying se-quentially n-controlled-unitary operations C − U2j , with 0 ≤ j ≤ n − 1, to the uniform superposition in a ‘counting’ register, gives;
|ψ2 = 2n/12 |0 + e2πiθ2n−1 |1 ⊗ . . . ⊗ |0 + e2πiθ21 |1 ⊗ |0 + e2πiθ20 |1 ⊗ |ψ
(a) Show that if k denotes the integer representation of n-bit binary numbers, this expres-sion can be simplified to
1
2n−1
|ψ2 =
e2πiθk |k ⊗ |ψ
2n/2
k=0
2
(b) If we inverse Fourier transform |ψ2 , we arrive at the state
2n−1 2n−1
|ψ3 = 21n e2πik(x−2nθ)/2n |x ⊗ |ψ
Explain why it is that by measuring x, we have a high likelihood of finding θ.
Problem 3: Quantum phase estimation qiskit circuit example (40 points) Fill out problem 3 on the attached Jupyter notebook.
3
