  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.
