  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.
