A note on quantum sequential machines

Quantum sequential machines (QSMs) are a quantum version of stochastic sequential machines (SSMs). Recently, we showed that two QSMs M1 and M2 with n1 and n2 states, respectively, are equivalent iff they are (n1+n2)2-equivalent [L.Z. Li, D.W. Qiu, Determination of equivalence between quantum sequential machines, Theoretical Computer Science 358 (2006) 65–74]. However, using this result to check the equivalence is likely to need exponential expected time. In this note, 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 (n1+n2)2. (2) We improve the bound for the equivalence between QSMs from (n1+n2)2 to , by employing Moore and Crutchfield’s method [C. Moore, J.P. Crutchfield, Quantum automata and quantum grammars, Theoretical Computer Science 237 (2000) 275–306. Also quant-ph/9707031, 1997]. In addition, by viewing MO-1QFAs as a special case of QSMs, we briefly discuss the equivalence between MO-1QFAs, where the method used and the result obtained are slightly different from those given by Koshiba [T. Koshiba, Polynomial-time algorithms for the equivalence for one-way quantum finite automata, in: Proceedings of the 12th International Symposium on Algorithms and Computation, ISAAC’2001, Christchurch, New Zealand, in: Lecture Notes in Computer Science, vol. 2223, Springer, Berlin, 2001, pp. 268–278].