A general definition of a quantum predicate and quantum labelled transition systems for finite quantum computation systems is presented. The notion of a quantum predicate as a positive operator-valued measure is developed. The main results of this paper are a theorem about the existence of generalised predicates for quantum programs defined as completely positive maps and a theorem about the existence of a GSOS format for quantum labelled transition systems. The first theorem is a slight generalisation of D'Hondt and Panagaden's theorem about the quantum weakest precondition in terms of discrete support positive operator-valued measures.
@article{bwmeta1.element.bwnjournal-article-amcv18i3p341bwm,
author = {Marek Sawerwain and Roman Gielerak},
title = {Natural quantum operational semantics with predicates},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {18},
year = {2008},
pages = {341-359},
zbl = {1200.68118},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv18i3p341bwm}
}
Marek Sawerwain; Roman Gielerak. Natural quantum operational semantics with predicates. International Journal of Applied Mathematics and Computer Science, Tome 18 (2008) pp. 341-359. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv18i3p341bwm/
[000] Aceto L. (1994). GSOS and finite labelled transition systems, Theoretical Computer Science 131(1): 181-195. | Zbl 0822.68060
[001] de Bakker J. W., de Roever W. P. (1972). A calculus for recursive programs schemes, in: M. Nivat (Ed.), Automata, Languages, and Programming, North-Holland, Amsterdam, pp. 167-196. | Zbl 0238.68006
[002] de Bakker J. W., Meertens, L. G. L. T. (1975). On the completeness of the inductive assertion method, Journal of Computer and Systems Sciences 11(3): 323-357. | Zbl 0353.68040
[003] Bennett C.H., Brassard G., Crepeau C., Jozsa R., Peres A. and Wooters W.K. (1993). Teleporting an unknown state via dual classical and Einstein-Podolsky-Rosen channels, Physical Review Letters 70(13): 1895-1899. | Zbl 1051.81505
[004] Birkhoff G. and von Neumann J. (1936). The logic of quantum mechanics, Annals of Mathematics 37(4): 823-843. | Zbl 0015.14603
[005] Bloom B. (1989): Ready Simulation, Bisimulation, and the Semantics of CCS-like Languages, Ph.D. thesis, Massachusetts Institute of Technology.
[006] Bloom B., Istrail S., Meyer A.R. (1989). Bisimulation can't be traced: Preliminary report, Conference Record of the 15th Annual ACM Symposium on Principles of Programming Languages, San Diego, CA, USA, pp. 229-239. | Zbl 0886.68027
[007] Boschi D., Branca S., de Martini F., Hardy L. and Popescu S. (1998). Experimental realization of teleporting an unknown pure quantum state via dual classical and EinsteinPodolsky-Rosen channels, Physical Review Letters 80(6): 1121-1125. | Zbl 0947.81004
[008] Bouwmeester D., Pan J.W., Mattle K., Eibl M., Weinfurter H. and Zeilinger A. (1997). Experimental quantum teleportation, Nature 390(6660): 575-579.
[009] Choi M.D. (1975). Completely positive linear maps on complex matrices, Linear Algebra and Its Applications 10(3): 285-290. | Zbl 0327.15018
[010] Coecke B. and Martin K. (2002). A partial order on classical and quantum states, Technical report, PRG-RR-02-07, Oxford University. | Zbl 1253.81008
[011] Deutsch D. and Jozsa R. (1992). Rapid solutions of problems by quantum computation, Proceedings of the Royal Society of London A, 439(1907): 553-558. | Zbl 0792.68058
[012] Dijkstra E. W. (1976). A Discipline of Programming, PrenticeHall, Englewood Cliffs, NJ. | Zbl 0368.68005
[013] D'Hondt E. and Panangaden P. (2006). Quantum weakest preconditions, Mathematical Structures in Computer Science 16(3): 429-451. | Zbl 1122.68058
[014] Gielerak R. and Sawerwain M. (2007). Generalised quantum weakest preconditions, available at: arXiv:quant-ph/0710.5239v1. | Zbl 1197.81047
[015] Gleason A. M. (1957). Measures on the closed subspaces of a Hilbert space, Journal of Mathematics and Mechanics 6(4): 885-893. | Zbl 0078.28803
[016] Grover L. K. (1996). A fast quantum-mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, USA, ACM Press, New York, NY, pp. 212-219. | Zbl 0922.68044
[017] Hirvensalo M. (2001). Quantum Computing, Springer-Verlag, Berlin. | Zbl 0976.68063
[018] Hoare C. (1969). An axiomatic basis for computer programming, Communications of the ACM 12(10): 576-583. | Zbl 0179.23105
[019] Jozsa R. (2005). An introduction to measurement based quantum computation, available at: arXiv:quant-ph/0508124.
[020] Kraus K. (1983). State, Effects, and Operations, Springer, Berlin.
[021] Kak S. (2003). Teleportation protocols requiring only one classical bit, available at: arXiv:quant-ph/0305085v4.
[022] Lalire M., Jorrand P. (2004). A process algebraic approach to concurrent and distributed quantum computation: Operational semantics, Proceedings of the 2nd International Workshop on Quantum Programming Languages, Turku, Finland, pp. 109-126.
[023] Löwner K. (1934): Über monotone Matrixfunktionen, Mathematische Zeitschrift 38(1): 177-216. | Zbl 0008.11301
[024] Mlnařík H. (2006): LanQ-Operational Semantics of Quantum Programming Language LanQ, Technical report FIMURS-2006-10, available at: http://www.muni.cz/research/publications/706560.
[025] Mauerer W. (2005). Semantics and simulation of communication in quantum programming, M.Sc. thesis, University Erlangen-Nuremberg Erlangen, Nürnberg, see: arXiv:quant-ph/0511145.
[026] Ömer B. (2005). Classical concepts in quantum programming, International Journal of Theoretical Physics, 44(7): 943-955, see: arXiv:quant-ph/0211100. | Zbl 1119.81316
[027] Peres A. (1995). Quantum Theory: Concepts and Methods, Kluwer Academic Publishers, Dordrecht. | Zbl 0867.00010
[028] Plotkin G.D. (2004). A structural approach to operational semantics, Journal of Logic and Algebraic Programming 60: 17-139. | Zbl 1082.68062
[029] Raynal P. (2006). Unambiguous state discrimination of two density matrices in quantum information theory, Ph.D. thesis, Institut für Optik, Information und Photonik, Max Planck Forschungsgruppe, see: arXiv:quant-ph/0611133.
[030] Rüdiger R. (2007). Quantum programming languages: An introductory overview, The Computer Journal 50(2): 134-150.
[031] Raussendorf R., Briegel H.J. (2001). A one-way quantum computer, Physical Review Letters 86(22): 5188-5191, see: arXiv:quant-ph/0010033.
[032] Raussendorf R., Browne D.E., Briegel H.J. (2003). Measurement-based quantum computation with cluster states, Physical Review A, 68(2), 022312, see: arXiv:quant-ph/0301052.
[033] Sawerwain M., Gielerak R. and Pilecki J. (2006). Operational semantics for quantum computation, in: Węgrzyn S., Znamirowski L., Czachórski T., Kozielski S. (Eds.), New Technologies in Computer Networks, WKiŁ, Warsaw, Vol. 1, pp. 69-77, (in Polish).
[034] Selinger P.: (2004): Towards a quantum programming language, Mathematical Structures in Computer Science 14(5): 527-586. | Zbl 1085.68014
[035] Selinger P.: (2004). Towards a semantics for higher order quantum computation, Proceedings of the 2nd International Workshop on Quantum Programming Languages, Turku, Finland, pp. 127-143.
[036] Sewell G.: (2005). On the mathematical structure of quantum measurement theory, Reports on Mathematical Physics 56(2): 271-290, see: arXiv:math-ph/0505032. | Zbl 1086.81016
[037] Shor P. (2004). Progress in quntum algorithms, Quantum Information Processing 3(1): 5-13. | Zbl 1075.68602