No Access

A Unifying Coalgebraic Semantics Framework for Quantum Systems

Ai Liu

School of Mathematical Sciences, Peking University, P. R. China

Graduate School of Advanced Science and Engineering, Hiroshima University, Japan

E-mail Address: shaoai@pku.edu.cn

Search for more papers by this author

and

Meng Sun

School of Mathematical Sciences, Peking University, P. R. China

Center for Quantum Computing, Peng Cheng Laboratory, Shenzhen 518055, P. R. China

E-mail Address: sunm@pku.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218194021500133Cited by:1 (Source: Crossref)

Abstract

As a quantum counterpart of labeled transition system (LTS), quantum labeled transition system (QLTS) is a powerful formalism for modeling quantum programs or protocols, and gives a categorical understanding for quantum computation. With the help of quantum branching monad, QLTS provides a framework extending some ideas in non-deterministic or probabilistic systems to quantum systems. On the other hand, quantum finite automata (QFA) emerged as a very elegant and simple model for resolving some quantum computational problems. In this paper, we propose the notion of reactive quantum system (RQS), a variant of QLTS capturing reactive system behavior, and develop a coalgebraic semantics for QLTS, RQS and QFA by an endofunctor on the category of convex sets, which has a final coalgebra. Such a coalgebraic semantics provides a unifying abstract interpretation for QLTS, RQS and QFA. The notions of bisimulation and simulation can be employed to compare the behavior of different types of quantum systems and judge whether a coalgebra can be behaviorally simulated by another.

Keywords:

References

