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 -