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. Breugel, F. V. 2005. A behavioural pseudometric for metric labelled transition systems. In Proceedings of the International Conference on Concurrency Theory. Lecture Notes in Computer Science, vol. 3653. Springer, 141--155.
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. Feng, Y., Duan, R. Y., Ji, Z. F., and Ying, M. S. 2007. Probabilistic bisimulations for quantum processes. Inf. Comput. 205, 1608--1639.
6. Gay, S. J. and Nagarajan, R. 2005. Communicating quantum processes. In Proceedings of the 32nd ACM Symposium on Principles of Programming Languages. ACM Press, 145--157.
7. Gay, S. J. and Nagarajan, R. 2006. Typechecking communicating quantum processes. Math. Structures Comput. Sci. 16, 375--406.
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. Jorrand, P. and Lalire, M. 2005. Toward a quantum process algebra. In Proceedings of the 1st ACM Conference on Computing Frontiers. ACM Press, 111--119.
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. Lalire, M. 2006. Relations among quantum processes: Bisimilarity and congruence. Math. Structures Comput. Sci. 16, 407--428.
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. Milner, R. 1989. Communication and Concurrency. Prentice Hall, New York.
15. Milner, R., Parrow, J., and Walker, D. 1992. A calculus of mobile processes, Parts i and ii. Inf. Comput. 100, 1--77.
16. Nielsen, M. A. and Chuang, I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge.
17. Selinger, P. 2004. Towards a quantum programming language. Math. Structures Comput. Sci. 14, 527--586.
18. Wootters, W. K. and Zurek, W. H. 1982. A single quantum cannot be cloned. Nature 299, 802--803.
19. Ying, M. S. 2001. Topology in Process Calculus: Approximate Correctness and Infinite Evolution of Concurrent Programs. Springer, New York.
20. Ying, M. S. 2002. Bisimulation indexes and their applications. Theor. Comput. Sci. 275, 1--68.
21. Ying, M. S. and Wirsing, M. 2000. Approximate bisimilarity. In Proceedings of the 8th International Conference on Algebraic Methodology and Software Technology (AMAST'00). T. Rus, Ed. Lecture Notes in Computer Science, vol. 1816, Springer, 309--322.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

• Theory of computation

  • Formal languages and automata theory

  • Semantics and reasoning

    • Program reasoning

      • Program specifications

    • Program semantics

      • Operational semantics