review articles
Doi: 10.1145/1646353.1646375
What quantum algorithms outperform
classical computation and how do they do it?
BY DAVe BAcon AnD Wim VAn DAm
Recent
Progress in
Quantum
Algorithms
it is impossible to imagine today’s technological
world without algorithms: sorting, searching,
calculating, and simulating are being used
everywhere to make our everyday lives better. But
what are the benefits of the more philosophical
endeavor of studying the notion of an algorithm
through the perspective of the physical laws of
the universe? This simple idea, that we desire
an understanding of the algorithm based upon
physics seems, upon first reflection, to be nothing
more than mere plumbing in the basement of
computer science. That is, until one realizes
that the pipes of the universe do not seem to
behave like the standard components out of
which we build a computer, but instead obey the
counterintuitive laws of quantum theory. And,
even more astoundingly, when one puts these
quantum parts together, one gets a
notion of the algorithm—the quantum algorithm—whose computational power appears to be fundamentally
more efficient at carrying out certain
tasks than algorithms written for
today’s, nonquantum, computers.
Could this possibly be true: that there
is a more fundamental notion of algorithmic efficiency for computers built
from quantum components? And, if
this is true, what exactly is the power
of these quantum algorithms?
The shot that rang round the computational world announcing the arrival
of the quantum algorithm was the 1994
discovery by Peter Shor that quantum
computers could efficiently factor natural numbers and compute discrete
logarithms. 24 The problem of finding
efficient algorithms for factoring has
been burning the brains of mathematicians at least as far back as Gauss
who commented upon the problem
that “the dignity of science seems to
demand that every aid to the solution
of such an elegant and celebrated
problem be zealously cultivated.” Even
more important than the fact that
such a simple and central problem has
eluded an efficient algorithmic solution is that the lack of such an efficient
algorithm has been used as a justification for the security of public key cryptosystems, like RSA encryption. 23 Shor’s
algorithm, then, didn’t just solve a
problem of pure academic interest, but
instead ended up showing how quantum computers could break the vast
majority of cryptographic protocols in
widespread use today. If we want the
content of our publicly key encrypted
messages to remain secret not only
now, but also in the future, then Shor’s
algorithm redefines the scope of our
confidence in computer security: we
communicate securely, today, given
that we cannot build a large scale
quantum computer tomorrow.
Given the encryption breaking powers promised by quantum computers, it was natural that, in the decade
following Shor’s discovery, research
has focused largely on whether a