An axiomatization for quantum processes to unifying quantum and classical computing. (English) Zbl 1468.81032
Summary: We establish an axiomatization for quantum processes, which is a quantum generalization of process algebra ACP (Algebra of Communicating Processes). We use the framework of a quantum process configuration \(\langle p,\varrho\rangle\), but we treat it as two relative independent part: the structural part \(p\) and the quantum part \(\varrho\), because the establishment of a sound and complete theory is dependent on the structural properties of the structural part \(p\). We let the quantum part \(\varrho\) be the outcomes of execution of \(p\) to examine and observe the function of the basic theory of quantum mechanics. We establish not only a strong bisimilarity for quantum processes, but also a weak bisimilarity to model the silent step and abstract internal computations in quantum processes. The relationship between quantum bisimilarity and classical bisimilarity is established, which makes an axiomatization of quantum processes possible. An axiomatization for quantum processes called qACP is designed, which involves not only quantum information, but also classical information and unifies quantum computing and classical computing. qACP can be used easily and widely for verification of most quantum communication protocols.
MSC:
| 81P68 | Quantum computation |
| 81P45 | Quantum information, communication, networks (quantum-theoretic aspects) |
References:
| [1] | Baeten, J.C.M.: A brief history of process algebra. Theor. Comput. Sci. In. Process. Algebra 335(2-3), 131-146 (2005) · Zbl 1080.68072 · doi:10.1016/j.tcs.2004.07.036 |
| [2] | Milner, R.: Communication and Concurrency. Prentice Hall, Upper Saddle River (1989) · Zbl 0683.68008 |
| [3] | Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes, Parts I and II. Inf. Comput. 1992(100), 1-77 (1992) · Zbl 0752.68036 · doi:10.1016/0890-5401(92)90008-4 |
| [4] | Hoare, C.A.R.: Communicating sequential processes. http://www.usingcsp.com/ (1985) · Zbl 0637.68007 |
| [5] | Fokkink, W.: Introduction to Process Algebra, 2nd edn. Springer, Berlin (2007) · Zbl 0941.68087 |
| [6] | Plotkin, G.D.: A structural approach to operational semantics. Aarhus University, Tech. Report DAIMIFN-19 (1981) |
| [7] | Baeten, J.C.M., Bergstra, J.A., Klop, J.W.: On the consistency of Koomen’s fair abstraction rule. Theor. Comput. Sci. 51(1/2), 129-176 (1987) · Zbl 0621.68010 · doi:10.1016/0304-3975(87)90052-1 |
| [8] | Feng, Y., Duan, R.Y., Ji, Z.F., Ying, M.: Probabilistic bisimulations for quantum processes. Inf. Comput. 205(2007), 1608-1639 (2007) · Zbl 1130.68079 · doi:10.1016/j.ic.2007.08.001 |
| [9] | Gay, S.J., Nagarajan, R.: Communicating quantum processes. In: Proceedings of the 32nd ACM Symposium on Principles of Programming Languages, Long Beach, California, USA, pp. 145-157. ACM Press (2005) · Zbl 1369.68207 |
| [10] | Gay, S.J., Nagarajan, R.: Typechecking communicating quantum processes. Math. Struct. Comput. Sci. 2006(16), 375-406 (2006) · Zbl 1122.68059 · doi:10.1017/S0960129506005263 |
| [11] | Jorrand, P., Lalire, M.: Toward a quantum process algebra. In: Proceedings of the 1st ACM Conference on Computing Frontiers, Ischia, Italy, pp. 111-119. ACM Press (2005) |
| [12] | Jorrand, P., Lalire, M.: From quantum physics to programming languages: a process algebraic approach. Lect. Notes Comput. Sci 2005(3566), 1-16 (2005) |
| [13] | Lalire, M.: Relations among quantum processes: bisimilarity and congruence. Math. Struct. Comput. Sci. 2006(16), 407-428 (2006) · Zbl 1122.68060 · doi:10.1017/S096012950600524X |
| [14] | Lalire, M., Jorrand, P.: A process algebraic approach to concurrent and distributed quantum computation: operational semantics. In: Proceedings of the 2nd International Workshop on Quantum Programming Languages, pp. 109-126 (2004) |
| [15] | Ying, M., Feng, Y., Duan, R., Ji, Z.: An algebra of quantum processes. ACM Trans. Comput. Log. (TOCL) 10(3), 1-36 (2009) · Zbl 1351.68187 · doi:10.1145/1507244.1507249 |
| [16] | Hennessy, M., Lin, H.: Symbolic bisimulations. Theor. Comput. Sci. 138(2), 353-389 (1995) · Zbl 0874.68187 · doi:10.1016/0304-3975(94)00172-F |
| [17] | Feng, Y., Duan, R., Ying, M.: Bisimulations for quantum processes. In: Proceedings of the 38th ACM Symposium on Principles of Programming Languages (POPL 11), pp. 523-534. ACM Press (2011) · Zbl 1284.68425 |
| [18] | Bennett, C.H., Brassard, G.: Quantum cryptography: Public-key distribution and coin tossing. In: Proceedings of the IEEE International Conference on Computer, Systems and Signal Processing, pp. 175-179 (1984) · Zbl 1306.81030 |
| [19] | Deng, Y., Feng, Y.: Open bisimulation for quantum processes. Manuscript, arXiv:1201.0416 (2012) · Zbl 1362.68210 |
| [20] | Feng, Y., Deng, Y., Ying, M.: Symbolic bisimulation for quantum processes. Manuscript, arXiv:1202.3484 (2012) |
| [21] | Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) · Zbl 1049.81015 |
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.
