Encodability criteria for quantum based systems. (English) Zbl 07872352
Summary: Quantum based systems are a relatively new research area for that different modelling languages including process calculi are currently under development. Encodings are often used to compare process calculi. Quality criteria are used then to rule out trivial or meaningless encodings. In this new context of quantum based systems, it is necessary to analyse the applicability of these quality criteria and to potentially extend or adapt them. As a first step, we test the suitability of classical criteria for encodings between quantum based languages and discuss new criteria.
Concretely, we present an encoding, from a language inspired by CQP into a language inspired by qCCS. We show that this encoding satisfies compositionality, name invariance (for channel and qubit names), operational correspondence, divergence reflection, success sensitiveness, and that it preserves the size of quantum registers. Then we show that there is no encoding from qCCS into CQP that is compositional, operationally corresponding, and success sensitive.
Concretely, we present an encoding, from a language inspired by CQP into a language inspired by qCCS. We show that this encoding satisfies compositionality, name invariance (for channel and qubit names), operational correspondence, divergence reflection, success sensitiveness, and that it preserves the size of quantum registers. Then we show that there is no encoding from qCCS into CQP that is compositional, operationally corresponding, and success sensitive.
MSC:
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
References:
| [1] | 20 A. Schmitt, K. Peters, and Y. Deng Vol. 20:2 |
| [2] | Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70:1895-1899, 1993. doi:10.1103/PhysRevLett.70.1895. · Zbl 1051.81505 · doi:10.1103/PhysRevLett.70.1895 |
| [3] | Benjamin Bisping, Uwe Nestmann, and Kirstin Peters. Coupled similarity: the first 32 years. Acta Informatica, 57(3-5):439-463, 2020. doi:10.1007/s00236-019-00356-4. · Zbl 1476.68166 · doi:10.1007/s00236-019-00356-4 |
| [4] | Timothy A. S. Davidson, Simon J. Gay, Rajagopal Nagarajan, and Ittoop V. Puthoor. Analysis of a Quantum Error Correcting Code using Quantum Process Calculus. In Proceedings of QPL, volume 95 of EPTCS, pages 67-80, 2012. doi:10.4204/EPTCS.95.7. · Zbl 1462.81068 · doi:10.4204/EPTCS.95.7 |
| [5] | DRMT + 04] Hugues De Riedmatten, Ivan Marcikic, Wolfgang Tittel, Hugo Zbinden, Daniel Collins, and Nicolas Gisin. Long Distance Quantum Teleportation in a Quantum Relay Configuration. Physical Review Letters, 92:047904, 2004. doi:10.1103/PhysRevLett.92.047904. · doi:10.1103/PhysRevLett.92.047904 |
| [6] | Yuan Feng, Runyao Duan, Zhengfeng Ji, and Mingsheng Ying. Probabilistic bisimulations for quantum processes. Information and Computation, 205(11):1608-1639, 2007. doi:10.1016/j. ic.2007.08.001. · Zbl 1130.68079 · doi:10.1016/j.ic.2007.08.001 |
| [7] | Yuan Feng, Runyao Duan, and Mingsheng Ying. Bisimulation for Quantum Processes. ACM Transactions on Programming Languages and Systems, 34(4), 2012. doi:10.1145/2400676. 2400680. · doi:10.1145/2400676.2400680 |
| [8] | Sonja Franke-Arnold, Simon J. Gay, and Ittoop V. Puthoor. Quantum Process Calculus for Linear Optical Quantum Computing. In Proceedings of Reversible Computation, volume 7948 of LNCS, pages 234-246. Springer, 2013. doi:10.1007/978-3-642-38986-3_19. · Zbl 1407.81063 · doi:10.1007/978-3-642-38986-3_19 |
| [9] | Vol. 20:2 ENCODABILITY CRITERIA FOR QUANTUM BASED SYSTEMS 5:39 |
| [10] | Sonja Franke-Arnold, Simon J. Gay, and Ittoop V. Puthoor. Verification of Linear Optical Quantum Computing using Quantum Process Calculus. In Preoceedings of EXPRESS/SOS, volume 160 of EPTCS, pages 111-129, 2014. doi:10.4204/EPTCS.160.10. · Zbl 1464.68242 · doi:10.4204/EPTCS.160.10 |
| [11] | Simon J. Gay. Quantum programming languages: survey and bibliography. Mathematical Structures of Computer Science, 16(4):581-600, 2006. doi:10.1017/S0960129506005378. · Zbl 1122.68021 · doi:10.1017/S0960129506005378 |
| [12] | Simon J. Gay and Rajagopal Nagarajan. Communicating quantum processes. In Proceedings of POPL, pages 145-157, 2005. doi:10.1145/1040305.1040318. · Zbl 1369.68207 · doi:10.1145/1040305.1040318 |
| [13] | Daniele Gorla. Towards a Unified Approach to Encodability and Separation Results for Process Calculi. Information and Computation, 208(9):1031-1053, 2010. doi:10.1016/j.ic.2010.05. 002. · Zbl 1209.68336 · doi:10.1016/j.ic.2010.05.002 |
| [14] | Simon J. Gay and Ittoop V. Puthoor. Application of Quantum Process Calculus to Higher Dimensional Quantum Protocols. In Proceedings of Quantum Physics and Logic, volume 158 of EPTCS, pages 15-28, 2012. doi:10.4204/EPTCS.158.2. · Zbl 1464.81019 · doi:10.4204/EPTCS.158.2 |
| [15] | Jozef Gruska. Quantum Computing. In Wiley Encyclopedia of Computer Science and Engineering. John Wiley & Sons, Inc., 2009. doi:10.1002/9780470050118.ecse720. · doi:10.1002/9780470050118.ecse720 |
| [16] | Philippe Jorrand and Marie Lalire. Toward a Quantum Process Algebra. In Proceedings of CF, pages 111-119, 2004. doi:10.1145/977091.977108. · doi:10.1145/977091.977108 |
| [17] | KKK + 12] Takahiro Kubota, Yoshihiko Kakutani, Go Kato, Yasuhito Kawano, and Hideki Sakurada. Application of a process calculus to security proofs of quantum protocols. In Proceedings of FCS, 2012. |
| [18] | KKK + 13] Takahiro Kubota, Yoshihiko Kakutani, Go Kato, Yasuhito Kawano, and Hideki Sakurada. Automated Verification of Equivalence on Quantum Cryptographic Protocols. EPiC Series in Computing, 15:64-69, 2013. |
| [19] | Dimitrios Kouzapas, Jorge A. Pérez, and Nobuko Yoshida. On the Relative Expressiveness of Higher-Order Session Processes. In Proceedings of ESOP, volume 9632 of LNCS, pages 446-475, 2016. doi:10.1007/978-3-662-49498-1_18. · Zbl 1335.68174 · doi:10.1007/978-3-662-49498-1_18 |
| [20] | Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press, 2010. doi:10.1017/cbo9780511976667.016. · Zbl 1288.81001 · doi:10.1017/cbo9780511976667.016 |
| [21] | Kirstin Peters. Comparing Process Calculi Using Encodings. In Proceedings of EXPRESS/SOS, volume 300 of EPCTS, pages 19-38, 2019. doi:10.4204/EPTCS.300.2. · Zbl 1543.68249 · doi:10.4204/EPTCS.300.2 |
| [22] | Gordon D. Plotkin. A Structural Approach to Operational Semantics. Journal of Logic and Algebraic Programming, 60:17-140, 2004. [An earlier version of this paper was published as technical report at Aarhus University in 1981.]. · Zbl 1082.68062 |
| [23] | Kirstin Peters, Uwe Nestmann, and Ursula Goltz. On Distributability in Process Cal-culi. In Proceedings of ESOP, volume 7792 of LNCS, pages 310-329, 2013. doi:10.1007/ 978-3-642-37036-6_18. · Zbl 1381.68215 · doi:10.1007/978-3-642-37036-6_18 |
| [24] | Kirstin Peters and Rob van Glabbeek. Analysing and Comparing Encodability Criteria. In Proceedings of EXPRESS/SOS, volume 190 of EPTCS, pages 46-60, 2015. doi:10.4204/EPTCS. 190.4. · Zbl 1476.68181 · doi:10.4204/EPTCS.190.4 |
| [25] | Eleanor Rieffel and Wolfgang Polak. An introduction to quantum computing for non-physicists. ACM Computing Surveys, 32(3):300-335, 2000. doi:10.1145/367701.367709. · doi:10.1145/367701.367709 |
| [26] | Anna Schmitt and Kirstin Peters. Probabilistic Operational Correspondence. In Proceedings of CONCUR, volume 279 of LIPIcs, pages 15:1-15:17, 2023. doi:10.4230/LIPIcs.CONCUR.2023. 15. · doi:10.4230/LIPIcs.CONCUR.2023.15 |
| [27] | Anna Schmitt, Kirstin Peters, and Yuxin Deng. Encodability Criteria for Quantum Based Systems. In Proceedings of Forte, volume 13273 of LNCS, pages 151-169. Springer, 2022. doi:10.1007/978-3-031-08679-3_10. · Zbl 1499.68234 · doi:10.1007/978-3-031-08679-3_10 |
| [28] | Anna Schmitt, Kirstin Peters, and Yuxin Deng. Encodability Criteria for Quantum Based Systems (Technical Report). Technical report, 2022. doi:10.48550/ARXIV.2204.06068. · doi:10.48550/ARXIV.2204.06068 |
| [29] | Mingsheng Ying, Yuan Feng, Runyao Duan, and Zhengfeng Ji. An algebra of quantum processes. ACM Transactions on Computational Logic, 10(3):1-36, 2009. doi:10.1145/1507244.1507249. · Zbl 1351.68187 · doi:10.1145/1507244.1507249 |
| [30] | Kazuya Yasuda, Takahiro Kubota, and Yoshihiko Kakutani. Observational Equivalence Using Schedulers for Quantum Processes. In Proceedings of Quantum Physics and Logic, volume 172 of EPTCS, pages 191-203, 2014. doi:10.4204/EPTCS.172.13. · Zbl 1464.68271 · doi:10.4204/EPTCS.172.13 |
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.
