Bisimulation for Quantum Processes
Bisimulation for Quantum Processes
Feng, Duan, and Ying introduce probabilistic bisimulation for quantum processes and study its compositional and recursive properties.
Paper information (POPL 2011; extended TOPLAS version 2012; preprint: 2010) — Yuan Feng, Runyao Duan, and Mingsheng Ying. arXiv:1007.2584
Work
The paper introduces probabilistic bisimulation for quantum processes with both classical and quantum communication. Bisimulation compares observable actions, communications, and quantum-state changes to determine whether two processes behave alike. The paper studies congruence under process-algebra combinators such as parallel composition, and proves uniqueness results for solutions of recursive process equations.
Contributions
- A probabilistic bisimulation notion for quantum processes.
- Congruence results for combinations involving classical and quantum communication.
- Algebraic laws and uniqueness results for recursive quantum-process equations.
- A process-level proof technique for equivalence checking of complex quantum protocols.
Limits
Bisimulation depends on the chosen process model, observable actions, and quantum-state equivalence; it does not automatically establish equivalence under hardware noise, resource costs, or protocol confidentiality. Recursive-equation results must be read within the stated semantic domain and combinator range, and do not directly cover every quantum language.
Connections
The paper extends the CQP process and ownership direction of Communicating Quantum Processes toward process equivalence and compositional closure. It can also be compared with the compositional protocol representation in A Categorical Semantics of Quantum Protocols and gives a process-algebra perspective on equivalence checking in Verification Methods and Tools.
Original paper
Yuan Feng, Runyao Duan, and Mingsheng Ying, Bisimulation for Quantum Processes, POPL 2011; extended ACM Transactions on Programming Languages and Systems 34(4), Article 17 (2012). arXiv:1007.2584