Geometry of abstraction in quantum computation

Quantum algorithms are sequences of abstract operations, per­ formed on non-existent computers. They are in obvious need of categorical semantics. We present some steps in this direction, following earlier contribu­ tions of Abramsky, Goecke and Selinger. In particular, we analyze function abstraction in quantum computation, which turns out to characterize its clas­ sical interfaces. Intuitively, classical data can be recognized as just those data that can be manipulated using variables, i.e. copied, deleted, and abstracted over. A categorical framework of polynomial extensions provides a convenient language for specifying quantum algorithms, with a clearly distinguished clas­ sical fragment, familiar from functional programming. As a running example, we reconstruct Simon's algorithm, which is a sim­ ple predecessor of Shor's quantum algorithms for factoring and discrete loga­ rithms. The abstract specification in the framework of polynomial categories displays some of the fundamental program transformations involved in devel­ oping quantum algorithms, and points to the computational resources, whether quantum or classical, which are necessary for the various parts of the execution. The relevant resources are characterized as categorical structures. They are normally supported by the standard Hilbert space model of quantum mechan­ ics, but in some cases they can also be found in other, nonstandard models. We conclude the paper by sketching an implementation of Simon's algorithm using just abelian groups and relations.