1. Bernstein-Vazirani with a noisy oracle [16 points]

Recall that in the Bernstein-Vazirani problem, there is a hidden string \(s \in \{0,1\}^n\) and we have access to a function \(f : \{0,1\}^n \to \{0,1\}\) such that

\[f(x) = s \cdot x \bmod 2 = (s_1 x_1 + s_2 x_2 + \cdots + s_n x_n) \bmod 2.\]

The goal is to recover the secret \(s\), and the Bernstein-Vazirani algorithm allows us to do this with only a single quantum query to \(f\).

Suppose now that the function \(f\) is noisy, in the sense that, for some noise parameter \(\varepsilon > 0\), we only have the guarantee

\[\frac{\#\! \left\{ x \in \{0,1\}^n : f(x) = s\cdot x\bmod 2\right\}}{2^n} \geq 1-\varepsilon.\]

1. [10 pts] Calculate a lower bound on the probability that a single run of the Bernstein-Vazirani algorithm nevertheless succeeds in recovering \(s\) and make sure to justify your calculation.

2. [6 pts] What happens when \(\varepsilon = 1/2\)? Explain why there is no hope for an algorithm to recover \(s\) in this case.

2. Group theory for Shor [16 points]

1. [0 pts] 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. [4 pts] Use this to show that the groups \(\mathbb{Z}_{p-1}\) and \(\mathbb{Z}_p^*\) are isomorphic.

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

4. [4 pts] 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. [4 pts] 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\)?

3. More group theory for Shor [16 points]

1. [4 pts] 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. [4 pts] 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. [4 pts] 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. [4 pts] 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})\).

4. 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\).

5. 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)}\).

Extra credit: 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.