Let and , so . Modular multiplication is the unitary acting on the computational…

PHYSICS · Subjective · Fermi University Physics · Mathematical Methods for Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Order finding and Shor's factoring algorithm

Problem

Let

N=9

and

a=4

, so

\gcd(a,N)=1

. Modular multiplication is the unitary

U_a

acting on the computational basis states

|x\rangle

x=0,1,\ldots,N-1

, by

U_a|x\rangle=|ax\bmod N\rangle

. (a) Explain why

U_a

is unitary. (b) Compute the orbit of

1

under repeated multiplication by

a=4

modulo

9

, and hence the order

r

. (c) For

s=0,1,\ldots,r-1

define

|u_s\rangle=\frac{1}{\sqrt r}\sum_{k=0}^{r-1}e^{-2\pi isk/r}\,|a^k\bmod N\rangle.

Show that

U_a|u_s\rangle=e^{2\pi is/r}|u_s\rangle

. (d) Show that

\dfrac{1}{\sqrt r}\displaystyle\sum_{s=0}^{r-1}|u_s\rangle=|1\rangle

. (e) Write out every

|u_s\rangle

explicitly for this

a

and

N

, in terms of

\omega=e^{2\pi i/r}

, and check their sum against part (d).

Browse the problem library