Geometry of abstraction in quantum computation

Quantum algorithms are sequences of abstract operations, performed on non-existent computers. They are in obvious need of categorical semantics. We present some steps in this direction, following earlier contributions of Abramsky, Coecke and Selinger. In particular, we analyze function abstraction in quantum computation, which turns out to characterize its classical 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 classical fragment, familiar from functional programming.

As a running example, we reconstruct Simon's algorithm, which is a simple predecessor of Shor's famous algorithms for factoring and discrete logarithms. The abstract specification in the framework of polynomial categories displays some of the fundamental program transformations involved in quantum programming, 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 mechanics, 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.