Communications - February 2010

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.