Beam me up Scotty, said the Qubit
---------------------------------

Supported by a grant from Curriculum Innovation, the Departments of
Computer Science, Physics, and Mathematics, are embarking on a novel
initiative in cooperative curriculum design, by offering a third year
course in Quantum Computing from the spring semester of 2003. The
very possibility of constructing such a course has grown out of
recent research, largely in physics. 

For the last fifteen years or so the potential for storing and
processing information using quantum theory has exercised the minds
of some talented physicists, among them the late Nobel Laureate
Richard Feynman. Using the extraordinary phenomena that characterise
the quantum domain as an information medium, introduces possibilities
undreamed of until a few short years ago. Computing was to change
for ever.

'Killer Apps' (to use the prefered jargon) are the things that
propel a branch of computer science to prominence. They are
applications in which as a result of advances in research, the
potential for a paradigm shift in the application domain becomes
selfevident. Henceforth the topic in question attracts intense
interest worldwide. Eliciting the relevant 'app' in the mid 90's
was what changed quantum computing from an esoteric backwater of
physics to a major new discipline.

Security of internet information transfers, especially with regard to
credit card numbers and similar sensitive data, was the 'app' in
question. The strength of the public key cryptosystems used over the
internet, the RSA cryptosystem in particular, depends on the presumed
intractability of factoring large numbers; and the internet is by
no means the only place where RSA is critical to system security.
Undermining the difficulty of factoring enormous numbers therefore
has the capacity to fatally weaken a significant proportion of
contemporary commercial activity. Dramatic work by Peter Shor at
Bell Labs in the mid 90's resulted in an algorithm for factoring,
which delivers an answer at a cost which grows roughly as the cube
of the size of the number to be factored, which is to be compared
with the overwhelmingly greater exponential cost of the best
classical techniques. 

Effectively this means that RSA remains secure, but only until a
serious quantum computer can be built. Not that a serious quantum
computer is in the offing at any time in the near future. The biggest
obstacle to constructing such a device is the difficulty of finding
quantum systems in nature that behave in the way that calculations
say ought to be possible. Sensitivity to disturbances by their
environment is one of the main characteristics of known quantum
systems, and reducing such effects so that the quantum phenomena
speak loud and clear remains a perennial headache for experimenters.

Thus the internet, and other application areas that depend for their
security on RSA, remain secure for the moment. However the financial
institutions now take a keen interest in developments in quantum
computing, and devote some attention to developing contingencies
in readiness for the day that quantum factorisation, and therefore
the demise of RSA, become reality. 

Security applications, while perhaps having the greatest potential
impact at the everyday level, do not give much of an inkling about
just how surprising the quantum domain can be. Other, more fundamental
and counterintuitive quantum phenomena include superposition, in which
a system can be in more than one state at the same time, something
which is inconceivable according to our normal intuitions about the
physical world. Despite the bizarre nature of superposition, it is a
key resource exploited in quantum computing.

Teleportation is another, even more astonishing possibility that quantum
theory admits. Having a particle dematerialise and reappear elsewhere is
the stuff of science fiction, but is theoretically possible, and the
underlying principles have been observed experimentally. Entanglement
is the key ingredient in this, a phenomenon in which the properties of
perhaps distant systems are inextricably entwined, so that affecting one
of them causes an instantaneous change in the other.

Computing with quantum phenomena tries to steal a march on what conventional
systems can do. In favourable situations, the information to be processed
and the answer to be obtained (both encoded using the quantum mechanical
analogue of the classical bit, the qubit), together with the strange
facilities offered by quantum physics, combine to strike at the heart
of the matter more efficiently than is possible classically. Undergraduates
will now have the opportunity to immerse themselves in this whirlwind
of new ideas as part of their degree.

Quantum computing as it is understood today is an eclectic melange of
concepts from physics, computation, and mathematics. Formulating the
quantum computing course so that it could sit comfortably in the
curricula of all three departments therefore seemed the most reasonable
way of proceeding.

The resulting course starts off by recalling the linear algebra required,
and by introducing the necessary quantum mechanics. Reviewing these basic
topics is vital preparation for what is to come. Ultimately this first
section concludes in a presentation of entanglement, nonlocality and
teleportation. Leading on from this introduction, there follows a reading
week where the different student constituencies can reinforce their knowledge
of the complementary subjects. 

Elaborating now the core of the course, Grover's efficient quantum search
algorithm is presented. Since this comes in two versions, a simple one when
one knows how many instances of the searched for item exist, and a more complex
one when one doesn't, after covering the simple case the technical issues
needed for the latter are examined. Estimating the phase of a quantum state
is one of the ingredients here. Proceeding towards quantum computing's killer
app, a number of other technical issues are dealt with, such as the quantum
Fourier Transform and continued fractions. Subsequently Shor's Algorithm can
be discussed in detail making for a fitting culmination to the course.

Realising that quantum computing comprises a number of areas, each offering
a range of technical challenges, meant making a selection of the topics to
be covered. Choosing some particular topic meant presenting both the topic
itself and the necessary background, which could be extensive. Since
course duration is limited, all of the fascinating possibilities could not
be included. Thus there was no room to incorporate the remarkable phemonena
pertaining to cryptography and truly secure communications that quantum
effects make possible, and that have been extensively verified experimentally.
Indeed, this area of the subject is now in transition from being a topic for
theoretical and laboratory speculation to becoming a technological reality.

Nonetheless, it is hoped that by creating a course that covers at least the
current killer app of the subject, a springboard for well motivated students
has been put in place. Knowing the impact that even this single application
could potentially have on peoples' lives, means that the last word on quantum
computing is very far from having been written. Students on the new course
might well end up contributing to future paragraphs of the story.

Dr. R. Banach
Computer Science Department
University of Manchester