- Two talks by John Preskill this week.
- Henry, please record the lecture!

- Phase Estimation Algorithm, RSA, Factoring and Order Finding

**Input**: given positive integers $N,x$ such that

- $1 \leq x < N$
- $gcd(N,x) = 1$ (i.e. they do not have any nontrivial factors in common)

**Output**: find smallest integer $r$ such that $x^r = 1 \text{ mod } N$ (called the **order** of $x$ mod $N$).

There is a *classical reduction* between Factoring and Order Finding.

**Input**: Integers $N$ and $1 \leq x < N$ coprime to $N$.

Order Finding algorithm uses Phase Estimation Algorithm with respect to the **modular multiplication unitary** $U_x$, defined as

if $0 \leq y < N$, and otherwise $U_x \ket{y} = \ket{y}$ if $y$ is at least $N$.

**Fact 1**: This map is unitary.

**Fact 2**: $U_x$ is computable by a quantum circuit with $\mathrm{poly}(n)$ gates.

**Subtlety**: it's easy to implement a quantum circuit for the map

This is different from $U_x$. The proof that $U_x$ is unitary uses the fact that $gcd(x,N) = 1$.

**Facts**: This map is unitary, and is computable by a quantum circuit with $\mathrm{poly}(n,j)$ gates.

This uses fact that one can "shortcut" compute $x^{2^j}$ modulo $N$ without doing $2^j$ multiplications, by repeatedly squaring, reducing mod $N$, squaring, reducing mod $N$, etc...

$$ x \to x^2 \to x^2 \text{ mod } N \to (x^2 \text{ mod } N)^2 \to x^4 \text{ mod } N \to \cdots $$Remember that we're trying to use Phase Estimation Algorithm.

We have efficient way to implement controlled $U_x^{2_j}$ operations.

We just need an eigenvector of $U_x$.

Let $r$ denote the **order** of $x$ (i.e. $x^r = 1$ mod $N$). Then for all $0 \leq s < r$, define the state

**Claim**: $U_x \ket{v_s} = \exp \Big( 2\pi i \frac{s}{r} \Big) \, \ket{v_s}$.

Given:

- Ability to run controlled versions of $U, U^2, U^4, \ldots, U^{2^j},\ldots$
- An
**eigenstate**$\ket{\psi}$ where $U \ket{\psi} = e^{2\pi i \theta} \ket{\psi}$

Using $O(t)$ qubits of ancilla, PEA outputs an estimate $\widetilde{\theta}$ satisfying

$$ | \widetilde{\theta} - \theta | \leq 2^{-t} $$with high probability. The algorithm runs in $\mathrm{poly}(t)$ time.

**Input**: Integers $N,x$ where $2^{n-1} \leq N < 2^n$ and $1 \leq x < N$ coprime to $N$.

Suppose we run Phase Estimation algorithm with $O(n)$ ancilla qubits, with controlled-$U_x^{2^j}$ operations and an eigenvector $\ket{v_s}$ for some $0 \leq s < r$.

**Complexity**: $\mathrm{poly}(n)$ (including complexity of controlled-$U_x^{2_j}$).

**Output**: estimate $\widetilde{\theta}_s$ that is within $2^{-3n} \leq 1/N^3$ of $s/r$.

Remember that the goal is to recover the integer $r$, the order of $x$.

**Issue 1**: The algorithm outputs something that looks like

We don't know $s$, $r$. How do find the $s/r$ fraction corresponding to this?

**Issue 2**: How do we get our hands on the eigenvector $\ket{v_s}$?

We can solve Issue 2 by running Phase Estimation on the superposition

$$ \frac{1}{\sqrt{r}} \sum_{s = 0}^{r-1} \ket{v_s} $$**exercise**)

After running PEA on input $\ket{1}$, the output will be approximately

$$ \approx \frac{1}{\sqrt{r}} \sum_{s = 0}^{r-1} \ket{v_s} \otimes \ket{\widetilde{\theta}_s} $$where $|\widetilde{\theta}_s - s/r| \leq 2^{-3n} \leq 1/N^3$.

Imagine that $\widetilde{\theta}_s$ was actually $s/r$ **exactly**, and furthermore $s$ was coprime to $r$.

Then we can recover $s,r$ from $\widetilde{\theta}_s$.

**Example**: Suppose $\widetilde{\theta}_s = 0.358$. Then clearly

However $\widetilde{\theta}_s$ is not $s/r$ exactly.

We solve **Issue 1** by the **Continued Fractions Algorithm**.

This is a classical algorithm from number theory.

Let $\varphi$ be a real number and $s/r$ a fraction such that

$$ \Big | \varphi - \frac{s}{r} \Big| \leq \frac{1}{2r^2}. $$Then the Continued Fractions Algorithm, given input $\varphi$, will output the reduced form of $s/r$ in time $\mathrm{poly}(\log r)$.

We can apply Continued Fractions to our setting because we have

$$ \Big | \widetilde{\theta}_s - \frac{s}{r} \Big | \leq \frac{1}{N^3} $$which is less than $\frac{1}{2r^2}$. So Continued Fractions outputs $s/r$ in reduced form. If $s$ is coprime to $r$, then we get $s,r$ exactly.

Run Phase Estimation with the unitary controlled-$U_x$ (and its powers) and input state $\ket{1}$ (which is uniform superposition of eigenvectors).

Get random estimate $\widetilde{\theta}$.

Use Continued Fractions algorithm on $\widetilde{\theta}$ to obtain reduced form $a/b$ of $s/r$.

Check whether $x^b = 1$ mod $N$. If so, then $b = r$. Otherwise, go back to Step 1.

Each loop succeeds with probability $1/\log \log r$, so we only have to repeat a few times.

Every real number $\varphi$ can be written as

$$ \varphi = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}} $$for some sequence of integers $a_0,a_1,a_2,\ldots$.

$\pi = 3.1415926535 8979323846 2643383279 \cdots$

An **inefficient** way of writing $\pi$ as a fraction:

In order to get $k$ decimal places of accuracy, need to keep $k$ digits of numerator and denominator.

$\pi = 3.1415926535 8979323846 2643383279 \cdots$

An **better** way of writing $\pi$ as a fraction:

$\pi = 3.1415926535 8979323846 2643383279 \cdots$

If we just keep $3$ terms of the continued fractions, we get

$$ \pi \approx 3 + \cfrac{1}{7 + \cfrac{1}{15 + 1}} = \frac{355}{113} = 3.1415929\cdots $$Better bang for buck!

- If we can factor, we can break RSA.

- If we can solve Order Finding, we can factor integers.

- We can "decode" these estimates by using Continued Fractions algorithm.

**Gidney, Ekera 2018**: given current methods for error correction, we would need

- 20 million noisy qubits
- 8 hours

to factor a 2048-bit RSA integer.

**IBM Roadmap**: 1 million qubits by 2030.

US National Institute for Standards and Technology (NIST) just concluded a multiyear competition to find **postquantum** cryptosystems to replace RSA. The winners are...

- CRYSTALS-Kyber
- CRYSTALS-Dilithium
- FALCON
- SPHINCS+

Kyber is for encryption, and the last three are for digital signatures.

Kyber, Dilithium, and Falcon are all based on **lattice problems**, where the goal is to find short vectors in a high-dimensional lattice.

It is believed that these problems cannot be quickly solved by quantum computers.

It is an important research problem to find better evidence that lattice problems are hard for quantum computers.

But there's always the possibility that someone can find a fast quantum algorithm for them...

It will take time to build confidence in these new cryptosystems.

Quantum search algorithms

In [ ]:

```
```