Fri 7 February 2014, 16:30-18:00

Mingsheng Ying (University of Technology Sydney & Tsinghua University)
Reachability Analysis of Quantum Markov Chains

理学部7号館2階 214教室   Room 214, School of Science Bldg. No. 7

アクセス： https://www-mmm.is.s.u-tokyo.ac.jp/indexj.html （一番下）
Access: http://www-mmm.is.s.u-tokyo.ac.jp/ (see bottom)

The talk will be based on our Concur'12 and Concur'13 papers, which study verification of quantum systems, including quantum programs, modelled by quantum Markov chains (qMCs). We consider three kinds of long-term behaviour, namely reachability, repeated reachability and persistence, of qMCs. As a stepping-stone, we introduce the notion of bottom strongly connected component (BSCC) of a qMC and develop an algorithm for finding BSCC decompositions of the state space of a qMC. As the major contribution, several (classical) algorithms for computing the reachability, repeated reachability and persistence probabilities of a qMC are presented, and their complexities are analysed.