\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