Decidable and undecidable problems about quantum automata

被引：43

作者：

Blondel, VD ^{[1
]}

Jeandel, E

Koiran, P

Portier, N

机构：

[1] Catholic Univ Louvain, Dept Engn Math, Louvain, Belgium

[2] Ecole Normale Super Lyon, Lab Informat Parallelisme, Lyon, France

来源：

SIAM JOURNAL ON COMPUTING | 2005年 / 34卷 / 06期

关键词：

quantum automata; probabilistic automata; undecidable problems; algebraic groups;

D O I：

10.1137/S0097539703425861

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata, for which it is known that strict and nonstrict thresholds both lead to undecidable problems.

引用

页码：1464 / 1473

页数：10

共 25 条

[1]

Amano M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P368, DOI 10.1145/301250.301344

[2] ELEMENTARY GATES FOR QUANTUM COMPUTATION [J].

BARENCO, A ;

BENNETT, CH ;

CLEVE, R ;

DIVINCENZO, DP ;

MARGOLUS, N ;

SHOR, P ;

SLEATOR, T ;

SMOLIN, JA ;

WEINFURTER, H .

PHYSICAL REVIEW A, 1995, 52 (05) :3457-3467

[3] On the combinatorial and algebraic complexity of quantifier elimination [J].

Basu, S ;

Pollack, R ;

Roy, MF .

JOURNAL OF THE ACM, 1996, 43 (06) :1002-1045

[4]

Bertoni A., 1975, GI 4 JAHRESTAGUNG LE, V26, P107

[5]

Bertoni A., 1977, Automata, Languages and Programming, V52, P87

[6] When is a pair of matrices mortal? [J].

Blondel, VD ;

Tsitsiklis, JN .

INFORMATION PROCESSING LETTERS, 1997, 63 (05) :283-286

[7] Undecidable problems for probabilistic automata of fixed dimension [J].

Blondel, VD ;

Canterini, V .

THEORY OF COMPUTING SYSTEMS, 2003, 36 (03) :231-245

[8] Characterizations of 1-way quantum finite automata [J].

Brodsky, A ;

Pippenger, N .

SIAM JOURNAL ON COMPUTING, 2002, 31 (05) :1456-1478

[9]

Cox D., 1992, UNDERGRAD TEXTS MATH

[10] Quantum automata and algebraic groups [J].

Derksen, H ;

Jeandel, E ;

Koiran, P .

JOURNAL OF SYMBOLIC COMPUTATION, 2005, 39 (3-4) :357-371

← 1 2 3 →