Promise problems solved by quantum and classical finite automata

Abstract

The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose of this paper is to explore the promise problems accepted by classical, quantum and also semi-quantum finite automata. More specifically, we first introduce two acceptance modes of promise problems, recognizability and solvability, and explore their basic properties. Afterwards, we show several results concerning descriptional complexity on promise problems. In particular, we prove: (1) there is a promise problem that can be recognized exactly by measure-once one-way quantum finite automata (MO-1QFA), but no deterministic finite automata (DFA) can recognize it; (2) there is a promise problem that can be solved with error probability $\epsilon \le 1/3$ by one-way finite automaton with quantum and classical states (1QCFA), but no one-way probability finite automaton (PFA) can solve it with error probability $\epsilon \le 1/3$; and especially, (3) there are promise problems $A(p)$ with prime $p$ that can be solved {\em with any error probability} by MO-1QFA with only two quantum basis states, but they can not be solved exactly by any MO-1QFA with two quantum basis states; in contrast, the minimal PFA solving $A(p)$ with any error probability (usually smaller than $1/2$) has $p$ states. Finally, we mention a number of problems related to promise for further study.

Substantial changes are made. Some new resutls are added

References in corpus (7)

• Superiority of exact quantum automata for promise problems
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Generalizations of the distributed Deutsch-Jozsa promise problem
• On hybrid models of quantum finite automata
• Potential of quantum finite automata with exact acceptance
• Implications of quantum automata for contextuality
• From Quantum Query Complexity to State Complexity