1. N. S. Yanofsky and M. Mannucci, Quantum Computing for Computer Scientists (Cambridge University Press, Cambridge, 2008). Crossref, Google Scholar
2. M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2002). Google Scholar
3. M. Ying, Foundations of Quantum Programming (Morgan Kaufmann, Amsterdam, 2016). Google Scholar
4. P. Selinger, Towards a quantum programming language, Math. Structures Comput. Sci. 14(4) (2004) 527–586. Crossref, Web of Science, Google Scholar
5. A. Molina and J. Watrous, Revisiting the simulation of quantum turing machines by quantum circuits, 2018, arXiv:1808.01701. Google Scholar
6. I. Hasuo and N. Hoshino, Semantics of higher-order quantum computation via geometry of interaction, Ann. Pure Appl. Logic 168(2) (2017) 404–469. Crossref, Web of Science, Google Scholar
7. B. Coecke and A. Kissinger, Picturing Quantum Processes (Cambridge University Press, Cambridge, 2017). Crossref, Google Scholar
8. M. Ying, Y. Feng, R. Duan and Z. Ji, An algebra of quantum processes, ACM Trans. Comput. Log. 10(3) (2009) 19:1–19:36. Crossref, Web of Science, Google Scholar
9. M. Hirvensalo, Quantum automata theory - A review, in Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement, LNCS, Vol. 7020 (Springer, Berlin, 2011), pp. 146–167. Crossref, Google Scholar
10. L. Li and Y. Feng, Quantum Markov chains: Description of hybrid systems, decidability of equivalence, and model checking linear-time properties, Inf. Comput. 244 (2015) 229–244. Crossref, Web of Science, Google Scholar
11. S. J. Gay and R. Nagarajan, Communicating quantum processes, in Proc. POPL 2005, 2005, pp. 145–157. Crossref, Google Scholar
12. C. Moore and J. P. Crutchfield, Quantum automata and quantum grammars, Theor. Comput. Sci. 237(1–2) (2000) 275–306. Crossref, Web of Science, Google Scholar
13. A. Kondacs and J. Watrous, On the power of quantum finite state automata, in Proc. FOCS 1997, 1997, pp. 66–75. Crossref, Google Scholar
14. A. Ambainis, M. Beaudry, M. Golovkins, A. Kikusts, M. Mercer and D. Thérien, Algebraic results on quantum automata, Theory Comput. Syst. 39(1) (2006) 165–188. Crossref, Web of Science, Google Scholar
15. M. Hirvensalo, Quantum automata with open time evolution, IJNCR 1(1) (2010) 70–85. Google Scholar
16. E. Ardeshir-Larijani, S. J. Gay and R. Nagarajan, Equivalence checking of quantum protocols, in Proc. TACAS 2013, LNCS, Vol. 7795, 2013, pp. 478–492. Crossref, Google Scholar
17. U. D. Lago and A. Rioli, Applicative bisimulation and quantum $λ$ $λ$ -calculi, in Proc. FSEN 2015, LNCS, Vol. 9392, 2015, pp. 54–68. Google Scholar
18. T. A. S. Davidson, Formal Verification Techniques Using Quantum Process Calculus, PhD thesis, University of Warwick, Coventry, UK (2012). Google Scholar
19. Y. Deng and Y. Feng, Open bisimulation for quantum processes, in Proc. TCS 2012, LNCS, Vol. 7604, 2012, pp. 119–133. Crossref, Google Scholar
20. Y. Feng, Y. Deng and M. Ying, Symbolic bisimulation for quantum processes, ACM Trans. Comput. Log. 15(2) (2014) 14:1–14:32. Crossref, Web of Science, Google Scholar
21. Y. Feng, R. Duan and M. Ying, Bisimulation for quantum processes, ACM Trans. Program. Lang. Syst. 34(4) (2012) 17:1–17:43. Crossref, Web of Science, Google Scholar
22. T. Kubota, Y. Kakutani, G. Kato, Y. Kawano and H. Sakurada, Application of a process calculus to security proofs of quantum protocols, in Proc. (FCS) 2012, 2012, p. 1. Google Scholar
23. B. Jacobs, Introduction to Coalgebra: Towards Mathematics of States and Observation, Cambridge Tracts in Theoretical Computer Science, Vol. 59 (Cambridge University Press, Cambridge, 2016). Crossref, Google Scholar
24. H. Ogawa, Coalgebraic approach to equivalences of quantum systems, Master’s thesis, University of Tokyo (2014). Google Scholar
25. N. Urabe and I. Hasuo, Generic forward and backward simulations III: Quantitative simulations by matrices, in Proc. CONCUR 2014, LNCS, Vol. 8704, 2014, pp. 451–466. Crossref, Google Scholar
26. F. Roumen, Coalgebraic quantum computation, in Proc. QPL 2012, EPTCS, Vol. 158, 2014, pp. 29–38. Crossref, Google Scholar
27. A. Liu and M. Sun, A coalgebraic semantics framework for quantum systems, in Proc. ICFEM 2019, LNCS, Vol. 11852, 2019, pp. 387–402. Crossref, Google Scholar
28. J. J. M. M. Rutten, Universal coalgebra: A theory of systems, Theor. Comput. Sci. 249(1) (2000) 3–80. Crossref, Web of Science, Google Scholar
29. S. Meng and L. S. Barbosa, Components as coalgebras: The refinement dimension, Theor. Comput. Sci. 351(2) (2006) 276–294. Crossref, Web of Science, Google Scholar
30. M. Ying and Y. Feng, Quantum loop programs, Acta Informatica 47(4) (2010) 221–250. Crossref, Web of Science, Google Scholar
31. A. Sokolova, Coalgebraic analysis of probabilistic systems, PhD thesis, Technische Universiteit Eindhoven (2005). Google Scholar
32. Y. Feng, N. Yu and M. Ying, Model checking quantum Markov chains, J. Comput. Syst. Sci. 79(7) (2013) 1181–1198. Crossref, Web of Science, Google Scholar
33. H. Nishimura and M. Ozawa, Perfect computational equivalence between quantum turing machines and finitely generated uniform quantum circuit families, Quantum Inf. Proc. 8(1) (2009) 13–24. Crossref, Web of Science, Google Scholar
34. S. Ying and M. Ying, Reachability analysis of quantum Markov decision processes, Inf. Comput. 263 (2018) 31–51. Crossref, Web of Science, Google Scholar