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.
Quantum sequential machines (QSMs) are a quantum version of stochastic sequential machines (SSMs). Recently, we showed that two QSMs M_1 and M_2 with n_1 and n_2 states, respectively, are equivalent iff they are (n_1+n_2)^2--equivalent (Theoretical Computer Science 358 (2006) 65-74). However, using this result to check the equivalence likely needs exponential expected time. In this paper, we consider the time complexity of deciding the equivalence between QSMs and related problems. The main results are as follows: (1) We present a polynomial-time algorithm for deciding the equivalence between QSMs, and, if two QSMs are not equivalent, this algorithm will produce an input-output pair with length not more than (n_1+n_2)^2. (2) We improve the bound for the equivalence between QSMs from (n_1+n_2)^2 to n_1^2+n_2^2-1, by employing Moore and Crutchfield's method (Theoretical Computer Science 237 (2000) 275-306). (3) We give that two MO-1QFAs with n_1 and n_2 states, respectively, are equivalent iff they are (n_1+n_2)^2--equivalent, and further obtain a polynomial-time algorithm for deciding the equivalence between two MO-1QFAs. (4) We provide a counterexample showing that Koshiba's method to solve the problem of deciding the equivalence between MM-1QFAs may be not valid, and thus the problem is left open again.
[synopsis] In this paper, the Bethe-Peierls approximation of the Ising model is interpreted. It is an improvement over the Bragg-Williams approximation of the assumpion N _<++>/2/1γN=(N_+/N)^2 of a relation between N_<++> and N_+. In the Bethe-Peierls approximation we focus our attention on a sublattice composed of any lattice site plus its γ nearest neighbors. And we find a more accurate relation between N_<++> and N_+. P(S,n) is the probability that n of the nearest neighbors are in a spin-up state while the canter site has the spin state S. From the meaning given to P(S,n) it follows that {(1+L)/2}=N_+/N=Σ^^γ__ P(+1,n) and {(1+σ)/2}=N_<++>/(_γN/2)=(1/γ)Σ^^γ__ nP(+1,n). In our approximation we require that Σ^^γ__ P(+1,n)=(1/γ)x Σ^^γ__ n{P(+1,n)+P(-1,n)}. We assume that P(±1,n)=(1/q)_γC_ne^<1/(k_BT)(±2n±γ)>z^n. z={(1+ze^<2ε/k_BT>)/(z+e^<2ε/k_BT>)}^<γ-1>. L^^-={(z^x-1)/(z^x)+1}, σ^^-[2z^2/{(1+ze)^^<2ε/k_BT>)(1+z^x)}]-1, x≡γ/(γ-1). The internal energy of the Ising lattice in H=0 is U(0,T)=-(1/2)εγ(2σ^^--2L^^-+1). The Curie tempererature T_c is T_c=[(2ε/k_B)/log_e{γ/(γ-2)}] .