\documentclass{article}
\usepackage{amssymb}
\newcommand{\by}{\times}
\newcommand{\state}[1]{\left| #1 \right\rangle}
\newcommand{\tensor}{\otimes}
\newcommand{\field}{{\cal Z}/ (p-1)}
\newcommand{\ceiling}[1]{\left\lceil #1 \right\rceil} 
%\newtheorem{claim}{Claim}
%\newenvironment{proof}{\begin{trivlist}\item \textbf{Proof:}}{ $\Box$ \end{trivlist}}

\input{preamble}


\begin{document}
\lecture{12}{20 March 2001}{Daniel Spielman}{Jonathan Herzog}
This particular lecture was structured into four parts:
\begin{enumerate}
\addtocounter{enumi}{-1}
\item The Fourier transform (FT)
\item Computing the discrete logarithm problem with arbitrary quantum FTs
\item Which quantum FT's can we compute?
\item Showing that it suffices to use the quantum FTs that can be
  computed
\end{enumerate}

\addtocounter{section}{-1}
\section{Fourier Transform}
\label{sec:ft}

The Fourier transform is a linear transform, and so can be represented
with an $n \by n$ matrix. Let $\omega = e^{\frac{2 \pi i}{n}}$. Then
$M$ is a matrix where 
$$M_{x,y} = \frac{1}{\sqrt{n}} \omega^{xy}$$

The quantum fourier transform (QFT) is the transformation on states:
$$QFT_N: \state{x} \longrightarrow \frac{1}{\sqrt{n}} \sum_{y
  =0}^{N-1} \omega^{xy} \state{y}$$
where both $x$ and $y$ are basis vectors of $n = \log N$ bits,
interpreted as a number in binary. If $N$ is a power of 2, then we can
compute $QFT_N$ in $O(n^2)$ time.


\section{Discrete Log Problem}
\label{sec:dl}

The discrete log problem is a basic number-theoretic problem whose
hardness serves as the foundation of many modern cryptographic
techniques and protocols. Given as inputs a prime $p$, a number $g$
which generates ${\cal Z}^\star_p$ (i.e., the sequence $1$, $g$, $g^2$,
$g^3$... $g^{p-1} \bmod p$ contains all the numbers 1, 2, 3... $p-1$
in some order) and some number $x$, the discrete log problem is to
compute an $r$ such that $g^ r = x \bmod p$. [\textbf{Scribe note}: The
best known (classical) algorithms for this problem are the
Pohlig-Hellman algorithm, which is fast if $p-1$ is smooth, and the
number field sieve algorithm, which runs in $O\left( e^{(1.923 +
    o(1))(\log p)^\frac{1}{3} (\log \log p)^\frac{2}{3}} \right)$
time.]

The discrete log problem can be done in QP, with Shor's algorithm:
\begin{enumerate} 
  
\item Begin in the state $\state{0,0} \tensor
  \state{0}$, where the $0$'s are actually $\log (p-1)$ bit
  registers. (This is another way of writing a $3 \log (p-1)$ bit
  register, where we treat each third of the register as a distinct
  unit.) 


\item Apply $QFT_{p-1}$ to each of the first two registers, where
  $\omega = e^{\frac{2 \pi i}{p-1}}$. This moves the system into the
  state:

  $$\frac{1}{p-1} \sum_{a \in \field} \sum_{b \in \field} \state{a,b}
  \tensor \state{0}$$
  
\item Replace the final $\state{0}$ with $\state{g^a x^{-b} \bmod p}$.
  (Since $a$ and $b$ are in the $\state{a,b}$ register, this
  substitution is a reversible computation.\footnote{That is, if $g$
    and $x$ are considered to be constants, or hardwired into the
    circuit.}) This puts us in the state: 
  
  $$\frac{1}{p-1} \sum_{a \in \field} \sum_{b \in \field} \state{a,b}
  \tensor \state{g^a x^{-b} \bmod p}$$

\item Then we apply $QFT_{p-1}$ again to each of the first two
  registers, putting us in state:

  $$\frac{1}{p-1} \sum_{a \in \field} \sum_{b \in \field} \sum_{c \in
  \field} \sum_{d \in \field} \omega^{ac+bd} \state{c,d}
  \tensor \state{g^a x^{-b} \bmod p}$$

\item Measure the entire register.

\end{enumerate}

Okay, why does this work? 
\begin{claim}
If you actually observe
$c$, $d$, and $g^k \bmod p$, then $c$ and $d$ are uniformly chosen
from pairs such that $cr = -d \bmod p$, and $k$ is chosen uniformly
from $\left[0 \ldots p-1\right]$.
\end{claim}

\begin{proof}
  
  For a given $c$, $d$, and $g^k \bmod p$, what is the magnitude of
  $\state{c,d,g^k \bmod p}$? Well, how many ways can we end up with
  those values? Look at the last register. In step 2, we replaced
  $\state{0}$ with $\state{g^a x^{-b} \bmod p}$, and $x = g^r \bmod
  p$. So if we observe $g^k \bmod p$ it must be that $k = a - br \bmod
  (p-1)$. Or, rewritten, that $a = br -k \bmod (p-1)$.

  So, given a $k$, $a$ is fixed by the value of $b$. So write the
  final state as:
%
  $$\sum_{c} \sum_{d} \sum_{k}  \beta^k_{c,d} \state{c,d,g^k}$$
%  
  Through algebraic manipulation, we can find that
%
  \begin{eqnarray}
    \beta_{c,d}^k &=& \frac{1}{(p-1)^2} \sum_{b \in \field}
    \omega^{c(br-k) + db}\\ 
    & =& \frac{1}{(p-1)^2} \omega^{ck} \sum_{b \in \field}
    \omega^{b(cr+d)}\label{eqn:beta}
  \end{eqnarray}
%
  If $cr+d=0 \bmod (p-1)$, then $\omega^{b(cr+d)} =1$. In that case,
  $\left| \beta_{c,d}^k \right|^2 = \frac{1}{(p-1)^2}$. So, if $cr =
  -d \bmod p$, then the probability of observing the state
  $\state{c,d,g^k \bmod p}$ is exactly $\frac{1}{(p-1)^2}$. But there
  are exactly $(p-1)^2$  such pairs of $(c,d)$, so the probability of
  observing one such pair is exactly 1. And since $k$ is free, it can
  range over all values in $\left[0 \ldots p-1\right]$.
\end{proof}

Great. Now, if $c$ is relatively prime to $p-1$, we can solve the
equation $cr-d=0 \bmod (p-1)$ to find the value of $r$. (What is the
probability that $c$ is relatively prime to $p-1$? It turns out to be
at least $\frac{1}{\log p}$.) 

As a sanity check, let's make sure that all the other amplitudes go to
zero: Let  $cr + d = f \bmod (p-1)$. Then if $f \not = 0$, look at the
value of  $\beta_{c,d}^k$ we derived in equation (\ref{eqn:beta})
above:
$$\beta_{c,d}^k = \frac{1}{(p-1)^2} \sum_{b \in \field} \omega^{bf}$$
But we defined $\omega$ to be a $(p-1)$st 
  root of unity, so the sum in the above
equation is the sum of a number of roots of unity, all evenly spaced
around 0. Hence, they all cancel each other out in the sum.

Now, as a digression, how can we use this algorithm to factor? The
trick is to use a number theoretic fact: if $m$ is a composite number,
and $x^2 = y^2 \bmod m$, but $x \not = \pm y \bmod m$, then $x-y$ is a
non-trivial factor of $m$. We also know that $(-1)^2 = 1 \bmod m$, so
all we need to do is find another square root of unity.

So, choose a random $x<m$. Then find the order of $x$ in ${\cal
  Z}_m^\star$.\footnote{Note that if $x<m$ and $x \not \in {\cal
    Z}_m^\star$, then $x$ is itself a factor of $m$ and you're done.}
In other words, find the least $r$ such that $x^r =1\bmod m$. Then
  $x^\frac{r}{2}$ will be a square root of $1 \bmod m$, and with
  probability .5 it will not be $\pm 1$. 


\section{Calculable Quantum Fourier Transforms}
\label{sec:actual}

So, which quantum transforms can we actually compute? When $N=2^n$,
i.e. the size of the matrix is a power of 2, it is easy to compute
the function:

$$x \longrightarrow \frac{1}{\sqrt{N}} \sum_{y=0}^{2^n -1} e^{\frac{2
    \pi i x y}{N}} \state{y}$$

Here's how it's done. Write $x$ and $y$ in binary notation:
\begin{eqnarray*}
  x& =& 2^{n-1} x_1 + 2^{n-2} x_2 + \ldots 2 x_{n-1} + x_n \\ 
  y& =& 2^{n-1} y_1 + 2^{n-2} y_2 + \ldots 2 y_{n-1} + y_n 
\end{eqnarray*}
Then
\begin{eqnarray*}
  xy \bmod 2^n &=& y_1 \left(2^{n-1} x_n\right)\\
  && + y_2 \left(2^{n-2} x_n + 2^{n-1} x_{n-1}\right)\\
  && \vdots\\
  && + y_n \left(x_n + 2 x_{n-1} + \ldots 2^{n-1} x_1 \right)
\end{eqnarray*}
So, letting $\omega = e^{\frac{2i\pi}{N}}$, we can write the transform
  as:
\begin{eqnarray*}
(x_1, \ldots x_n) \longrightarrow &\frac{1}{\sqrt{N}}& \left(
  \state{0} + \omega^{x_n 2^{n-1}} \state{1} \right)\\
  &\tensor& \left(\state{0} + \omega^{x_{n-1} 2^{n-1} + x_n 2^{n-2}}
    \state{1} \right)\\
  & \vdots & \\
  & \tensor&  \left( \state{0} + \omega^{x_n + 2 x_{n-1} + \ldots +x_1
      2^{n-1}} \state{1} \right) 
\end{eqnarray*}

So, for bit $y_n$ of the output, we can construct the sequence of
gates:

\begin{center}
  

\begin{picture}(250,100)
\put(0,10){$x_n$}
\put(0,20){$x_{n-1}$}
\put(0,30){$\vdots$}
\put(0,45){$x_3$}
\put(0,55){$x_2$}
\put(0,65){$x_1$}

\put(40,60){\framebox(10,10){H}}
\put(70,60){\framebox(35,15){$R_{\omega^{2^{n-2}}}$}}
\put(120,60){\framebox(35,15){$R_{\omega^{2^{n-3}}}$}}
\put(200,60){\framebox(35,15){$R_{\omega^{2^{n}}}$}}

\put(15,10){\line(1,0){240}}
\put(25,20){\line(1,0){230}}
\put(15,45){\line(1,0){240}}
\put(15,55){\line(1,0){240}}

\put(15,65){\line(1,0){25}}
\put(50,65){\line(1,0){20}}
\put(105,65){\line(1,0){15}}
\put(155,65){\line(1,0){15}}
\put(185,65){\line(1,0){15}}
\put(235,65){\line(1,0){20}}
\put(172,65){$\ldots$}

\put(88,60){\line(0,-1){5}}
\put(138,60){\line(0,-1){15}}
\put(218,60){\line(0,-1){50}}

\put(88,55){\circle*{2}}
\put(138,45){\circle*{2}}
\put(218,10){\circle*{2}}

\put(260,65){$y_n$}
\end{picture}
\end{center}
where $R_{\omega^i}$ is the gate represented by the unary transform
$$\left( 
  \begin{array}{cc}
    1 & 0 \\
    0 & \omega^i \\
  \end{array}
\right)
$$

We then obtain bit $y_{n-1}$ in a similar way from
  bits $x_{2}, \ldots, x_{n}$, and so on.


\section{Sufficiency of these Transforms}
\label{sec:last}

[\textbf{Scribe note:} Due to time constraints, the lecturer gave only
a proof sketch of this.]  Since we can only use transforms where the
size is a power of 2, that's exactly what we do when actually
performing Shor's algorithm. Replace $QFT_{p-1}$ with $QFT_{2^n}$,
where $30 (p-1) \log p < 2^n < 60 (p-1) \log p$. Then, if we get
$(c,d)$ out of the first algorithm, there is a non-negligible chance
that we get:
%
$$ \left( \ceiling{\frac{2^n}{p-1} c}, \ceiling{\frac{2^n}{p-1} d} \right)$$

How much of a chance? We will see the pair on the right with
probability at least $\frac{1}{10 \log p}\Pr[(c,d)]$. So, by using
these larger transformations, we map each possible output of the
original algorithm to something in a larger domain. 

Another way to see this is to look at the results of
$$QFT_{2^n} \left( QFT_{p-1}^{-1} \left( \state{c} \right) \right)$$
Before we measure, we get out some superposition
$$ \sum_{c' = 0}^{2^n} \beta_{c'} \state{c'}$$
where $\beta_{c'}$ is distributed nicely. If you graph the
distribution\footnote{ Which I can't do easily in LaTeX...} of
$\beta_{c'}$, you'll see that it is close to zero almost everywhere,
with all the non-zero amplitudes in a nice bell-like distribution
centered at $\ceiling{\frac{2^n c}{p-1}}$, with a width of
$\frac{2^n}{p-1}$. 

In other words, using the calculable transformations instead of the
exact transformations will give you results ``close'' to those from
the exact algorithm. 

\end{document}