Reachability Analysis of Recursive Quantum Markov Chains

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science, 2013, 8087 (1), pp. 385 - 396
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013002061OK.pdf258.85 kB
Adobe PDF
We introduce the notion of recursive quantum Markov chain (RQMC) for analysing recursive quantum programs with procedure calls. RQMCs are natural extension of Etessami and Yannakakiss recursive Markov chains where the probabilities along transitions are replaced by completely positive and trace-nonincreasing super-operators on a state Hilbert space of a quantum system. We study the reachability problem for RQMCs and establish a reduction from it to computing the least solution of a system of polynomial equations in the semiring of super-operators. It is shown that for an important subclass of RQMCs, namely linear RQMCs, the reachability problem can be solved in polynomial time. For general case, technique of Newtonian program analysis recently developed by Esparza, Kiefer and Luttenberger is employed to approximate reachability super-operators. A polynomial time algorithm that computes the support subspaces of the reachability super-operators in general case is also proposed.
Please use this identifier to cite or link to this item: