Quantum Computing Homework #11

Description

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.

1. 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 = x₁p + x₂ where 0 ≤ x₁ < q and

0 ≤ x₂ < p. Similarly for 0 ≤ y < pq − 1 we can write y = y₁q + y₂ for 0 ≤ y₂ < q and

0 ≤ y₁ < p.

Now we can rewrite our computational basis state:

|x = |x₁p + x₂ = |x₁ |x₂

where x₁ = x₁p mod q.

(b) Fill in the blanks:

(i)	|x is an			-dimensional vector.
(ii)	|x1 is an				-dimensional vector.
(iii)	|x2 is an				-dimensional vector.

3. _{Show that e}^2πixy/pq _{= e}^2πix1^y2^/q_e^2πix2^y1^/p_e^2πix2^y2^/pq_.

Assume that we have a phase operator:

ϕ_pq |y₂ |x₂ = e^2πix2y2/pq |y₂ |x₂

It will be useful to extend the above functions to the full pq-dimensional Hilbert space:

U_a := U_a ⊗ I_p, U_b := I_q ⊗ U_b

.

(f) Combine the above arguments and operators to construct U = QF T_pq:

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 |ψ = e^2πiθ |ψ . This means:

U^2j |ψ = U^{2j −1}U |ψ = U^{2j −1}e^2πiθ |ψ = · · · = e^{2πi2j θ} |ψ

As we showed in class, quantum phase estimation involves a circuit in which applying se-quentially n-controlled-unitary operations C − U^2j , with 0 ≤ j ≤ n − 1, to the uniform superposition in a ‘counting’ register, gives;

|ψ₂ = _2n/¹₂ |0 + e^2πiθ2n−1 |1 ⊗ . . . ⊗ |0 + e^2πiθ21 |1 ⊗ |0 + e^2πiθ20 |1 ⊗ |ψ

1. 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

(b) If we inverse Fourier transform |ψ₂ , we arrive at the state

^{2n−1 2n−1}

_{|ψ3 = 2}¹_{n e}2πik(x−2ⁿθ)/2ⁿ _{|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