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

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

2008-08-20

arxiv.org/abs/0808.2833v5

Computer Science

Information Theory

16 pages, requires llncs.cls

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Efficient tests for equivalence of hidden Markov processes and quantum random walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient tests for equivalence of hidden Markov processes and quantum random walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient tests for equivalence of hidden Markov processes and quantum random walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-219079