Efficient tests for equivalence of hidden Markov processes and quantum random walks

Abstract

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 $\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.

16 pages, requires llncs.cls

References in corpus (2)

• Quantum Random Walks Hit Exponentially Faster
• Mixing Times in Quantum Walks on the Hypercube

Cited by in corpus (6)

• Algebraic Reduction of Hidden Markov Models
• Generic identification of binary-valued hidden Markov processes
• Model Reduction for Quantum Systems: Discrete-time Quantum Walks and Open Markov Dynamics
• Entropy rate calculations of algebraic measures
• Markovian Statistics on Evolving Systems
• On Hidden States in Quantum Random Walks