Journal
INFORMATION PROCESSING LETTERS
Volume 112, Issue 7, Pages 289-291Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2012.01.001
Keywords
Computational complexity; Exact quantum computation; Promise problems; Succinctness; Quantum finite automaton; Classical finite automaton
Categories
Funding
- ESF [1DP/1.1.1.2.0/09/APIA/VIAA/044]
- FP7 Marie Curie International Reintegration [PIRG02-GA-2007-224886]
- FP7 FET-Open project QCS
- Scientific and Technological Research Council of Turkey (TUBITAK) [108E142]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
