Efficient Tests for Equivalence of Hidden Markov Processes and Quantum Random Walks
Ulrich Faigle, Alexander Schönhuth · IEEE Transactions on Information Theory · 2011
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 equivalence of two HMP parametrizations M1, M2resp. two QRW parametrizations Q1, Q2in time O(|Σ| max(N1, N2)4), where N1,N2are the number of hidden states in M1, M2resp. the dimension of the state spaces associated with Q1, Q2, and Σ is the set of output symbols. Previously avail able 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 subrou tines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.