THE ZOOLOGY OF QUANTUM COMPUTERS - QUANTUM AND CLASSICAL CONTROL
STRUCTURES, APPLIED TO QUANTUM AND CLASSICAL DATA
Peter Hines
Abstract
Although the computational power of quantum mechanics is generally
described as coming from the quantum phenomena of superposition and
entanglement, the interaction of quantum and classical systems is also
a feature of both algorithms and computational protocols.
An aim of this talk is to show that "a quantum computer" may mean many
things, according to the extent to which the control structures and
datasets are either classical or quantum. Possibilites range from a
classical computer that may also apply unitary transformations to a
quantum register followed by a final projection (the currently
favoured experimental model), to an isolated quantum system that
evolves according to a unitary operator (the Feynman computer).
Although the underlying computational complexity may (or may not) be
the same, each of these qualitatively different pictures has a
distinct set of advantages and disadvantages. The purely quantum case
is considered, in terms of the problems associated with iteration and
termination --- in particular, what has become known as the
'subroutine problem'.
A final observation, as part of ongoing work, is that some underlying
categorical structures of quantum mechanics are familiar from abstract
theoretical computer science (and vice versa). Examples are briefly
described, and the potential for unusual implementations of computing
systems is considered.