Abstract
Quantum processes describe concurrent communicating systems that may involve quantum information. We propose a notion of open bisimulation for quantum processes and show that it provides both a sound and complete proof methodology for a natural extensional behavioural equivalence between quantum processes. We also give a modal characterisation of the behavioural equivalence, by extending the Hennessy-Milner logic to a quantum setting.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baeten, J.C.M., Weijland, W.P.: Process Algebra. Cambridge University Press (1990)
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)
Davidson, T.A.S.: Formal Verification Techniques using Quantum Process Calculus. PhD thesis, University of Warwick (2011)
Deng, Y., Du, W.: Logical, metric, and algorithmic characterisations of probabilistic bisimulation. Technical Report CMU-CS-11-110. Carnegie Mellon University (March 2011)
Deng, Y., Feng, Y.: Open bisimulation for quantum processes. Full Version of the current paper, http://arxiv.org/abs/1201.0416
Deng, Y., Hennessy, M.: On the Semantics of Markov Automata. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 307–318. Springer, Heidelberg (2011)
Deng, Y., van Glabbeek, R., Hennessy, M., Morgan, C.: Testing Finitary Probabilistic Processes (Extended Abstract). In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 274–288. Springer, Heidelberg (2009)
Feng, Y., Duan, R., Ji, Z., Ying, M.: Probabilistic bisimulations for quantum processes. Information and Computation 205(11), 1608–1639 (2007)
Feng, Y., Duan, R., Ying, M.: Bisimulation for quantum processes. In: Proc. POPL 2011, pp. 523–534. ACM (2011)
Fournet, C., Gonthier, G.: A hierarchy of equivalences for asynchronous calculi. Journal of Logic and Algebraic Programming 63(1), 131–173 (2005)
Gay, S.J., Nagarajan, R.: Types and typechecking for communicating quantum processes. Mathematical Structures in Computer Science 16(03), 375–406 (2006)
Gay, S.J., Nagarajan, R.: Communicating quantum processes. In: Palsberg, J., Abadi, M. (eds.) Proc. POPL 2005, pp. 145–157 (2005)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. ACM STOC, pp. 212–219 (1996)
Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters 78(2), 325 (1997)
Hennessy, M.: A proof system for communicating processes with value-passing. Formal Aspects of Computer Science 3, 346–366 (1991)
Hennessy, M., Ingólfsdóttir, A.: A theory of communicating processes value-passing. Information and Computation 107(2), 202–236 (1993)
Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. Journal of the ACM 32(1), 137–161 (1985)
Hoare, C.A.R.: Communicating Sequential Processes. Prentice Hall (1985)
Honda, K., Tokoro, M.: On reduction-based process semantics. Theoretical Computer Science 151(2), 437–486 (1995)
Jeffrey, A., Rathke, J.: Contextual equivalence for higher-order pi-calculus revisited. Logical Methods in Computer Science 1(1:4) (2005)
Jorrand, P., Lalire, M.: Toward a quantum process algebra. In: Proceedings of the 1st Conference on Computing Frontiers, pp. 111–119. ACM (2004)
Lalire, M.: Relations among quantum processes: Bisimilarity and congruence. Mathematical Structures in Computer Science 16(3), 407–428 (2006)
Milner, R.: Communication and Concurrency. Prentice-Hall (1989)
Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes, Parts I and II. Information and Computation 100, 1–77 (1992)
Nielsen, M., Chuang, I.: Quantum computation and quantum information. Cambridge University Press (2000)
Rathke, J., Sobociński, P.: Deriving Structural Labelled Transitions for Mobile Ambients. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 462–476. Springer, Heidelberg (2008)
Sangiorgi, D.: A theory of bisimulation for the pi-calculus. Acta Informatica 33(1), 69–97 (1996)
Sangiorgi, D., Kobayashi, N., Sumii, E.: Environmental bisimulations for higher-order languages. In: Proc. LICS 2007, pp. 293–302. IEEE Computer Society (2007)
Sangiorgi, D., Walker, D.: The π-calculus: a Theory of Mobile Processes. Cambridge University Press (2001)
Shor, P.W.: Algorithms for quantum computation: discrete log and factoring. In: Proc. FOCS 1994, pp. 124–134 (1994)
Ying, M., Feng, Y., Duan, R., Ji, Z.: An algebra of quantum processes. ACM Transactions on Computational Logic 10(3), 1–36 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Deng, Y., Feng, Y. (2012). Open Bisimulation for Quantum Processes. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds) Theoretical Computer Science. TCS 2012. Lecture Notes in Computer Science, vol 7604. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33475-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-33475-7_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33474-0
Online ISBN: 978-3-642-33475-7
eBook Packages: Computer ScienceComputer Science (R0)