Let
L>λ(A) and
L≥λ(A) be the languages recognized by {\em measure many 1-way quantum finite automata (MM-QFA)} (or,{\em enhanced 1-way quantum finite automata(EQFA)})
A with strict and non-strict cut-point
λ, respectively. We consider the language equivalence problem and show the following 1. both strict and non-strict language equivalence are undecidable; 2. we provide an another proof of the undecidability of non-strict and strict emptiness of MM-QFA and EQFA, and then reducing the language equivalence problem to emptiness problem; 3. lastly, we obtain some other properties which can be derived from the above results.
In this paper, we study some decision problems both for {\it multi-letter quantum finite automata} and {\it measure many multi-letter quantum finite automata}. We first show that given a
k1-letter quantum finite automaton
A1 and a
k2-letter quantum finite automaton
A2 over the same input alphabet
Σ, they are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
ni,
i=1,2, are the number of states in
Ai respectively, and
k=max{k1,k2}. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a
k1-letter measure many quantum finite automaton
A1 and a
k2-letter measure many quantum finite automaton
A2 are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
ni,
i=1,2, are the number of states in
Ai respectively, and
k=max{k1,k2}.
Next, we study the emptiness problem of those two kinds of quantum finite automata. We show that whether the language recognized by a
k-letter quantum finite automaton with non-strict cut-point is empty is undecidable, but we leave open the emptiness of language reorganized by a
k-letter quantum finite automaton with strict cutpoint. We also show that whether the languages recognized by a
k-letter measure many quantum finite automaton with both nonstrict and strict cutpoints are undecidable. And the direct consequences of the above outcomes are summarized in the paper.
Two-way finite automata with quantum and classical states (2QCFA’s), introduced by Ambainis and Watrous, extend deterministic two-way finite automata with a constant-size quantum register and provide a natural hybrid model of computation. In this paper, we introduce two-way nondeterministic finite automata with quantum and classical states (2QCNFA’s), extending this framework to the nondeterministic setting. We show that 2QCNFA’s are closed under union, intersection, and marked concatenation, and that they can recognize certain comparison languages whose status for 2QCFA’s remains open. We further initiate the study of decision problems for this model by proving that 2QCNFA’s can recognize the set of invalid computations of a deterministic Turing machine, which implies that the universality problem is undecidable. In addition, we investigate descriptional complexity, showing that there is no approximation algorithm for minimization between 2QCNFA’s and classical models such as DFA’s and context-free grammars, and that the corresponding trade-offs are non-recursive.
We develop a quantum algorithm to verify the correctness of systems modeled by nondeterministic finite-state automata-a problem that is computationally intractable on conventional computers. Specifically, our algorithm solves the language containment problem in three steps. First, we translate a nondeterministic finite-state automaton into a quantum finite state automaton (QFA) circuit. Second, the QFA is embedded into a larger circuit which generates a superposed set of all bounded strings that are marked to indicate whether they are accepted or not. Finally, we amplify the amplitudes of accepted strings so that they are measured more frequently. The last step may be done either by using Grover's algorithm, or by using FnR, a custom algorithm that we have developed for the cases where Grover's algorithm is not effective. Our work represents the first proposal to apply quantum computing to the problem of verifying conventional systems; our approach would facilitate software verification, program analysis, protocol design, and verification of circuits, among other applications.