• You may make use of any non-human assistance — any book, the web (but do not ask for help online), etc. Solutions must be self-contained.
• Solutions given with little or no justification may receive little or no credit.
• Solutions will be graded based on correctness, quality, and presentation. Turn in something that you are proud of.
• There are 3 problems. Submit only 2 for grading.
“I pledge on my honor that I have neither given nor received unauthorized aid on this assignment.” Signature:
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 = (gi) ∈ QZ/miZ. Recall that the Quantum Fourier Transform for G was
defined where
k µ(g,h) := Yωmgiihi, ωmi := exp(2πi/mi).
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 = (aij),
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
D |v1i = |w1i + |w2i + |w3i, E |x1i = |y1i − |y2i,
D|v2i = 2|w2i − |w3i, E |x2i = 2|y2i,
E |x3i = |y1i + |y2i.
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 bs = 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 Ub and Ua†.
(i) Show that the state in the circuit before passing through the two inverse Quantum
Fourier Transform blocks is proportional to
.
(ii) 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 bs = a.]
(iii) Conclude that measuring the top two registers of the circuit produces pairs |u,vi such that bua−v = 1. Explain how to use such pairs to find s.
