\documentclass[landscape]{seminar}
\slideframe{none}
\usepackage{epsf}
\usepackage{color}
\usepackage{amssymb,amsfonts}

\newcommand{\ket}[1]{\left| \, #1 \right\rangle}
\newcommand{\bra}[1]{ \left\langle #1 \, \right|}
\newcommand{\proj}[1]{\ket{#1}\bra{#1}}
\newcommand{\vpols}{\mbox{$\updownarrow$}}
\newcommand{\hpols}{\mbox{$\leftrightarrow$}}

\newcommand{\ppols}{\mbox{\small
\,\mbox{$\nearrow$}\llap{\mbox{$\swarrow$}}\,}}

\newcommand{\qpols}{\mbox{\small
\,\mbox{$\searrow$}\llap{\mbox{$\nwarrow$}}\,}}

\newcommand{\rpols}{\mbox{\raisebox{-0.66ex}{$\triangleleft$}$\!\!\supset$}}
\newcommand{\lpols}{\mbox{$\subset\!\!$\raisebox{-0.66ex}{$\triangleright$}}}

\newcommand{\rz}{{\color{red}0}}
\newcommand{\ro}{{\color{red}1}}
\newcommand{\bz}{{\color{blue}0}}
\newcommand{\bo}{{\color{blue}1}}


\begin{document}

\pagestyle{empty}
\begin{slide}
\pagestyle{empty}
\begin{center}
{\large
Quantum Computers
}

Peter Shor\\
MIT

\end{center}

\end{slide}

\begin{slide}
What is the difference between
a computer and a physics 
experiment?
\end{slide}

\begin{slide}
One answer:\\*[2ex]
A computer answers mathematical questions.\\
A physics experiment answers physical questions.
\end{slide}

\begin{slide}
Another answer:\\*[2ex]
A physics experiment is a big, custom-built, finicky, piece of apparatus.\\
A computer is a little box that sits on your desk (or in your briefcase).
\end{slide}

\begin{slide}
A third answer:\\*[2ex]
You don't need to build a new computer for each mathematical
question you want answered.
\end{slide}

\begin{slide}
The mathematical theory of computing started in the 1930's
(before computers) \\ \\
After G\"odel proved his famous incompleteness theorem, it
 was followed by four papers giving
a distinction between computable and uncomputable functions \\(Church, Turing,
Kleene, Post, ca.\ 1936)\\ \\
These papers contained three definitions of computable functions which
looked quite different.
\end{slide}

\begin{slide}
{\Large Universality of computers I.}
\\ \\
This led Church and Turing to propose
\\ \\
{\Large Church-Turing thesis:}\\
{\large A Turing machine can perform any computation that any (physical) device
can perform.} \\ {\normalsize (Turing, Church, ca.\ 1936).}
\\ \\
Until recently, it was not generally realized this is a statement
about physics, and not about mathematics.
\end{slide}

\begin{slide}
With the development of practical computers, the distinction between
uncomputable and computable become much too coarse. \\ \\
To be practical, a program must return an answer in a reasonable
amount of time (minutes? days? years?).
\end{slide}

\begin{slide}
Theoretical computer scientists consider an algorithm {\em efficient}
if its running time is a polynomial function of the size $n$ of its 
input. ($n^2$, $n^3$, $n^4$, etc.)
\\
\\
The class of problems solvable with polynomial-time algorithms is called P
\\ \\
This is a reasonable compromise between theory and practice.
\end{slide}

\begin{slide}
For the definition of P (polynomial-time solvable problems) to be
meaningful, you need to know that it doesn't depend on the exact
type of computer you use.
\end{slide}
 
\begin{slide}
{\Large Universality of computers II.}
\\ \\
This led various computer scientists to propose the
\\ \\
{\Large Quantitative Church's Thesis}\\
{\large A Turing machine can perform {\em efficiently} any computation that any
(physical) device can perform efficiently.} \\
{\small (ca.\ 1970).}
\\ \\
If quantum computers can be built, this would imply this 
``folk thesis'' is probably not true.
\end{slide}

\begin{slide}
{\Large Misconceptions about Quantum Computers} \\*[2ex]
{\color{red} False: Quantum computers would be able to speed up 
all computations.}\\*[2ex]
Quantum computers are not just faster versions of classical computers,
but use a different paradigm for computation.
\\
They would speed up some problems by large factors and other problems
not at all.
\end{slide}

\begin{slide}
\epsfxsize=1.75in
\raisebox{-1in}{\epsfbox{Feynman.eps}}\hspace*{\fill}\epsfxsize=1.2in\raisebox{-1in}{\epsfbox{Manin.eps}}\\*[.1in]
{\Large Richard Feynman\ \ \ Yuri Manin}

{
\normalsize
\begin{itemize}
\item
Simulating physics using a digital computer seems inherently 
exponentially inefficient.  (R.~P.~Poplavskii, 1975; Feynman, 1982)
\item
A ``quantum computer'' might be able to get around this problem.
(Manin, 1980; Feynman, 1982)
\end{itemize}
}
\end{slide}

\begin{slide}
\epsfxsize=1.25in
\raisebox{5em}{\parbox{2in}{
{\Large David Deutsch}\\
In 1985, he asked whether quantum computers might speed up
computation.\\[2ex]
Problems with potential speed-ups by quantum computers were found by:
}}
\hspace*{\fill}\epsfbox{Deutsch.eps}\\*[2ex]

\vspace*{-2em}

\noindent David Deutsch and Richard Jozsa (1992)\\*[.4ex]
\noindent Andr\'e Berthiaume and Gilles Brassard (1992)\\*[.4ex]
\noindent Ethan Bernstein and Umesh Vazirani (1993)\\*[.4ex]
\noindent Dan Simon (1993)\\*[.4ex]
\noindent Peter Shor (1994)\\*[.4ex]
\noindent Lov Grover (1996)\\*[.4ex]
\end{slide}

\begin{slide}
What do we know quantum computers are good for?
\begin{itemize}
\item
Simulating/exploring quantum mechanical systems efficiently.\\
{}[Richard Feynman/Yuri Manin]\\
Estimating zeros of certain Riemann zeta functions [van Dam]
\item
Finding periodicity.\\
Simon's problem [Dan Simon]\\
Factoring large integers and finding discrete logarithms efficiently
[PWS]\\
Pell's equation and class groups [Sean Hallgren].
\item
Searching large solution spaces more efficiently [Lov Grover]\\
Amplifying the success probably of (quantum) algorithms with small 
success probabilities.\\
Finding solutions by walking on large graphs more efficiently
\end{itemize}
\end{slide}

\begin{slide}
Searching\\ \\
Quantum computers give a quadratic speed-up for 
exhastive search problems (Lov Grover).
Looking through $N$ possibilities takes
\begin{itemize}
\item expected time $N/2$ on a classical computer.
\item expected time $\frac{\pi}{4} \sqrt{N}$ on a quantum computer.
\end{itemize}
\end{slide}

\begin{slide}
{\large Factoring}\\ \\
Quantum computers give an exponential speed up for factoring
large integers.
\\
\\
Given a number $N$, find $A$,$B$ $<$ $N$ so 
\[
A*B = N
\]
\end{slide}

\begin{slide}
Factoring an $L$-bit number\\ \\
Best classical method is the number field sieve (Pollard)\\
time: $\exp(c L^{1/3} (\log L)^{2/3})$. \\ \\
Quantum factoring:  theoretical asymptotic time bound $c L^2 (\log L) (\log \log L)$
\end{slide}

%\begin{slide}
%{\Large Misconceptions about Quantum Computers II.} \\*[2ex]
%{\color{red} False: A quantum computers is $X$ times as fast as a classical
%computer.}\\*[2ex]
%In fact, a single step on a quantum computer is almost certain to take 
%longer than a single step on a classical computer because 
%\begin{itemize}
%\item Quantum computers need to keep coherence between superpositions of
%computational states.
%\item Quantum computers can be used for classical computation.
%\end{itemize}
%Quantum computers speed up computations by drastically reducing
%the number of steps required.
%\end{slide}


%\begin{slide}
%\begin{center}
%Estimates on Cost of Factoring\\
%(using known algorithms)
%\\*[2ex]
%\begin{tabular}{|c|cc|}
%\hline
%Number of &  Classical & Quantum\\
%Digits & instructions & logical ops \\*[.2ex]
%\hline
%& & \\*[-1.3ex]
%130 & 10$^{17}$ & 10$^{10}$ \\
%300 & 10$^{24}$ & 10$^{11}$ \\
%600 & 10$^{33}$ & 10$^{12}$ \\
%\hline
%\end{tabular}
%\end{center}
%
%\end{slide}


\begin{slide}
{\large Practical implications}
\\ \\
Security on the Internet is based on public key cryptography.
\\ \\
The most widely used (and most trusted) public key cryptosystems 
are based on the difficulty of factoring and of
finding discrete logarithms.
\\ \\
Both of these are vulnerable to attacks by a quantum computer.
\end{slide}

\begin{slide}
What are the fundamental physical principles on which a quantum
computer operates?
\begin{itemize}
\item
The superposition principle
\item
High dimensionality of quantum state spaces
\item
Quantum interference
\item
Quantum entanglement
\end{itemize}
\end{slide}

%\begin{slide}
%\begin{center}
%{\Large
%The Superposition Principle:
%}
%\end{center}
%If a quantum system can be in one of two mutually distinguishable
%states ${\ket{ A}}$ and $\ket{ B}$, it can be both these states at once.
%Namely, it can be in the {\em superposition} of states
%\vspace{-1ex}
%\[
%\alpha \ket{ A} + \beta \ket{ B}
%\] 
%\vspace{-1ex}where $\mathbf \alpha$ and $\mathbf \beta$ are complex
%numbers and $|{\alpha}|^2 + |{\beta}|^2 = 1$.

%\vspace{1ex}
%If you look at the system, the chance of seeing it in state $\ket{ A}$
%is $|{\alpha}|^2$ and in state $\ket{ B}$ is $|\beta|^2$.
%\end{slide}

%\begin{slide}
%{\large The Superposition Principle (in mathematics)}\\ \\
%Quantum states are represented by unit vectors in a complex vector 
%space.  

%Multiplying a quantum states by a unit complex phase does not change
%the essential quantum state.

%Two quantum states are {\em distinguishable} if they are represented
%by orthogonal vectors. 
%\end{slide}

%\begin{slide}
%A {\em qubit} is a quantum system with $2$ distinguishable states,
%i.e., a $2$-dimensional state space.

%If you have a polarized photon, there can only be two distinguishable states,
%for example, vertical $\ket{\vpols}$ and horizontal $\ket{\hpols}$ 
%polarizations.


%All other states can be made from these two.
%\[ \ket{\ppols} = \frac{1}{\sqrt{2}} \ket{ \hpols } + 
%\frac{1}{\sqrt{2}} \ket{ \vpols }
%\]
%\[ \ket{\qpols} = \frac{1}{\sqrt{2}} \ket{ \hpols} - 
%\frac{1}{\sqrt{2}} \ket{ \vpols }
%\]
%\[ 
%\ket{\rpols} = \frac{1}{\sqrt{2}} \ket{\hpols } + 
%\frac{i}{\sqrt{2}} \ket{ \vpols }
%\]
%\[ 
%\ket{\lpols} = \frac{1}{\sqrt{2}} \ket{ \hpols } - 
%\frac{i}{\sqrt{2}} \ket{\vpols }
%\]

%\end{slide}

%\begin{slide}
%If you have two qubits, they can be in any superposition of the four
%states \\*[2ex]
%\hspace*{.5in} $\ket{00}$ \quad $\ket{01}$ \quad $\ket{10}$ \quad $\ket{11}$
%\\*[2ex]
%This includes states such as an EPR (Einstein-Podolsky-Rosen) pair:
%\[\frac{1}{\sqrt{2}}(\ket{01} - \ket{10}),\] where neither qubit
%alone has a definite state.
%\end{slide}

%\begin{slide}
%If you have $n$ qubits, their joint state is described by a $2^n$
%dimensional vector.  \\*[2ex]
%The basis states of this vector space are:\\*[2ex]
%\hspace*{.25in} $\ket{000\ldots00}$ \quad $\ket{000\ldots01}$ \quad $\cdots$ \quad$\ket{111\ldots11}$
%\\*[2ex]
%The high dimensionality of this space 
%is one of the places where quantum computing obtains
%its power.
%\end{slide}

% \begin{slide}
% Quantum mechanics: Interference\\
% \\
% 
% The two-slit experiment.
% 
% \vspace{\fill}

% 
% \end{slide}

\begin{slide}
{\Large Models for quantum computation}

To compute, we need to
\begin{itemize}
\item Put the input into the computer. 
\item Change the state of the computer. 
\item Get the output out of the computer. 
\end{itemize}
\end{slide}

\begin{slide}
There are several mathematical
models for describing quantum computation.  
As is the case classically, they are all polynomially equivalent.
\begin{itemize}
\item Quantum circuit model (described below).
\item Quantum Turing machine.
\item Quantum cellular automata.
\item Quantum adiabatic computing.
\item Modular functors.
\item Braiding of anyons in topological quantum field theories.
\end{itemize}
\end{slide}

\begin{slide}
{\Large Input} {\small (for quantum circuit model)}

Start the computer in the state corresponding to the input
in binary, e.g.
\[\ket{100101101}.\] \\ \\
We may need extra workspace for the algorithm.  We then need to
add $0$s to the starting configuration.  
\[\ket{100101101} \otimes \ket{0000000000}.\] 
\end{slide}

\begin{slide}
{\Large Output} {\small (for quantum circuit model)}
At the end of the computation, the computer is in some state
\[
\sum_{i=0}^{2^k-1} \alpha_i \ket{i}
\]
We can NOT measure the state completely, because of the Heisenberg 
uncertainty principle. \\ \\
We assume that we measure in the canonical basis.  We observe 
the output $i$ with probability $|\alpha_i|^2$.
\end{slide}

\begin{slide}
{\Large Output}

When we observe the computer, we get a sample from a probability 
distribution.

Because of quantum mechanics, this is inherently 
a probabilistic process.  We say
that the computer computes a function correctly if we are 
able to get output that gives us the right answer with high probability.
\end{slide}

%\begin{slide}
%{\large The Linearity Principle}\\ \\
%The evolution of an {\em isolated} quantum system is linear. \\ \\
%Evolution of pure states in an isolated quantum system can be described
%by a matrix operating on the state space. \\ \\
%To preserve probabilities, the matrices must be unitary.
%\end{slide}

\begin{slide}
{\Large Computation} {\small (in quantum circuit model)}

Apply transformations to qubits two at a time.
\epsfxsize=2in
\begin{center}
\epsfbox{fig1.eps}
\end{center}
By linearity of quantum mechanics, a one-qubit gate is a $2\times2$
unitary matrix and a two-qubit gate is a $4\times 4$ unitary matrix.
\end{slide}
\begin{slide}
\vspace{-1in}
{\normalsize
A computation (program) is a sequence of quantum gates applied to
one or two qubits at a time.}

Why two?\\
Three doesn't give any more power, and seems more complicated
experimentally.  \\
Arbitrary many-qubit gates are hopeless, and theoretically realizable 
ones don't seem to add any extra computational power.
\end{slide}

\begin{slide}
A quantum gate is thus a linear transformation on a 2-dimensional (1-qubit)
or 4-dimensional (2-qubit) vector space.

It is thus a $2 \times 2$ or $4 \times 4$ matrix.

In order to preserve probabilities, it must take unit vectors to unit
vectors.  This means the matrix is {\em unitary}.  That is, if $G$ is
the gate, $G^\dag = G^{-1}$.
\end{slide}

\begin{slide}
As in classical computing, you only need a finite set of quantum
gates to perform arbitrary computation.  

These gates will not let you simulate computations with an 
arbitrary set of gates exactly, but will let you approximate them
arbitrarily closely.
\end{slide}
% \begin{slide}
% {\large Interference}\\
% Because superpositions of states can have complex coefficients
% (including both positive and negative coefficients), you can make 
% qubits interfere destructively with themselves.
% 
% Applying the transformation
% \begin{eqnarray}
% \mathbf{0} & \rightarrow &\frac{1}{\sqrt{2}}(\mathbf{0}+\mathbf{1}) \nonumber\\
% \mathbf{1} & \rightarrow &\frac{1}{\sqrt{2}}(\mathbf{1}-\mathbf{0}) \nonumber
% \end{eqnarray}
% twice takes 
% $\mathbf{0} \rightarrow \mathbf{1}$ and
% $\mathbf{1} \rightarrow - \mathbf{0}$, since the $\mathbf{0}$ terms
% in the result cancel out. \\ \\
% Without interference, a quantum computer can be simulated by a digital
% computer with a random number generator.
% \end{slide}

% \begin{slide}
% \begin{center}
% {\large Entanglement}
% \end{center}
% 
% You can have a system of quantum objects, such that
% \begin{itemize}
% \item
% each object has no definite state,
% \item
% the whole system has a definite state.
% \end{itemize}

% Quantum objects with this property are called
% {\em entangled}.\\ 
% 
% For example, the two qubits in the state
% \[\frac{1}{\sqrt{2}}(\ket{01} - \ket{10})\] 
% are entangled.  This is an EPR pair of qubits. 
% \end{slide}

% \begin{slide}
% 
% Entanglement is the property that makes quantum interference and the 
% high dimensionality of quantum systems work together for quantum computing. 
% \\ \\
% 
% There are classical systems, such as waves, with interference and
% high dimensionality.  These cannot perform quantum computing. 
% 
% 
% \end{slide}

\begin{slide}
How can you use quantum mechanical systems for computing?
\\
\\
You
need $2^{k}$ numbers to describe the state of $k$ quantum bits.
\\
\\
The Heisenberg uncertainty principle says you cannot measure the
complete state of a quantum system.
\\
\\
It turns out you can only get $k$ classical bits of information
out of $k$ quantum bits.  \\
Therefore, does not increase the capacity of information storage.
\end{slide}

\begin{slide}
Idea behind fast quantum computer algorithms:

Arrange the algorithm to make 
all the computational paths that produce the wrong answer destructively
interfere, and the computational paths that produce the right answer
constructively interfere, so as to greatly increase the probability 
of obtaining the right answer.
\end{slide}

\begin{slide}
{\large Simon's Problem}\\
Given a function $f$ mapping strings of length $n$ to strings of
length $n$, such that $f$ is 2 to 1, and 
\[
\exists c \mbox{\ such that\ }f(x) = f(x \oplus c) \forall x
\]
Find $c$.

Classically, if $f$ is a random such function, you have to query
values of $f$ until you have two such that $f(a) = f(b)$.  Then,
\[
c = a \oplus b.
\]
This takes on average $\approx 2^{n/2}$ queries.
\end{slide}

\begin{slide}
Hadamard gate
\[
H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc}1&1\\1&-1\end{array}\right)
\]
The amplitude for going from $\ket{a}$ to $\ket{b}$ [by this I mean the
matrix element $M_{ba}$] is
$(-1)^{ab}\frac{1}{\sqrt{2}}$.\\
The tensor product of $n$ Hadamard gates gives an amplitude going
from $\ket{a}$ to $\ket{b}$ of $(-1)^{a \cdot b}2^{-{n/2}}$, where $a$ and $b$
are binary strings of length $n$.

Thus,
\[
H^{\otimes n} \ket{a} = \frac{1}{2^{n/2}} \sum_{k=0}^{2^{n}-1} 
(-1)^{a\cdot b}\ket{b}
\]
\end{slide}


\begin{slide}
{\large Simon's Algorithm:}\quad
Start with 
\[
2^{-n/2}\sum_{k=0}^{2^n-1} \ket{k}\ket{0}
\]
Compute $\ket{f(k)}$ in second register
\[
2^{-n/2}\sum_{k=0}^{2^n-1} \ket{k} \ket{f(k)}
\]
Take Hadamard transform of first register
\[
2^{-n}\sum_{k=0}^{2^n-1} \sum_{l=0}^{2^n-1} (-1)^{k\cdot l} \ket{l} \ket{f(k)}
\]
Observe state.
\end{slide}
\begin{slide}
We had state
\[
2^{-n}\sum_{k=0}^{2^n-1} \sum_{l=0}^{2^n-1} (-1)^{k\cdot l} \ket{l} \ket{f(k)}
\]
A particular value of $f(k)$ will come from both $k$ and $k \oplus c$.  
The chance you observe a particular value $\ket{l}\ket{f(k})$ is
\[
2^{-2n} \left((-1)^{k \cdot l} + (-1)^{(k+c) \cdot l}\right)^2
\]
This is 0 unless $c \cdot l = 0$.  Thus, the algorithm returns only values
of $l$ that are perpendicular to $c$, and it returns a random such value.  
If you have $n-1$ such values
of $l$, you can uniquely identify $c$. 

This takes $O(n)$ queries, and $O(n^2)$ non-query steps.
\end{slide}
\begin{slide}
\begin{center}
{\Large Idea Behind All Fast Factoring Algorithms}
\end{center}
To factor a large number $N$,
Find numbers $a$ and $b$ so that
\[
a^2 = b^2 \mathrm{~~~mod~N}
\]
\[
a \neq \pm b \mathrm{~~~mod~N}
\]
Then
\[
a^2 - b^2 = (a+b) (a-b) = c N
\]
We now extract one factor from $a+b$ and another from $a-b$.\\
\end{slide}

\begin{slide}
\begin{center}
{\Large Example: Factoring 33}
\end{center}
Take the numbers $a=7$ and $b=4$.  Then 49 divided by 33 has remainder 16,
so
\[
7^2 = 4^2 \mathrm{~~~mod~33}
\]
Then
\[
7^2 - 4^2 = (7+4) (7-4) = 33
\]
and we find $33 = 3 * 11$.
\end{slide}


\begin{slide}
\begin{center}
{\Large Quantum Factoring Idea}
\end{center}
To factor a large number $N$:\\*[2ex]
Find the smallest $r>0$ such that  $x^r \equiv 1$ (mod $N$).\\*[1ex]
\hspace*{.4in}$(x^{r/2} + 1) ( x^{r/2} -1) \equiv 0$ (mod $N$).\\*[2ex]
We now get two factors by taking the greatest common divisors\\*[1ex]
\hspace*{.4in} gcd($x^{r/2} + 1$, $N$)\\*[2ex]
\hspace*{.4in} gcd($x^{r/2} - 1$, $N$)
\\ \\
We can show this gives a non-trivial factor for at least half of 
the residues $x ({\mathrm{mod}}\ N)$.
\end{slide}

\begin{slide}
How do we find $r$ with
\[
x^r \equiv 1  \ \ ({\mathrm{mod}}\ N)?
\]
Find the period $r$ of the sequence $x^a$ (mod $N$).\\*[2ex]
\end{slide}
\begin{slide}
\begin{center}
{\Large Example: Factoring 33}
\end{center}
Take $x=5$.  Then (mod 33) we get

{
\normalsize
\[
\begin{array}{cccccccccccc}
1 & 5 & 5^2 & 5^3 & 5^4 & 5^5 & 5^6 & 5^7 & 5^8 & 5^9 & 5^{10} & 5^{11}\\
1 & 5 &  25 &  26 &  31 &  23 &  16 &  14 &   4 &  20 &      1 &  5
\end{array}
\]

}
The period $r$ is 10, and
\[
x^{r/2} = 5^5 = 23 \mathrm{~~~mod~33}.
\]
Then
\[
33 {\mathrm{\ divides \ }} (23+1)(23-1) = 24*22 
\]
Taking greatest common divisors, 24 gives us the factor 3, 
and 22 gives us the factor 11, 
and we find $33 = 3 * 11$.
\end{slide}

\begin{slide}
Need to find the period of $x^a$ (mod $N$).\\*[2ex]
Idea: Use the Fourier transform\\*[2ex]
Problem: The sequence has an exponentially long period\\*[2ex]
Solution: Use the exponentially large state space of a quantum computer
to take an exponentially large Fourier transform efficiently.
\end{slide}



\begin{slide}
Factoring $L$-bit numbers

We will work with quantum superpositions of two registers
\[
\begin{array}{cc}
\mathrm{Register\ 1}&
\mathrm{Register\ 2}\\
2L \ {\mathrm{bits}}&
\phantom{2}L \ {\mathrm{bits}}
\end{array}
\]

We will not give the fine details of the algorithms.

These involve more workspace\\ ($3L$ is easy, $o(L)$ is possible).
\end{slide}

\begin{slide}
Quantum Fourier Transform over $Z_{2^k}$

Have $k$ qubits

\[
\ket{x} \rightarrow \frac{1}{2^{k/2}} \sum_{y=0}^{2^k-1} 
\exp ( \frac{2 \pi i x y}{2^k} )  \ket{y}
\]

This is easily seen to be a unitary transformation on the $2^k$-dimensional
space of $k$ qubits.  

In order to implement this on a quantum computer, we need to break this 
into a series of 2-qubit gates.

The Cooley-Tukey FFT easily adapts to give $O(k^2)$ steps.
\end{slide}

\begin{slide}
\begin{center}
{\large Reversible Computation}
\end{center}
We can do classical computations on a quantum computer as long as
we can do these classical computations {\em reversibly}.  That is,
with gates each of whose possible outputs maps uniquely back to the 
inputs.

Any classical computation can be made reversible as long as we 
keep the input around.

The 3-bit {\em Toffoli gate} is a universal gate for reversible
computation
\[
\Big(x, y, z\Big) \rightarrow \Big(x, y, z \oplus (x \wedge y)
\Big)
\]

This Toffoli gate can be implemented as a sequence of 2-qubit quantum
gates.
\end{slide}

\begin{slide}
$
\displaystyle \ket{0} \ket{0}
$

$
\quad \quad \downarrow \quad \approx L {\mathrm{\ steps}}
$

$
\displaystyle \frac{1}{2^L} \sum_{a=0}^{2^L} \ket{a} \ket{0}
$

$
\quad \quad \downarrow \quad \approx L^2 \log L \log \log L {\mathrm{\ steps}}
$

$
\displaystyle \frac{1}{2^L} \sum_{a=0}^{2^L} \ket{a} \ket{x^a\ ({\mathrm{mod\ }}N) }
$

$
\quad \quad \downarrow \quad \approx L^2 {\mathrm{\ steps}}
$

$
\displaystyle \frac{1}{2^L} \sum_{a=0}^{2^L} \sum_{c=0}^{2^L} 
\ket{c} \ket{x^a\ ({\mathrm{mod\ }}N)} \ e^{2 \pi i a c / 2^{2L}}
$

Observe computer.
\end{slide}

\begin{slide}
We need to find the probability amplitude on
\[
\ket{c} \ket{x^a\ ({\mathrm{mod\ }}N)} 
\]
in the superposition
\[
\frac{1}{2^L} \sum_{a=0}^{2^L} \sum_{c=0}^{2^L} 
\ket{c} \ket{x^a\ ({\mathrm{mod\ }}N)} \ e^{2 \pi i a c / 2^{2L}}
\]
Many different values of $a$ give the same value of 
$x^a \ (\mathrm{mod}\ N)$.

We have to add the coefficients $e^{2 \pi i a c / 2^{2L}}$ on
all of them.
\end{slide}

\begin{slide}
Let $a_0$ be the smallest non-negative integer such that
\[
x^{a_0} \equiv x^a (\mathrm{mod}\ N).
\]
Then $x^{a_0}$, $x^{a_0+r}$, $x^{a_0+2r}$,  ... are all equal
(mod $N$).

Each contributes to the amplitude on 
\[
\ket{c} \ket{x^a\ ({\mathrm{mod\ }}N)} 
\]
with the coefficient $e^{2 \pi i (a_0 + br) c / 2^{2L}}$.

We observe $\ket{c}$ with probability proporitional to
\[
\left|
\sum_{b = 0}^{\approx 2^{2L/r}}
e^{2 \pi i b r c / 2^{2L}}
\right|^2
\]

This is a geometric sum which is close to 0 unless,
for some integer~$d$.
\[
\frac{rc}{2^{2L}} = d + O(r/2^{2L})
\]
\end{slide}

\begin{slide}
We know 
\[
\frac{rc}{2^{2L}} = d + O(r/2^{2L}).
\]
Thus
\[
\frac{c}{2^{2L}} = \frac{d}{r} + O\left(\frac{1}{N^2}\right).
\]
with $r < N$.

$\frac{d}{r}$ will be one of the closest fractions to
$\frac{c}{2^{2L}}$ with numerator and denominator less than $N$.

We can use continued fractions to find $\frac{d}{r}$, and then use
$r$ to factor $N$.
\end{slide}

\begin{slide}
\epsfxsize=3in
\begin{center}
~\epsfbox{bigplot.eps}~~\\*[-1ex]
{\Large Example: Factoring 33}
\end{center}
The period $r$ is 10.
\end{slide}

\begin{slide}
{\large Proposals for building quantum computers:}
\begin{itemize}
% \item
% Cavity QED (quantum electrodynamics)
\item
Ion traps \\
(Cirac and Zoller, 1995)
\item
NMR (nuclear magnetic resonance)\\
(Cory et al., Gershenfeld et al., 1997)
\item
Nuclear spins on silicon chips\\ (Kane, 1998)
\item
Superconducting states on silicon chips \\ (Devoret, 2002)

\end{itemize}
\end{slide}


%\begin{slide}
%
%{\large Difficulties of Quantum Computing}
%\\
%\\
%Quantum states are notoriously hard to manipulate.
%\\
%\\
%To do $10^{10}$ steps on a quantum computer without error correction,
%and still come up with the right answer,
%you would need to perform each step with accuracy one part in~$10^{10}$. 
%
%\end{slide}
%
%\begin{slide}
%The same objection was raised to scaling up classical computers in the
%1950's.  \\*[2ex]
%Von Neumann showed that you could build reliable classical computers
%out of unreliable classical components. \\*[2ex]
%Currently, we don't use many of these techniques because we have
%extremely reliable integrated circuits, so we don't need them.
%\end{slide}
%
%\begin{slide}
%\begin{center}
%Main techniques for fault-tolerance \\
%on classical computers.
%\end{center}
%
%\begin{itemize}
%\item Consistency Checks
%\item Checkpointing
%\item Error-Correcting Codes
%\item Massive Redundancy
%\end{itemize}
%\end{slide}
%
%\begin{slide}
%\begin{center}
%{\Large Quantum Computing Difficulties}
%\end{center}
%\vspace{1ex}
%
%{\Large Heisenberg Uncertainty Principle:} \\
%You cannot measure a quantum state without changing it.
%
%{\Large No-Cloning Theorem:} \\
%You cannot duplicate an unknown quantum state.
%\end{slide}
% 
%\begin{slide}
%Can you use these techniques on a quantum computer?
%\\ \\
%\begin{itemize}
%\item Consistency Checks\\
%Doesn't get you very far on either classical or quantum computers.
%\item Checkpointing\\
%Cannot use on a quantum computer.
%\item Error-Correcting Codes\\
%Works well quantum mechanically.
%\item Massive Redundancy
%Does not work well quantum mechanically; need to use error-correcting
%codes instead.
%\end{itemize}
%\end{slide}
%
%\begin{slide}
%{\Large Quantum error correction}
%\\
%\\
%Quantum error correcting codes exist.\\
%\\
%\\
%They can be used to make quantum computers fault-tolerant.
%so that you only need to perform each step with 
%accuracy approximately one part in~$10^4$.
%\end{slide}

%\begin{slide}
%How do quantum error-correcting codes get around the no-cloning theorem
%Heisenberg uncertainty principle?\\*[2ex]
%Measuring one of the qubits gives NO information about the
%encoded state, so the remaining qubits can retain all the information
%about the encoded state without violating the non-cloning theorem.\\*[2ex]
%We design the codes so that we can measure the error without
%measuring (or disturbing) the encoded state. \\*[2ex]
%This means that all likely errors are {\em orthogonal} to the
%encoded data\\*[2ex]
%We can then fix the error without destroying the encoded data.
%
%\end{slide}

%\begin{slide}
%\begin{center}
%Fault Tolerant Computing\\*[1.5ex]
%\normalsize Classically:\\*[.2ex]
%\epsfxsize=3in
%~\epsfbox{fig2.eps}~\\*[.75ex]
%Quantum Mechanically:\\*[.2ex]
%\epsfxsize=3in
%~\epsfbox{fig3.eps}~
%\end{center}
%\end{slide}

\begin{slide}

{\large NMR Proposal for Quantum Computers}
\\
\\
The qubits are the spins of the nuclei of atoms in a large molecule.
\\
\\
These can be manipulated using standard NMR (Nuclear Magnetic Resonance)
techniques.
\\
\\
The computing is done with $10^{20}$ computers (molecules)
all at once, all doing the same computation.

\end{slide}

\begin{slide}

{\large Difficulty with NMR Proposal}
\\
\\
Currently, NMR quantum computers are initialized by using a thermal 
state.  The computer is put it in its initial state by using the fact 
that in a strong magnetic field, very slightly more of the nuclear spins 
are pointing down.
\\ 
\\
This initialization method means that the signal strength goes down
by a factor of two each time you add a qubit.  This method will 
break down somewhere between 10 and 20 qubits.
To improve this, you need some good way of cooling these nuclear spins, 
so most are
pointing in the same direction.
\\ 
\\
Similarly, to correct errors during computation,  you need some way
of getting the incorrect qubits out of the system.  This essentially 
requires cooling some nuclear spins during the computation.

\end{slide}

\begin{slide}
{\large Ion Trap Proposal for Quantum Computers}
\\
\\
Experimentalists can use electromagnetic fields to trap a line of 
ions in a low-temperature vacuum.
\[
{\rm Be}^+\ \ {\rm Be}^+\ \ {\rm Be}^+\ \ {\rm Be}^+\ \ {\rm Be}^+\ \ 
{\rm Be}^+
\]
\end{slide}

\begin{slide}
Proposal: Use the ground state and an excited state of the ions for
qubits in a quantum computer.
\\
The ions should be far enough apart so you can manipulate their states by
shining laser pulses on individual ions.  This lets you do one-qubit gates.
\end{slide}

\begin{slide}
The ions can be made to interact, giving two-qubit gates,
by using a shared vibrational mode 
of the trap.
\\
\[ \longrightarrow  \ \ \ \ \ \ \ \ 
\longrightarrow  \ \ \ \ \ \ \ \ \longrightarrow
\]
\[
{\rm Be}^+\ \ {\rm Be}^+\ \ {\rm Be}^+\ \ {\rm Be}^+\ \ {\rm Be}^+\ \ 
{\rm Be}^+
\]
\[ \longleftarrow  \ \ \ \ \ \ \ \ 
\longleftarrow  \ \ \ \ \ \ \ \ \longleftarrow
\]
\\

\end{slide}

\begin{slide}
Difficulty with ion trap proposal:\\*[2ex]
It is very difficult to make ion traps do what you want.\\*[2ex]
So far, at NIST, David Wineland has managed to put an ion trap 
containing four ions into the ground state, and do a few computations.

\end{slide}

\begin{slide}
\begin{center}
{\large
Conclusions
}
\end{center}

\begin{itemize}
\item
Quantum computers have the potential for enormous speed-up of certain
problems.
\item
Need good new idea to build large (100- to 1000- qubit)
quantum computers.
\item
Good new ideas appear to be coming regularly.
\end{itemize}

\end{slide}


\end{document}