dorsal/arxiv
View SchemaA Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines
| Authors | Lvzhou Li, Daowen Qiu |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0604085 |
| URL | https://arxiv.org/abs/quant-ph/0604085 |
Abstract
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.
{
"annotation_id": "bd407388-bfa2-4b98-b0a8-1df98cc8b54f",
"date_created": "2026-03-02T18:02:27.443000Z",
"date_modified": "2026-03-02T18:02:27.443000Z",
"file_hash": "db3419e1880abd32b4677209ed3585be9e626210bdf999c47f3a4cd2e3b5623d",
"private": false,
"record": {
"abstract": "Quantum sequential machines (QSMs) are a quantum version of stochastic\nsequential machines (SSMs). Recently, we showed that two QSMs M_1 and M_2 with\nn_1 and n_2 states, respectively, are equivalent iff they are\n(n_1+n_2)^2--equivalent (Theoretical Computer Science 358 (2006) 65-74).\nHowever, using this result to check the equivalence likely needs exponential\nexpected time. In this paper, we consider the time complexity of deciding the\nequivalence between QSMs and related problems. The main results are as follows:\n(1) We present a polynomial-time algorithm for deciding the equivalence between\nQSMs, and, if two QSMs are not equivalent, this algorithm will produce an\ninput-output pair with length not more than (n_1+n_2)^2. (2) We improve the\nbound for the equivalence between QSMs from (n_1+n_2)^2 to n_1^2+n_2^2-1, by\nemploying Moore and Crutchfield\u0027s method (Theoretical Computer Science\n 237 (2000) 275-306). (3) We give that two MO-1QFAs with n_1 and n_2 states,\nrespectively, are equivalent iff they are (n_1+n_2)^2--equivalent, and further\nobtain a polynomial-time algorithm for deciding the equivalence between two\nMO-1QFAs. (4) We provide a counterexample showing that Koshiba\u0027s method to\nsolve the problem of deciding the equivalence between MM-1QFAs may be not\nvalid, and thus the problem is left open again.",
"arxiv_id": "quant-ph/0604085",
"authors": [
"Lvzhou Li",
"Daowen Qiu"
],
"categories": [
"quant-ph"
],
"title": "A Polynomial-Time Algorithm for the Equivalence between Quantum Sequential Machines",
"url": "https://arxiv.org/abs/quant-ph/0604085"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "3c81c341-805b-47e3-af20-cc135144abbb",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}