[SOLVED] Quantum - Week 14 Final

Description

QUANTUM ALGORITHMS FINAL EXAM

1. Let G be a finite Abelian group such that

by the Fundamental Theorem of Finitely Generated Abelian Groups. Regard elements g ∈ G as tuples g = (g_i) ∈ ^QZ/m_iZ. Recall that the Quantum Fourier Transform for G was

defined where

k µ(g,h) := ^Yω_m^gi_i^hi,    ω_mi := exp(2πi/m_i).

i=1

k

Show that FG = OFZ/miZ.

i=1

2. Recall that the Kronecker product of matrices A and B is defined

   a11B            ···            a1nB

A ∗ B := ^_    ^...                       ^...    ^_,                             A = (a_ij),

   am1B           ···            amnB

and that given a linear operator C : T → U, we denote the matrix of C relative to some specified ordered bases for T and U as [C].

Let V,W,X,Y be vector spaces with respective ordered bases

,

,

Define linear operators D : V → W and E : X → Y by

• |v₁i = |w₁i + |w₂i + |w₃i, E |x₁i = |y₁i − |y₂i,

D|v₂i = 2|w₂i − |w₃i,                                            E |x₂i = 2|y₂i,

• |x₃i = |y₁i + |y₂i.

Show that [D] ∗ [E] = [D ⊗ E], where the bases for V ⊗ X and W ⊗ Y are the usual lexicographically ordered bases. You may do this by direct calculation if you wish.

3. Given a group G, recall that the discrete logarithm problem takes as input elements a,b ∈ G such that b^s = a, and outputs the number s. Recall that the quantum solution to the discrete logarithm problem involves running the eigenvalue estimation circuit in series using the operators U_b and U_a^†.
   • Show that the state in the circuit before passing through the two inverse Quantum

Fourier Transform blocks is proportional to

.

• Carefully show that the state after passing through the two inverse Quantum Fourier Transform blocks but before measurement is proportional to

 ,

where m is the period/order of b in G. [Hint: use b^s = a.]

• Conclude that measuring the top two registers of the circuit produces pairs |u,vi such that b^ua^−v = 1. Explain how to use such pairs to find s.