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

- Quantum Fourier Transform

Quantum algorithm computing the **Discrete Fourier Transform** unitaries $F_N$, using an $n$-qubit quantum circuit with $\mathrm{poly}(n)$ gates ($N = 2^n$).

Phase Estimation Algorithm (PEA) is one of the most important subroutines in quantum computing.

**Goal of PEA**: 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}$,

estimate $\theta$.

The eigenvalue $e^{2\pi i \theta}$ looks like a global phase...

**relative** phase once you run the controlled-$U$ gate in superposition:
\begin{align*}
cU \ket{+} \ket{\psi} &= \frac{1}{\sqrt{2}} (\ket{0} \ket{\psi} + \ket{1} U \ket{\psi}) \\
&= \frac{1}{\sqrt{2}} (\ket{0} \ket{\psi} + e^{2\pi i \theta} \ket{1} \ket{\psi}) \\
&= \frac{1}{\sqrt{2}} (\ket{0} + e^{2\pi i \theta} \ket{1}) \ket{\psi}
\end{align*}

Assume for simplicity that $\theta$ can be represented using exactly $t$ bits. In other words the binary representation of $\theta$ looks like

$$ \theta = 0.\theta_1 \theta_2 \cdots \theta_t $$where $\theta_1,\theta_2,\ldots \in \{0,1\}$. This is equivalent to

$$ \theta = \frac{\theta_1}{2} + \frac{\theta_2}{2^2} + \cdots + \frac{\theta_t}{2^t}. $$Measuring the first $t$ qubits will yield $\ket{\theta_1,\theta_2,\ldots,\theta_t}$.

Let's analyze a special case where $t = 2$, and $\theta = \frac{\theta_1}{2} + \frac{\theta_2}{4}$ for $\theta_1,\theta_2 \in \{0,1\}$.

(On the board...)

**Question**: What if the phase $\theta$ cannot be exactly expressed as $t$ bits?

**Answer**: If we use $t + k$ ancilla qubits, and measure only the first $t$ ancilla qubits, we will get the best $t$-bit approximation $\widetilde{\theta}$ of $\theta$ with probability $1 - 2^{-k}$.

**Question**: What happens if $\ket{\psi}$ is not an eigenvector of $U$?

**Answer**: The set $\{ \ket{\phi_j} \}$ of eigenvectors of $U$ forms a basis for $\C^{2^n}$ (if $U$ is $n$-qubit unitary). We can write $\ket{\psi}$ as
$$
\ket{\psi} = \sum_j \alpha_j \ket{\phi_j}
$$
for some coefficients $\alpha_j$.

Running Phase Estimation on $\ket{\psi}$ with ancilla qubits $\ket{0 \cdots 0}$ yields a state that is close to

$$ \approx \sum_j \alpha_j \ket{\phi_j} \otimes \ket{\widetilde{\theta}_j} $$where $\widetilde{\theta}_j$ is an approximation of the eigenphase $\theta_j$, i.e. $U \ket{\phi_j} = e^{2 \pi i \theta_j} \ket{\phi_j}$.

Measuring the last register yields $\widetilde{\theta}_j$ with probability $|\alpha_j|^2$.

- Shor's Factoring Algorithm
- Simulation of Quantum Systems
- Quantum Algorithms for Optimization

- Invented by Rivest, Shamir, and Adleman in 1977
- Most widely deployed public-key cryptosystem
- Enables public-key encryption as well as digital signatures

- Bob generates a
*secret-key/public-key*pair $(sk,pk)$, and publishes $pk$ on the internet. - Alice uses $pk$ and her message $m$ to create a
*ciphertext*$c$ which she sends to Bob. - Bob gets $c$, and uses $sk$ to decode $m$.
- The adversary sees $(pk,c)$, and should get no information about $m$.

- Pick random prime number $1 \leq e \leq (p-1)(q - 1)$.

- Compute integer $d$ where $ed = 1$ mod $(p-1)(q-1)$.

- Set public key $pk = (e,N)$, and secret key $sk = d$.

**Alice** gets a message $1 \leq m < N$. She computes and send $c = m^e$ mod $N$, and send $c$ to Bob.

**Bob** computes $m' = c^d$ mod $N$ to decode the message.

*Fermat's Little Theorem*.

**Adversary** sees the public key $pk = (e,N)$ and the encrypted message (ciphertext) $c$.

It does not know the primes $p,q$, nor the secret key $sk = d$.

If it knew the prime factorization $N = pq$ it could compute the secret key!

In other words, if the adversary can factor large integers very quickly, then it can break the security of the RSA cryptosystem).

(It's an open question of whether breaking RSA necessarily means being able to factor!)

**Input**: Positive integer $N$.

**Output**: Prime factorization of $N$ as $p_1^{a_1} p_2^{a_2} \cdots$.

The prime factorization of $N$ is unique by the **Fundamental Theorem of Arithmetic**.

To find a factorization of $N$, it suffices to be able to find *some* nontrivial divisor of $N$.

It is widely believed that Factoring is hard for classical computers. The best classical algorithm, known as the **General Number Field Sieve**, takes time roughly
$$
\exp \Big( O (\log N)^{1/3} \Big)~.
$$

This is essentially **exponential** in the number of digits of $N$.

A quantum algorithm to solve Factoring in $\mathrm{poly}(\log N)$ steps.

Discovered by Peter Shor in 1993. He was inspired by Simon's Algorithm.

Shor's Algorithm is also a hybrid classical-quantum algorithm.

**Classical part**: reduce the factoring problem to**order finding**.**Quantum part**: solve 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$ mod $N$ (called the **order** of $x$ mod $N$).

**Goal**: we want to find a nontrivial divisor of $N$, assuming ability to solve Order Finding.

- Pick a random $1 \leq x < N$. If $gcd(N,x) \neq 1$, great! We've found a nontrivial factor of $N$.

- Otherwise, $gcd(N,x) = 1$. Compute the order of $x$ mod $N$; call this $r$.

- If $r$ is odd, go back to Step 1.

- If $r$ is even, then $x^r - 1 = 0$ mod $N$ and

If $a, b$ are multiples of $N$, go back to Step 1.

- Otherwise, we have found integers $a,b$ such that

Since $a,b$ are not multiples of $N$, computing $gcd(a,N)$ or $gcd(b,N)$ will yield a nontrivial divisor.

A quantum algorithm to solve Order Finding

In [ ]:

```
```