CSE 599Q: Homework #4

1. Group theory for Shor [15 points]

1. [0 points] We write $\mathbb{Z}_n$ for the additive group of integers modulo $n$, whose elements can be represented by the numbers $\{ 0,1,2,\ldots,n-1 \}$, and we use $\mathbb{Z}_n^*$ to denote the multiplicative group of integers modulo $n$, whose elements can be represented by the numbers $\{ 1 \leq a < n : \gcd(a,n)=1 \}$.

   Show that for $p$ prime, there is some generator $g \in \mathbb{Z}_p^*$ such that $\mathbb{Z}_p^* = \{ g^0, g^1, g^2, \ldots, g^{p-2} \}$.

   You may assume that $\mathbb{Z}_p^*$ has a generator for the rest of the problem.

2. Use this to show that the groups $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p^*$ are isomorphic.

3. Show that $g^{(p-1)/2} \equiv -1 \pmod p$ must hold, where $g$ is your generator of $\mathbb{Z}_p^*$.

4. Suppose that $p,q$ are two distinct prime numbers. Show that $\mathbb{Z}_{pq}^*$ and $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$ are isomorphic.

   You may use the Chinese Remainder Theorem: If $m,n$ are two numbers with $\gcd(m,n)=1$, then the system of equations $\{ x \equiv a \pmod m, x \equiv b \pmod n \}$ has a solution and any two solutions $x,x'$ satisfy $x \equiv x' \pmod {mn}$.

   What is the image of $-1$ under this isomorphism?

5. Suppose you now compose these isomorphisms to map $\mathbb{Z}_{pq}^* \to \mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1}$. What is the image of $-1$?

2. More group theory for Shor [16 points]

1. If $(G,+)$ is a group with identity element $0$, then the order of an element $g \in G$ is the smallest $k$ such that $g+g+\cdots+g = 0$ (the sum of $k$ copies of $g$). We write $\mathrm{ord}_G(g)$ for the order of $g$.

   Suppose $m = 2^k b$ is an even integer ($k \geq 1$) and $b$ is odd. Show that if $u \in \mathbb{Z}_m$ is odd, then $2^k$ divides $\mathrm{ord}_{\mathbb{Z}_m}(u)$. Show that if $u \in \mathbb{Z}_m$ is even, then $2^k$ does not divide $\mathrm{ord}(u)$.

2. Suppose $m,n$ are even integers and we pick $u \in \mathbb{Z}_m$ and $v \in \mathbb{Z}_n$ uniformly at random. Show that with probability at least $1/2$, the largest power of $2$ that divides $\mathrm{ord}_{\mathbb{Z}_m}(u)$ is different from the largest power of $2$ that divides $\mathrm{ord}_{\mathbb{Z}_n}(v)$.

3. Show that if $(u,v) \in \mathbb{Z}_m \times \mathbb{Z}_n$, then

   $$\mathrm{ord}_{\mathbb{Z}_m\times \mathbb{Z}_n}(u,v) = \mathrm{LCM}\left(\mathrm{ord}_{\mathbb{Z}_m}(u),\mathrm{ord}_{\mathbb{Z}_n}(v)\right).$$

4. Suppose now that $p,q$ are distinct odd prime numbers and we pick $u \in \mathbb{Z}_{p-1}$ and $v \in \mathbb{Z}_{q-1}$ uniformly at random, and define $L \seteq \mathrm{ord}_{\mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1}}(u,v)$. Use Problem 1 and parts (A)-(C) to show that with probability at least $1/2$, both of the following hold:

   • $L$ is even
   • $(u,v)+(u,v)+\cdots+(u,v)$ (summed $L/2$ times) is not equal to $(\frac{p-1}{2},\frac{q-1}{2})$.

3. Non-trivial square roots [12 points]

Use Problems 1 and 2 to show the following: Suppose that $B=pq$ is a product of two distinct odd primes $p$ and $q$. Choose an element $A \in \mathbb{Z}_{B}^*$ uniformly at random and define $L \seteq \mathrm{ord}_{\mathbb{Z}_B^*}(A)$.

Show that with probability at least $1/2$, it holds that $L$ is even and $A^{L/2}$ is a non-trivial square root of $1$ modulo $B$, i.e., $\left(A^{L/2}\right)^2 \equiv 1 \pmod B$, and $A^{L/2} \not\equiv \pm 1 \pmod B$.

4. Order finding reduces to factoring [12 points]

In class, we showed that if $B=pq$ is a product of two primes and we can find the order of an element $A$ in $\mathbb{Z}_B^*$, we can produce the factors $p$ and $q$.

Suppose now that you have a subroutine that takes a number $B$ as input and outputs its prime factorization. Show that you can use this to find the order of any given element $A \in \mathbb{Z}_B^*$. Your algorithm shold run in polynomial time in the size of the input, i.e., in time $(\log_2 B)^{O(1)}$.

5. Shor critique [20 points]

One measure of progress in building quantum computers might be the size of numbers they can factor via Shor’s algorithm. The state of the art is still $15 = 3 \cdot 5$. But is this impressive? Is $77 = 7 \cdot 11$ more impressive?

1. Read the paper Pretending to factor large numbers on a quantum computer. Write a paragraph summarizing their main critique of prior experiments.

2. Read the paper Realization of a scalable Shor algoirthm. Do you think it adequately addresses the criticisms of the first article? Why (or why not)? Explain your thinking.

E. Extra credit: Hamiltonian evolution [25 points]

Read Sections 6.1–6.2 of Nielsen-Chuang and do Exercise 6.12.