[Solved] Quantum Homework 14

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(2i/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.