Admin¶
- Two talks by John Preskill this week.
- Henry, please record the lecture!
Last time¶
- Phase Estimation Algorithm, RSA, Factoring and Order Finding
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.
Quantum Algorithm for 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
$$ U_x \ket{y} = \ket{xy \text{ mod } N} $$if $0 \leq y < N$, and otherwise $U_x \ket{y} = \ket{y}$ if $y$ is at least $N$.
Modular multiplication unitary¶
$$ U_x \ket{y} = \ket{xy \text{ mod } N} $$Fact 1: This map is unitary.
Fact 2: $U_x$ is computable by a quantum circuit with $\mathrm{poly}(n)$ gates.
Modular multiplication unitary¶
Subtlety: it's easy to implement a quantum circuit for the map
$$ V \ket{x,y,0} = \ket{x,y,xy \text{ mod } N}. $$This is different from $U_x$. The proof that $U_x$ is unitary uses the fact that $gcd(x,N) = 1$.
Modular multiplication unitary, repeated¶
$$ U_x^{2_j} \ket{y} = \ket{x^{2^j} y \text{ mod } N} $$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$.
Eigenvectors 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
$$ \ket{v_s} = \frac{1}{\sqrt{r}} \sum_{k=0}^{r -1} \omega_r^{sk} \ket{x^k \text{ mod } N} $$Claim: $U_x \ket{v_s} = \exp \Big( 2\pi i \frac{s}{r} \Big) \, \ket{v_s}$.
Phase Estimation Algorithm¶
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.
Quantum Algorithm for Order Finding¶
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
$$ \widetilde{\theta} = 0.011110110011\ldots $$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}$?
Getting the eigenvectors¶
We can solve Issue 2 by running Phase Estimation on the superposition
$$ \frac{1}{\sqrt{r}} \sum_{s = 0}^{r-1} \ket{v_s} $$While it's hard to construct $\ket{v_s}$ individually, this superposition is easy to prepare, because this is equal to the standard basis state $\ket{1}$. (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$.
Measuring the second register yields $\ket{\widetilde{\theta}_s}$ for a uniformly random $0 \leq s < r$.
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
$$ \widetilde{\theta}_s = \frac{358}{1000} = \frac{179}{500}. $$This is equal to $s/r$. But since $s/r$ is already in most reduced form, it must be $s = 179$ and $r = 500$.
However $\widetilde{\theta}_s$ is not $s/r$ exactly.
We solve Issue 1 by the Continued Fractions Algorithm.
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.
Summary of Order Finding¶
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.
Idea behind Continued Fractions¶
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$.
We get good approximations of $\varphi$ if we just keep the first few "terms" of the continued fractions.
Continued Fractions example¶
$\pi = 3.1415926535 8979323846 2643383279 \cdots$
An inefficient way of writing $\pi$ as a fraction:
$$ \pi = \frac{31415926535}{10000000000} + \cdots $$In order to get $k$ decimal places of accuracy, need to keep $k$ digits of numerator and denominator.
Continued Fractions example¶
$\pi = 3.1415926535 8979323846 2643383279 \cdots$
An better way of writing $\pi$ as a fraction:
$$ \pi = 3 + \cfrac{1}{7 + \cfrac{1}{15 + \cfrac{1}{1 + \cdots}}} $$Continued Fractions example¶
$\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!
Summary of Factoring via Quantum Computers¶
- If we can factor, we can break RSA.
- If we can solve Order Finding, we can factor integers.
- By running Phase Estimation with Modular Multiplication unitary a few times, we can get noisy estimates of $s/r$.
- We can "decode" these estimates by using Continued Fractions algorithm.
How far away is Shor's 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.
What will replace RSA?¶
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.
Next time¶
Quantum search algorithms