\documentstyle[a4wide,11pt]{article}
\title{\Huge {\bf Quantum computing, and why it's exciting!}}
\author{Iain Stewart, Dept. of Computing, Imperial College,
	London SW7 2AZ, U.K.}
\date{Tuesday 28th July 2009 \\
	{\em (with some post-talk corrections and improvements)}}
\begin{document}
\maketitle
{\Large


\newpage
\begin{center}
\section*{\LARGE Quick summary - how to decide whether quantum computing
					is for you!}
\end{center}
\begin{itemize}
\item
If you're interested in {\bf speed}...
	\begin{itemize}
	\item
	you should be ``cautiously interested" in quantum computing
	\item
	it speeds up {\em a select few} things enormously over the
	``state of the art"...
	\item
	...but {\em most} general-purpose computing tasks apparently get
	little, if any, speedup - you have to ``strike lucky"
	\end{itemize}
\item
If you're interested in {\bf cryptography}...
	\begin{itemize}
        \item
	you should ``unfortunately"(!) feel obliged to keep an eye on
	quantum computing
	\item
	it {\em ruins} large swathes of classical cryptography...
	\item
	but then {\em offers} ``quantum cryptography" as a partial replacement!
	\end{itemize}
\item
If you're interested in {\bf modelling physical systems}...
	\begin{itemize}
        \item
	quantum computing has fascinating potential for modelling
	\item
	time and again, modellers have to ``cheat" with the quantum aspects
	of what they're modelling
	\item
	quantum computing offers the chance to be honest with those aspects
		\begin{itemize}
        	\item
		to get them {\em right} for our actual world; and
		\item
		even to explore the impact of {\em different parameters}
		(particle charges, mass ratios, etc.) than those of our world!
		\end{itemize}
	\end{itemize}
\item
If you're interested in {\bf distributed ``grid computing"}...
%
%	(page-break here with chosen font size - might change with other...)
%
\end{itemize}
\newpage
\section*{\LARGE {\em Quick summary, cont'd.}}
\begin{itemize}
%
%	(OK, back to more items...)
%
\item
If you're interested in {\bf distributed ``grid computing"}...
	\begin{itemize}
        \item
	you should suddenly be {\em very} interested in quantum computing!
	\item
	some recent developments may have great potential for grid computing
	\item
	a ``quantum grid" will, it seems, allow {\em perfect obfuscation}
	of what data - and even what algorithm! - one grid user (Alice)
	is asking another (Bob) to handle on her behalf
		\begin{itemize}
        	\item
		even {\em Bob} can't tell what Alice's requests ``really mean"!
		\end{itemize}
	\item
	thus, whole new communities (users with highly sensitive or private
	data and/or tasks) might learn to stop worrying and love the grid!
	\end{itemize}
\end{itemize}


\newpage
\section*{\LARGE Why is there such a thing as ``quantum computing" anyway?}
\begin{itemize}
\item
Take a subsystem of the world, put it in a box (even just in your imagination!),
and call it a ``computer"
\item
What can it compute?
\item
Answer: whatever {\bf physics} permits it to compute!
\item
The various ``classical" computing models
 - the Turing machine, the cellular automaton, etc. -
make implicit assumptions about what the stuff of our world can do
	\begin{itemize}
        \item
	a read/write head can move around and view/change a strip of tape
		- that sort of thing
	\end{itemize}
\item
But the stuff of our actual, quantum world can do {\em more!}
	\begin{itemize}
        \item
	it can go into a ``superposition" of states, {\em each} of which can be
	something like a classical state of {\em the whole machine}
	\item
	it can become ``entangled" with other stuff far away,
	such that no classical ``pre-agreement" instructions
	(``in circumstances X, you do this, and I'll do that...")
	can mimic {\em what the distributed entangled stuff actually does}
	\end{itemize}
\item
Quantum computing is what you get when you ask ``what can I compute with
stuff which has such extra capability?"
	\begin{itemize}
        \item
	and of course, how fast, with what resource usage, etc.
	\end{itemize}
\end{itemize}


\newpage
\section*{\LARGE General-purpose computing - some limited speedup possible}
\begin{itemize}
\item
For the specialised computations of {\em cryptography} and
{\em modelling physical systems}, quantum computing can offer huge speedups
 - more about those cases later
\item
But what about general-purpose computing?
\item
A large fraction of today's computing power goes on Knuth's two S's:
{\em sorting} and {\em searching}
\item
Quantum computing so far offers no speedup for {\em sorting}...
\item
...but {\bf Lov Grover} discovered around 1996 that quantum {\em searching}
through $N$ items can be done in $\sqrt{N}$ time!
\item
The small print:
	\begin{itemize}
	\item
	the entire database being searched has to be stored in quantum memory
	\item
	the ``time" expression above refers to {\em abstract sequential steps}
	\item
	it seems likely a quantum machine's ``clock cycle" will,
	at least initially, be slower than mature classical technology
	\end{itemize}
\item
Even so: a database with 1,000,000,000 items can be searched 30,000 times
``logically faster" - so even with a clock cycle 1,000 times {\em slower},
that's 30 times faster in real time!
\item
Grover's search algorithm also works for search through
{\em candidate solutions} to an optimisation problem or the like
	\begin{itemize}
	\item
	...and it only needs whatever quantum memory the act of testing
	{\em one} candidate solution requires!
	\end{itemize}
\item
Thus optimal paths, circuits etc. can be found in roughly the square root
of the classical time
(for example, taking 1,000,000,000 quantum steps to search through
1,000,000,000,000,000,000 candidate solutions)
\item
This is {\bf not} a reduction from exponential to polynomial...
\item
...but it may still be of value in many particular cases!
\end{itemize}


\newpage
\section*{\LARGE Cryptography - a death... and an awkward rebirth?}
\begin{itemize}
\item
Much of today's (classical) cryptography depends on making an adversary's
cracking efforts {\em too hard} to be practical
\item
The RSA public-key protocol, and various tweaks thereof, depend on a
number theorist's old favourite classically hard task -
{\em finding the factors} of a large integer
\item
{\bf Peter Shor} discovered around 1993 that {\em factoring is easy}
on a quantum computer!
        \begin{itemize}
        \item
	polynomial time, compared with somewhat less than exponential time
	for the best currently known classical algorithm
	\end{itemize}
\item
Thus, if quantum computing becomes cheap and ubiquitous,
much of classical cryptography will be ruined
\item
{\em Quantum} cryptography - designed to be unbreakable even if an
eavesdropper or other adversary has access to quantum computing power -
does exist as a partial replacement
\item
It is, however, more generally cumbersome than classical cryptography
        \begin{itemize}
        \item
	resources such as keys can't just be published and then used by
	any number of counterparties...
	\item
	...they need to be created, exchanged and consumed for each usage
	(just like classical one-time pad cryptography)
	\end{itemize}
\item
So cryptography will still be {\em possible} in a ubiquitous quantum computing
setting...
\item
...but not quite as {\em user-friendly} as the cryptography we know today!
\end{itemize}


\newpage
\section*{\LARGE Simulating the world}
\begin{itemize}
\item
Probably the single most inspiring {\em scientific} usage of computing power
has been {\bf simulation}
\item
But there's a problem, which modellers have brushed under the carpet
\item
The quantum ``stuff" of our world can casually go into vast, sprawling
superpositions of states, which can interfere and entangle with each other
in rich and complex ways
\item
The only known {\em fully honest} way a {\em classical} computer can mimic this
is to wade through an exponential explosion of ``versions"
of the system being modelled
\item
This is hopeless for all but the tiniest quantum systems
\item
Time and again, modellers have to ``cheat" with the quantum aspects
of what they're modelling - they may for example notice some regularity in
the way superpositions behave, which they hope(!) scales to larger systems
	\begin{itemize}
        \item
	For example, in {\em ab initio} chemistry, approximations such as
	{\em atomic and molecular orbitals} have become so useful that
	many people - even some textbook writers! - have forgotten that
	{\em they don't actually exist} in a true many-electron solution!
	\end{itemize}
\item
By ``hacking" a classically computed scaled version of a purported regularity
into a simulation, modellers can achieve tolerable accuracy in many cases...
\item
...but at the cost of no longer honestly tracking what the system is doing
in its own, quantum terms
%
%	(page-break here with chosen font size - might change with other...)
%
\end{itemize}
\newpage
\section*{\LARGE {\em Simulating the world, cont'd.}}
\begin{itemize}
%
%	(OK, back to more items...)
%
\item
Quantum computing has fascinating potential for modelling
\item
At least for many Hamiltonians (prescriptions for time evolution),
a quantum computer will be able to keep up with the system being modelled
	\begin{itemize}
        \item
	by sending {\em its own quantum stuff} into the same sort of
	sprawling superposition of ``versions" that so quickly overwhelms
	a classical machine
	\end{itemize}
\item
Such {\bf quantum simulation} will likely cut the run-time of many, many
simulation problems {\bf all the way from exponential time to polynomial!}
	\begin{itemize}
        \item
	chemical reactions - bond breaking and re-making in glorious detail
	\item
	exotic material properties - superconductivity, superfluidity, etc.
	\item
	some grand challenges for physics - quantum fields in the early universe
	(topological defects, etc) or other extreme environments
	\end{itemize}
\item
But there's more...
\item
...we can simulate things as they {\em could have been}, which history shows
often gives great insight into the way they actually are!
\end{itemize}


\newpage
\section*{\LARGE Simulating counterfactual worlds - ``journeys to elsewhy"}
\begin{itemize}
\item
Even with classical simulation, modellers enjoy varying things that our
actual world (or our actual corner of the world) holds constant,
or in advance of an anticipated change
	\begin{itemize}
        \item
	Fancy simulating the climate with a different atmosphere? a hotter sun?
	farms instead of rainforests intercepting the incoming sunlight?
	\item
	Fancy simulating planet formation with a different chemical cocktail
	than our actual early solar system?
	\item
	...and looking for planets elsewhere that resemble what you get?
	\end{itemize}
\item
With quantum simulation, more radical ``variant worlds" may become tractable
\item
Today's physics throws up ``constants" (particle charges, mass ratios, etc.)
stuck at certain values, with no clear reason {\em why} those values are special
\item
Simulations of {\em alternative versions} of those values may help clarify
whether and how our world's actual values ``stand out" in some sense
in the landscape of competing alternatives
\item
Modellers are used to taking simulated journeys to else{\em where} or
else{\em when} - ``what will the solar system be like a billion years from now?"
sort of thing
\item
Quantum simulation may offer us the scientific ride of a lifetime -
{\bf journeys to elsewhy!}
	\begin{itemize}
        \item
	some limited ``journeys to elsewhy" are possible even on
	classical hardware, but quantum simulation will likely
	greatly extend our range
	\end{itemize}
\item
It might be a while coming, but: {\bf Enjoy the ride!}
\end{itemize}


\newpage
\section*{\LARGE Distributed ``grid computing" - a possible quantum revolution!}
\begin{itemize}
\item
In recent years ``grids" of computers, large and small, have started to emerge
\item
Even at a hobby level, people are taking to offering spare CPU cycles
to help with various grand projects
	\begin{itemize}
        \item
	SETI@home - the search for extraterrestrial signals
	\item
	Einstein@Home - the search for gravity waves
	\item
	Folding@home - simulations of how proteins fold into precise shapes
	\end{itemize}
\item
The projects currently most successful in terms of sheer scale all have
one thing in common: {\bf non-sensitive data}
	\begin{itemize}
        \item
	typically data which has already been made public
	as part of the general scientific endeavour
	\end{itemize}
\item
But what about people wanting heavy crunching of {\bf sensitive} data?
	\begin{itemize}
        \item
	patient medical histories
	\item
	banking transactions, buy/sell orders in markets
	\item
	customer buying habits and preferences
	\end{itemize}
\item
Patterns hidden in such data could greatly help with medical progress
at one extreme of grandeur,
or just general market efficiency and responsiveness at the other
\item
The agencies sitting on such data typically don't want to acquire and manage
vast tracts of computer hardware themselves
\item
They'd love to farm out such interesting tasks to ``the grid"...
        \begin{itemize}
        \item
	...but they can't! the data is precious and confidential!
	\end{itemize}
\item
Encryption, sadly, is not the answer:
	\begin{itemize}
        \item
	Alice: ``if $x < y$..."
	\item
	Bob: ``Sorry, I can't help you there - you've encrypted $x$ and $y$!"
	\end{itemize}
%
%	(page-break here with chosen font size - might change with other...)
%
\end{itemize}
\newpage
\section*{\LARGE {\em Quantum grid computing, cont'd.}}
\begin{itemize}
%
%	(OK, back to more items...)
%
\item
People have looked into lighter forms of obfuscation than full encryption,
to let Bob do Alice's ``if $x < y$..." or whatever,
but (except in a few lucky cases like keyword search from a fixed repertoire)
obfuscation light enough to let serious data-crunching go ahead
is {\em so} light it's far too easy for Bob to figure out the sensitive data!
\item
{\bf QUANTUM COMPUTING TO THE RESCUE!}
\item
In 2008, {\bf Anne Broadbent}, {\bf Joseph Fitzsimons} and {\bf Elham Kashefi}
announced a quantum grid computing protocol they call
``universal blind quantum computation"
\item
With this protocol, if Alice hires Bob to perform a quantum computation
on her behalf, only Bob needs a quantum computer
 - Alice can get away with a classical machine
(to handle the required two-way data stream between her and Bob)
and some simple quantum hardware (single-bit preparation and transmission)
of the sort that exists today
\item
The level of obfuscation their protocol achieves is sensational:
	\begin{itemize}
        \item
	not only Alice's data but {\em even her algorithm} is completely
	cryptographically hidden from Bob
	\item
	Bob can make no sense of Alice's stream of either instructions or data,
	nor of any of the intermediate or final results
	he streams back to Alice,
	even if he uses further {\em quantum} computing power in his
	cracking efforts
	\item
	any eavesdroppers - whether in league with Bob or not - can likewise
	learn nothing of Alice's algorithm, data or results
	\end{itemize}
\item
If this still quite recent work stands up to scrutiny,
it may come to be heralded as the ``grid cleared for take-off" protocol
\item
Whole new communities - users with highly sensitive or private data
and/or tasks - might learn to {\bf stop worrying and love the grid!}
\end{itemize}


\newpage
\section*{\LARGE Waiting for quantum computing: the engineering challenge}
\begin{itemize}
\item
Will we see robust, reliable, scalable quantum computing any time soon?
\item
There are many candidate quantum architectures being explored,
but one in particular seems very hopeful for scalability and practicality:
{\bf measurement-based quantum computing}
\item
A traditional ``gate-based" quantum computation performs delicate
quantum operations all through its lifetime
\item
In 2000, {\bf Hans Briegel} and {\bf Robert Raussendorf} discovered a class of
quantum states - ``cluster" states - with some remarkable properties
\item
A cluster state acts as a {\em universal starting state}
for a new way of doing quantum computing
\item
You can be given a standard initial cluster state {\em before}
deciding what quantum algorithm you feel like running...
\item
...and you can then perform any quantum algorithm of your choice
by performing {\bf only measurements}
(these being much easier to perform than full quantum gate operations)
on the cluster state!
	\begin{itemize}
	\item
	you may of course use {\em classical} computing power
	 - your own brain, pencil and paper, any classical machine -
	to decide what measurements to perform next, given the outcomes so far
	\end{itemize}
\item
Cluster states of a few bits have been prepared - the race to create
decent-sized ones is on!
\item
There are many other proposed architectures, and many researchers are
much more optimistic about at least one of them succeeding
than was the case even a few years ago
\item
Thanks to the algorithms and protocols discussed earlier,
there will be {\em many} people cheering them on! {\bf WISH THEM LUCK!}
\item
{\bf Thank you!}
\end{itemize}


}	% end of \Large
\end{document}