An Algebra of Quantum Processes

被引:53
作者
Ying, Mingsheng [1 ,2 ]
Feng, Yuan [1 ]
Duan, Runyao [1 ]
Ji, Zhengfeng [3 ]
机构
[1] Tsinghua Univ, Dept Comp Sci & Technol, Tsinghua Natl Lab Informat Sci & Technol, State Key Lab Intelligent Technol & Syst, Beijing 100084, Peoples R China
[2] Univ Technol Sydney, Fac Informat Technol, Ctr Quantum Computat & Intelligent Syst, Ultimo, NSW 2007, Australia
[3] Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100080, Peoples R China
关键词
Theory; Quantum computation; quantum communication; super-operator; process algebra; bisimulation;
D O I
10.1145/1507244.1507249
中图分类号
TP301 [理论、方法];
学科分类号
080201 [机械制造及其自动化];
摘要
We introduce an algebra qCCS of pure quantum processes in which communications by moving quantum states physically are allowed and computations are modeled by super-operators, but no classical data is explicitly involved. An operational semantics of qCCS is presented in terms of (nonprobabilistic) labeled transition systems. Strong bisimulation between processes modeled in qCCS is defined, and its fundamental algebraic properties are established, including uniqueness of the solutions of recursive equations. To model sequential computation in qCCS, a reduction relation between processes is defined. By combining reduction relation and strong bisimulation we introduce the notion of strong reduction-bisimulation, which is a device for observing interaction of computation and communication in quantum systems. Finally, a notion of strong approximate bisimulation (equivalently, strong bisimulation distance) and its reduction counterpart are introduced. It is proved that both approximate bisimilarity and approximate reduction-bisimilarity are preserved by various constructors of quantum processes. This provides us with a formal tool for observing robustness of quantum processes against inaccuracy in the implementation of its elementary gates.
引用
收藏
页数:36
相关论文
共 21 条
[1]
[Anonymous], 2004, PROC QPL
[2]
BREUGEL FV, 2005, LECT NOTES COMPUTER, V3653, P141
[3]
Quantum copying: Beyond the no-cloning theorem [J].
Buzek, V ;
Hillery, M .
PHYSICAL REVIEW A, 1996, 54 (03) :1844-1852
[4]
D'Hondt E, 2005, THESIS VRIJE U BRUSS
[5]
COMMUNICATION BY ELECTRON-PARAMAGNETIC-RES DEVICES [J].
DIEKS, D .
PHYSICS LETTERS A, 1982, 92 (06) :271-272
[6]
Probabilistic bisimulations for quantum processes [J].
Feng, Yuan ;
Duan, Runyao ;
Ji, Zhengfeng ;
Ying, Mingsheng .
INFORMATION AND COMPUTATION, 2007, 205 (11) :1608-1639
[7]
Types and typechecking for communicating quantum processes [J].
Gay, Simon J. ;
Nagarajan, Rajagopal .
MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2006, 16 (03) :375-406
[8]
Communicating Quantum Processes [J].
Gay, SJ ;
Nagarajan, R .
ACM SIGPLAN NOTICES, 2005, 40 (01) :145-157
[9]
Jorrand P, 2005, LECT NOTES COMPUT SC, V3566, P1
[10]
JORRAND P, 2005, P 1 ACM C COMP FRONT, P111