Categorical quantum computation
Paquette, Éric Oliver
Quantum computation is a sub-discipline of computer science that studies computation performed using quantum-mechanical phenomena such as entanglement and the principle of quantum superposition. The work presented in this dissertation is part of a program of research initiated by S. Abramsky and B. Coecke that aims to establish a categorical foundation for quantum computation.
The usual axiomatisation of quantum computation uses the biproduct structure to express the classical fragment of the theory that comprises, for instance, the result of a measurement or classical control. Following the work of S. Abramsky and B. Coecke, that of P. Selinger for the quantum aspect, and that of B. Coecke and D. Pavlovic for the classical aspect, we will introduce a complete categorical semantics for quantum computation that includes bath the classical and the quantum fragments of the theory. In order to do so, we will introduce the notion of classical-quantum interface, which is sufficiently general to include the two fragments of the theory. Moreover, the classical fragment will be axiomatised exclusively with respect to the tensorial structure, i.e., without using biproducts. In particular, such an approach enables the use of an intuitive and rigorous graphical calculus as a proof technique which is often easier to use than the usual algebraic techniques. Moreover, we will see that the axiomatisation of basis structures from which is derived the notion of classical transformation also enables the definition of many families of classical transformations such as relations, functions, bijections, and stochastic and bistochastic transformations; the latter three being especially suitable in the context of quantum computation. Finally, we will present some quantum protocols and prove some results concerning these, using a graphical calculus developed for the categorical semantics in order to illustrates the usefulness and the well-foundedness of the theory.
Key words: Quantum computation. Classical control. Category theory. Compact closed categories. †-monoidal categories. †-compact categories. Classical-quantum interfaces.
•Jan 1, 2008•7 citations