On Quantum Pushdown Systems with Various Extensions

In this paper, we define the quantum analogues of the {\em probabilistic pushdown systems} and {\em Markov chains}, and further investigate whether it is necessary to define a quantum analogue of {\em probabilistic computational tree logic} to describe the branching-time properties of the {\em quantum Markov chain} defined in this paper. We study its model-checking question and show that the model-checking of {\em stateless quantum pushdown systems (qBPA)} against {\em probabilistic computational tree logic (PCTL)} is generally undecidable, with the immediate corollaries summarized. We define the notion of {\em probabilistic $\omega$-pushdown automaton} for the first time and study the model-checking question of {\em stateless probabilistic $\omega$-pushdown system ($\omega$-pBPA)} against $\omega$-PCTL (defined by Chatterjee et al. in \cite{CSH08}) and show that the model-checking of {\em stateless probabilistic $\omega$-pushdown systems ($\omega$-pBPA)} against $\omega$-PCTL is generally undecidable, with immediate consequences summarized. Our approach is to construct formulas of $\omega$-PCTL encoding the {\em Post Correspondence Problem} indirectly.