TY - CHAP

T1 - Geometry of abstraction in quantum computation

AU - Pavlovic, Dusko

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Chapter

SN - 978-0-8218-4923-1

T3 - Proceedings of symposia in applied mathematics

SP - 233

EP - 267

BT - Mathematical foundations of information flow

A2 - Abramsky, Samson

A2 - Mislove, Michael

PB - American Mathematical Society

T2 - Clifford lectures on Information Flow in Physics, Geometry, Logic and Computation 2008

Y2 - 12 March 2008 through 15 March 2008

ER -