An algebra of quantum processes

ABSTRACT

We introduce an algebra qCCS of pure quantum processes in which communications by moving quantum states physically are allowed and computations are modeled by super-operators, but no classical data is explicitly involved. An operational semantics of qCCS is presented in terms of (nonprobabilistic) labeled transition systems. Strong bisimulation between processes modeled in qCCS is defined, and its fundamental algebraic properties are established, including uniqueness of the solutions of recursive equations. To model sequential computation in qCCS, a reduction relation between processes is defined. By combining reduction relation and strong bisimulation we introduce the notion of strong reduction-bisimulation, which is a device for observing interaction of computation and communication in quantum systems. Finally, a notion of strong approximate bisimulation (equivalently, strong bisimulation distance) and its reduction counterpart are introduced. It is proved that both approximate bisimilarity and approximate reduction-bisimilarity are preserved by various constructors of quantum processes. This provides us with a formal tool for observing robustness of quantum processes against inaccuracy in the implementation of its elementary gates.

REFERENCES

• 1: Franck van Breugel, A behavioural pseudometric for metric labelled transition systems, CONCUR 2005 - Concurrency Theory, Springer-Verlag, London, 2005 [doi>10.1007/11539452_14]
• 2: Buzek, V. and Hillery, M. 1996. Quantum copying: Beyond the no-cloning theorem. Phys. Rev. A 54, 1844--1852.
• 3: D'Hondt, E. 2005. Distributed quantum computation: A measurement-based approach. Ph.D. thesis, Vrije Universiteit Brussel.
• 4: Dieks, D. 1982. Communication by EPR devices. Phys. Lett. A 92, 271--272.
• 5: Yuan Feng , Runyao Duan , Zhengfeng Ji , Mingsheng Ying, Probabilistic bisimulations for quantum processes, Information and Computation, v.205 n.11, p.1608-1639, November, 2007 [doi>10.1016/j.ic.2007.08.001]
• 6: Simon J. Gay , Rajagopal Nagarajan, Communicating quantum processes, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-157, January 12-14, 2005, Long Beach, California, USA
• 7: Simon J. Gay , Rajagopal Nagarajan, Types and typechecking for Communicating Quantum Processes, Mathematical Structures in Computer Science, v.16 n.3, p.375-406, June 2006 [doi>10.1017/S0960129506005263]
• 8: Jorrand, P. and Lalire, M. 2004. From quantum physics to programming languages: A process algebraic approach. In Proceedings of the International Workshop on Unconventional Programming Paradigms. J. P. Banatre et al. Eds., Revised Selected and Invited Papers, Lecture Notes in Computer Science, vol. 3566, Springer, 2005, 1--16.
• 9: Philippe Jorrand , Marie Lalire, Toward a quantum process algebra, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy [doi>10.1145/977091.977108]
• 10: Josza, R. and Linden, N. 2003. On the role of entanglement in quantum computational speed-up. Proc. Roy. Soc. Lond. A 459, 2011--2032.
• 11: Kitaev, A. 1997. Quantum computations: Algorithms and error-correction. Russian Math. Surv. 52, 1191--1249.
• 12: Marie Lalire, Relations among quantum processes: bisimilarity and congruence, Mathematical Structures in Computer Science, v.16 n.3, p.407-428, June 2006 [doi>10.1017/S096012950600524X]
• 13: Lalire, M. and Jorrand, P. 2004. A process algebraic approach to concurrent and distributed quantum computation: Operational semantics. In Proceedings of the 2nd International Workshop on Quantum Programming Languages, P. Selinger, Ed. TUCS General Publications 33, 109--126.
• 14: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 15: Robin Milner , Joachim Parrow , David Walker, A calculus of mobile processes, II, Information and Computation, v.100 n.1, p.41-77, Sept. 1992 [doi>10.1016/0890-5401(92)90009-5]
• 16: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 17: Peter Selinger, Towards a quantum programming language, Mathematical Structures in Computer Science, v.14 n.4, p.527-586, August 2004 [doi>10.1017/S0960129504004256]
• 18: Wootters, W. K. and Zurek, W. H. 1982. A single quantum cannot be cloned. Nature 299, 802--803.
• 19: Mingsheng Ying, Topology in process calculus: approximate correctness and infinite evolution of concurrent programs, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 20: Mingsheng Ying, Bisimulation indexes and their applications, Theoretical Computer Science, v.275 n.1-2, p.1-68, March 28 2002 [doi>10.1016/S0304-3975(01)00124-4]
• 21: Mingsheng Ying , Martin Wirsing, Approximate Bisimilarity, Proceedings of the 8th International Conference on Algebraic Methodology and Software Technology, p.309-322, May 20-27, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Specification techniques
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

General Terms:
Theory

Keywords:
Quantum computation, bisimulation, process algebra, quantum communication, super-operator