2015/04/01 by Jozef Gruska, Daowen Qiu, Shenggen Zheng · 16 citations
paper · doi:10.1142/s0129054115500215
published in International Journal of Foundations of Computer Science 26(03), 381-398 (World Scientific Pub Co Pte Ltd)
crossref issued 2015/04/01 · crossref published 2015/04/01 · crossref published-print 2015/04/01 · crossref published-online 2015/07/06 · crossref created 2015/07/07 · crossref deposited 2022/05/17 · crossref indexed 2026/07/30
The potential of the exact quantum information processing is an interesting, important and intriguing issue. For examples, it has been believed that quantum tools can provide significant, that is larger than polynomial, advantages in the case of exact quantum computation only, or mainly, for problems with very special structures. We will show that this is not the case. In this paper the potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes [Formula: see text] of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states, can be very small (and constant) though it grows proportional to [Formula: see text] in the case deterministic finite automata (DFAs) of the same power are used. This is here demonstrated also for the case that the component languages of the promise problems solvable by DFAs are non-regular. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems.