Superiority of exact quantum automata for promise problems

被引：41
作者：
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
    Ambainis, A
    Freivalds, R
    [J]. 39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, : 332 - 341
  • [2] Quantum lower bounds by polynomials
    Beals, R
    Buhrman, H
    Cleve, R
    Mosca, M
    de Wolf, R
    [J]. 39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, : 352 - 361
  • [3] Quantum complexity theory
    Bernstein, E
    Vazirani, U
    [J]. 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
    Buhrman, H
    de Wolf, R
    [J]. 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