×

Quantum patterns and types for entanglement and separability. (English) Zbl 1277.68066

Selinger, Peter (ed.), Proceedings of the 3rd international workshop on quantum programming languages (QPL 2005), DePaul University, Chicago, IL, USA, June 30 – July 1, 2005. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 170, 125-138 (2007).
Summary: 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. Techn. Rep. LAUR-96-2724, Los Alamos National Laboratory (1996)] and the classically-controlled quantum turing machine CQTM [the author and P. Jorrand, Electron. Notes Theor. Comput. Sci. 135, No. 3, 119–128 (2006; Zbl 1272.81041)]. Several quantum programming languages follow this model [J. W. Sanders and P. Zuliani, Lect. Notes Comput. Sci. 1837, 80–99 (2000; Zbl 0963.68037); P. Selinger, Math. Struct. Comput. Sci. 14, No. 4, 527–586 (2004; Zbl 1085.68014)]. Among them, the functional language defined by B. Valiron [“Quantum typing”, in: Proceedings of the 2nd international workshop on quantum programming languages, QPL 2004. Turku: Turku Centre for Computer Science, 163–178 (2004), http://www.mathstat.dal.ca/~selinger/qpl2004/PDFS/11Valiron.pdf] is the basis for the language developed in this paper. This is work in progress.
For the entire collection see [Zbl 1273.68044].

MSC:

68P05 Data structures
68N15 Theory of programming languages
81P68 Quantum computation

Software:

QPL; qGCL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bettelli, S.; Calarco, T.; Serafini, L., Toward an architecture for quantum programming, Eur. Phys. J. D, 25, 2, 181-200 (2003)
[2] Danos, V.; Kashefi, E.; Panangaden, P., The Measurement Calculus (2004), e-print
[3] S.J. Gay and R. Nagarajan Communicating quantum processes; S.J. Gay and R. Nagarajan Communicating quantum processes · Zbl 1369.68207
[4] Hein, M.; Eisert, J.; Briegel, J. H., Multi-party entanglement in graph states, Phys. Rev. A, 69, 062311 (2004) · Zbl 1232.81007
[5] E. Knill, Conventions for Quantum Pseudocode; E. Knill, Conventions for Quantum Pseudocode
[6] M. Lalire and Ph. Jorrand, A process algebraic approach to concurrent and distributed quantum computation: operational semantics; M. Lalire and Ph. Jorrand, A process algebraic approach to concurrent and distributed quantum computation: operational semantics
[7] Mhalla, M.; Perdrix, S., Complexity of Graph State Preparation (2004)
[8] Nielsen, M. A.; Chuang, I. L., Quantum Computation and Quantum Information (2000), Cambridge University Press · Zbl 1049.81015
[9] Perdrix, S.; Jorrand, Ph., Classically-Controlled Quantum Computation, to appear in Mathematical Structures in Computer Science · Zbl 1272.81041
[10] Perdrix, S., State Transfer instead of Teleportation in Measurement-based Quantum Computation, International Journal of Quantum Information, 3, 1, 219-224 (2005)
[11] Raussendorf, R.; Briegel, H. J., A One-Way Quantum Computer, Phys. Rev. Lett., 86, 5188-5191 (2001)
[12] Sanders, J. W.; Zuliani, P., Quantum Programming, Mathematics of Program Construction, (Springer LNCS, 1837 (2000)), 80-99 · Zbl 0963.68037
[13] Selinger, P., Towards a Quantum Programming Language, Mathematical Structures in Computer Science, 14, 4, 527-586 (2004) · Zbl 1085.68014
[14] Shor, P., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal of Computing, 26, 1484-1509 (1997) · Zbl 1005.11065
[15] B. Valiron, Quantum Typing; B. Valiron, Quantum Typing
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.