Abstract
In this paper, we study a model of quantum Markov chains that is a quantum analogue of Markov chains and is obtained by replacing probabilities in transition matrices with quantum operations. We show that this model is very suited to describe hybrid systems that consist of a quantum component and a classical one, although it has the same expressive power as another quantum Markov model proposed in the literature. Indeed, hybrid systems are often encountered in quantum information processing; for example, both quantum programs and quantum protocols can be regarded as hybrid systems. Thus, we further propose a model called hybrid quantum automata (HQA) that can be used to describe these hybrid systems that receive inputs (actions) from the outer world. We show the language equivalence problem of HQA is decidable in polynomial time. Furthermore, we apply this result to the trace equivalence problem of quantum Markov chains, and thus it is also decidable in polynomial time. Finally, we discuss model checking linear-time properties of quantum Markov chains, and show the quantitative analysis of regular safety properties can be addressed successfully.
Introduction
In classical computing, Markov Chains are essential for probabilistic modeling. As quantum computing matures, a "quantum analogue" is required. However, real-world quantum systems are typically hybrid: a classical control flow manages quantum data. For instance, the BB84 communication protocol involves classical decisions based on quantum measurements. Existing models often struggle to capture these hybrid interactions or lack efficient verification methods for equivalence and safety.
The Hybrid Quantum Markov Chain (hqMC)
The authors propose the Hybrid Quantum Markov Chain (hqMC) as a natural language for quantum programming. Unlike standard Markov chains where transitions are probabilistic, an hqMC transitions between classical states via quantum operations (super-operators) acting on a quantum state.
This model mirrors the "quantum data with classical control" paradigm found in languages like QCL or Quipper. The paper proves that while hqMCs are structurally distinct from standard quantum Markov chains, they possess the same expressive power.
Verification and Hybrid Quantum Automata
To address verification, the researchers introduce Hybrid Quantum Automata (HQA), extending hqMCs to handle external inputs. A key challenge in quantum verification is that standard graph-theoretical approaches fail; a path might exist in a graph, but the sequence of quantum operations could result in a "zero" operator, making the path physically impossible.
The authors overcome this by reducing HQAs to "Bilinear Machines," allowing the use of efficient classical algorithms. They demonstrate that the language equivalence problem for HQAs is decidable in polynomial time—specifically $O(|\Sigma|(n_1 + n_2)^3)$, where $\Sigma$ is the input alphabet.
Key Results and Model Checking
The paper establishes several critical results for quantum system verification:
- Trace Equivalence: Determining if two Markov chains produce identical observable patterns over time is decidable in polynomial time.
- Safety Verification: Quantitative analysis of regular safety properties (e.g., ensuring a "bad" state's probability remains below a threshold) is reduced to a solvable reachability problem using linear equations. This is achieved via a product construction between the quantum system and a classical monitor (DFA).
Conclusion and Future Directions
While the paper successfully addresses safety properties in finite time, infinite-time behaviors ($\omega$-regular properties) remain a challenge. Furthermore, the current model is discrete; extending these verification techniques to continuous-time quantum evolutions is a primary goal for future research.
Summary updated