In a recent paper we have described an optical implementation of a measure-once one-way quantum finite automaton recognizing a well-known family of unary periodic languages, accepting words not in the language with a given error probability. To process input words, the automaton exploits the degree of polarization of single photons and, to reduce the acceptance error probability, a technique of confidence amplification using the photon counts is implemented. In this paper, we show that the performance of this automaton may be further improved by using strategies that suitably consider both the orthogonal output polarizations of the photon. In our analysis, we also take into account how detector dark counts may affect the performance of the automaton.
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.
The 2-way quantum finite automaton introduced by Kondacs and Watrous [Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75] can accept nonregular languages with bounded error in polynomial time. If we restrict the head of the automaton to moving classically and to moving only in one direction, the acceptance power of this 1-way quantum finite automaton is reduced to a proper subset of the regular languages. In this paper we study two different models of 1-way quantum finite automata. The first model, termed measure-once quantum finite automata, was introduced by Moore and Crutchfield [Theoret. Comput. Sci., 237 (2000), pp. 275--306], and the second model, termed measure-many quantum finite automata, was introduced by Kondacs and Watrous [Proceedings of the38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75]. We characterize the measure-once model when it is restricted to accepting with bounded error and show that, without that restriction, it can solve the word problem over the free group. We also show that it can be simulated by a probabilistic finite automaton and describe an algorithm that determines if two measure-once automata are equivalent. We prove several closure properties of the classes of languages accepted by measure-many automata, including inverse homomorphisms, and provide a new necessary condition for a language to be accepted by the measure-many model with bounded error. Finally, we show that piecewise testable sets can be accepted with bounded error by a measure-many quantum finite automaton, introducing new construction techniques for quantum automata in the process.
The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with bounded error, the language
Leq={ambm:m∈N} in expected polynomial time and the language
Lpal={w∈{a,b}∗:w is a palindrome} in expected exponential time. We further demonstrate the power of 2QCFA by showing that they can recognize the word problems of many groups. In particular 2QCFA, with a single qubit and algebraic number transition amplitudes, can recognize, with bounded error, the word problem of any finitely generated virtually abelian group in expected polynomial time, as well as the word problems of a large class of linear groups in expected exponential time. This latter class (properly) includes all groups with context-free word problem. We also exhibit results for 2QCFA with any constant number of qubits. As a corollary, we obtain a direct improvement on the original Ambainis and Watrous result by showing that
Leq can be recognized by a 2QCFA with better parameters. As a further corollary, we show that 2QCFA can recognize certain non-context-free languages in expected polynomial time. In a companion paper, we prove matching lower bounds, thereby showing that the class of languages recognizable with bounded error by a 2QCFA in expected
subexponential time is properly contained in the class of languages recognizable with bounded error by a 2QCFA in expected
exponential time.
Quantum finite automata can be used for pattern recognition. Present implementations on actual quantum devices face decoherence issues, which compromise the quality of long strings computation. In this work, we focus on the Measure Once 1-way Quantum Finite Automata (MO1QFA) model for addressing the MOD^p problem, investigating how quantum errors may affect the quality of the computation in this model when implemented in IBM-Q superconducting environment. To improve the performance of the implementation, we use pulse-level programming for calibrating a fast single-qubit gate designed specifically for the automaton implementation. The demonstrations conducted on the Jakarta quantum computer show that using custom pulses significantly reduces errors during extended word computations. While realizing improvements in error variations and predictability -- with a fourfold reduction in circuit latency -- the proposed solution demonstrates a substantial increase in the supported computation length of the automaton. When considering thresholds of 10% and 20% in absolute errors of acceptance probabilities, the solution has the potential to increase the maximum word length by 12 and 7+ times, respectively, compared to the default Qiskit gate.