Physics – Quantum Physics
Scientific paper
2006-04-12
Physics
Quantum Physics
22 pages; some results have been added, while some proofs have been abbreviated
Scientific paper
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.
Li Lvzhou
Qiu Daowen
No associations
LandOfFree
A Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines 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 A Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-225818