Superiority of exact quantum automata for promise problems

被引：42
作者：
Ambainis, Andris [1 ]
Yakaryilmaz, Abuzer [1 ]
机构：
[1] Univ Latvia, Fac Comp, LV-1586 Riga, Latvia
来源：
INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 07期
关键词：
Computational complexity; Exact quantum computation; Promise problems; Succinctness; Quantum finite automaton; Classical finite automaton;
D O I：
10.1016/j.ipl.2012.01.001
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automaton operating in realtime mode, whereas the size of the corresponding classical automata grows without bound. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：289 / 291
页数：3
相关论文
共 17 条
[1]   1-way quantum finite automata: strengths, weaknesses and generalizations [J].
Ambainis, A ;
Freivalds, R .
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :332-341
[2]   Quantum lower bounds by polynomials [J].
Beals, R ;
Buhrman, H ;
Cleve, R ;
Mosca, M ;
de Wolf, R .
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :352-361
[3]   Quantum complexity theory [J].
Bernstein, E ;
Vazirani, U .
SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1411-1473
[4]  
Bertoni A, 2003, LECT NOTES COMPUT SC, V2710, P1
[5]  
Brassard G., 1997, ISR S THEOR COMP SYS, P12
[6]   Quantum zero-error algorithms cannot be composed [J].
Buhrman, H ;
de Wolf, R .
INFORMATION PROCESSING LETTERS, 2003, 87 (02) :79-84
[7]  
Buhrman H., 1999, FOCS P 40 IEEE S FDN, P358
[8]  
Ciamarra M. P., 2001, Fundamentals of Computation Theory. 13th International Symposium, FCT 2001. Proceedings (Lecture Notes in Computer Science Vol.2138), P376
[9]  
Freivalds R., 2009, CIAA 09, P208
[10]  
Hirvensalo Mika, 2010, International Journal of Natural Computing Research, V1, P70, DOI 10.4018/jncr.2010010104
12