2011/01/31 by Andris Ambainis, Abuzer Yakaryılmaz, Abuzer Yakaryilmaz · 1 citation
Computer Science · Physics and Astronomy · #cs.CC #cs.FL #quant-ph
paper · pdf · doi:10.1016/j.ipl.2012.01.001
published as Information Processing Letters, Volume 112, Issue 7, 31 March 2012, Pages 289-291 · A completely new version. 6 pages. (The previous version contains some errata.)
arxiv created 2011/08/16 · crossref created 2012/01/05 · crossref issued 2012/03/01 · crossref published 2012/03/01 · crossref published-print 2012/03/01 · arxiv updated 2014/01/29 · crossref deposited 2025/03/17 · crossref indexed 2026/08/01
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 automata operating in realtime mode, whereas the size of the corresponding classical automata grow without bound.