Quantum Patterns and Types for Entanglement and Separability

As a first step toward a notion of quantum data structures, we introduce a typing system for reflecting entanglement and separability. This is presented in the context of classically controlled quantum computation where a classical program controls a sequence of quantum operations, i.e. unitary transformations and measurements acting on a quantum memory. Abstract models for such quantum computations are the Quantum Random Access Machine (QRAM [E. Knill, Conventions for Quantum Pseudocode, LANL report LAUR-96-2724, 1996]) and the Classically-Controlled Quantum Turing Machine (CQTM [S. Perdrix, Ph. Jorrand, Classically-Controlled Quantum Computation, arXiv:quant-ph/0407008, to appear in Mathematical Structures in Computer Science]). Several quantum programming languages follow this model [S. Bettelli, T. Calarco, L. Serafini, Toward an architecture for quantum programming, Eur. Phys. J. D 25 (2) (2003) 181–200, S.J. Gay, R. Nagarajan, Communicating quantum processes, Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Jens Palsberg and Martin Abadi (Eds.), POPL 2005, January 12–14, 2005, pp. 145–157, M. Lalire, Ph. Jorrand, A process algebraic approach to concurrent and distributed quantum computation: operational semantics, Proceedings of the 2nd International Workshop on Quantum Programming Languages, 2004, pp. 109–126, J.W. Sanders, P. Zuliani, Quantum Programming, Mathematics of Program Construction, Springer LNCS 1837, 80–99, 2000, P. Selinger, Towards a Quantum Programming Language, Mathematical Structures in Computer Science 14 (4) (2004) 527–586]. Among them, the functional language defined by Valiron [B. Valiron, Quantum Typing, Proceedings of the 2nd International Workshop on Quantum Programming Languages, 2004, pp. 163–178] is the basis for the language developed in this paper. This is work in progress.