that classical probabilistic computers
cannot exploit: the only way to represent a group on a classical computer
is to represent it as by deterministic
permutation. But while a group can
be represented by unitary matrices, no
such representation is possible using
stochastic matrices. This, at its heart,
appears to be one of the key reasons
that quantum computers offer exponential benefits for some problems
over classical computers.
Given that Shor’s algorithm exploits
symmetry in such a successful way, it
is natural to search for other problems
that involve hidden symmetries. Following Shor’s discovery it was quickly
realized that almost all prior quantum
algorithms could be cast in a unifying
form as solving the hidden subgroup
problem for one group or the other.
For Shor’s algorithm the relevant group
is the group of addition modulo N.
For the discrete logarithm problem the
relevant group is the direct product
of the groups of addition modulo N.
Indeed it was soon discovered that
for all finite Abelian groups (Abelian
groups are those whose elements all
commute with each other) quantum
computers could efficiently solve the
hidden subgroup problem. A natural
follow-up question is: what about the
non-Abelian hidden subgroup problem? And, even more importantly,
would such an algorithm be useful for
any natural problems, as the Abelian
hidden subgroup problem is useful for
factoring?
One of the remarkable facts about
the problem of factoring is its inter-
mediate computational complexity.
Indeed, if one examines the decision
version of the factoring problem, one
finds that this is a problem which is in
the complexity class NP and in the com-
plexity class Co-NP. Because of this fact
it is thought to be highly unlikely that it
is NP-complete, since if it were, then the
polynomial hierarchy would collapse in
a way thought unlikely by complexity
theorists. On the other hand, there is
no known classical algorithm for fac-
toring. Thus factoring appears to be of
Goldilock’s complexity: not so hard as
to revolutionize our notion of tractabil-
ity by being NP-complete, but not so
easy as to admit efficient classical solu-
tion. There are, surprisingly, only a few
problems which appear to fit into this
category. Among them, however, are the
problems of graph isomorphism and
certain shortest-vector in a lattice prob-
lems. Might quantum computers help
at solving these problems efficiently?
simulating Quantum Physics
A final area in which quantum algorithms have made progress goes back
to the very roots of quantum computing
and indeed of classical computing itself.
From their earliest days, computers
have been put to use in simulating physics. Among the difficulties that were
table 1. some examples of integer solutions (x, y) to Pell’s equation x2 − dy2 = 1
for different values d.
Such solutions tell us what the units are of the number field Q[÷ ÷ `d] (the rational numbers extended
with the irrational ÷ ` ÷`d) and thereby solve the unit group problem. hallgren’s result shows how this
problem can be solved efficiently on a quantum computer, while no such algorithm is known for
classical computers.
d
2
3
5
.:
13
14
.:
6,009
x
3
2
9
y
2
1
4
649
15
180
4
6,013
.:
1,316,340, 106,327,253,158
9,259,446,951,059,947,388
4,013,975 » 1. 3 × 1044
40,929,908,599
1,698, 114,661,157,803,451
6,889,492,378,831,465,766
81,644 » 1. 6 × 1042