While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equiva
lence of two HMP parametrizations $cM_1,cM_2$ resp. two QRW parametrizations $cQ_1,cQ_2$ in time $O(|S|max(N_1,N_2)^{4})$, where $N_1,N_2$ are the number of hidden states in $cM_1,cM_2$ resp. the dimension of the state spaces associated with $cQ_1,cQ_2$, and $S$ is the set of output symbols. Previously available algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subroutines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.
While the standard approach to quantum systems studies length preserving linear transformations of wave functions, the Markov picture focuses on trace preserving operators on the space of Hermitian (self-adjoint) matrices. The Markov approach extends
the standard one and provides a refined analysis of measurements and quantum Markov chains. In particular, Bells inequality becomes structurally clear. It turns out that hidden state models are natural in the Markov context. In particular, a violation of Bells inequality is seen to be compatible with the existence of hidden states. The Markov model moreover clarifies the role of the negative probabilities in Feynmans analysis of the EPR paradox.
