Potential of quantum finite automata with exact acceptance

Abstract

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 $\{A^n{\}}_{n=1}^{\infty }$ 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 $n$ 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.

arXiv commentWe have improved the presentation of the paper. Accepted to International Journal of Foundation of Computer Science

References in corpus (14)

• Quantum Algorithms Revisited
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• Unbounded-error quantum computation with small space bounds
• Quantum vs. Classical Communication and Computation
• Superiority of exact quantum automata for promise problems
• Bounds for Small-Error and Zero-Error Quantum Algorithms
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• On the state complexity of semi-quantum finite automata
• Exact quantum query complexity of EXACT and THRESHOLD
• Implications of quantum automata for contextuality
• Exact quantum algorithms have advantage for almost all Boolean functions
• One-way finite automata with quantum and classical states
• State succinctness of two-way finite automata with quantum and classical states
• Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States

Cited by in corpus (5)

• Generalizations of the distributed Deutsch-Jozsa promise problem
• Quantum finite automata: A modern introduction
• Unary probabilistic and quantum automata on promise problems
• Exact quantum algorithms have advantage for almost all Boolean functions
• Promise problems solved by quantum and classical finite automata