Abstract Quantum automata can solve certain problems with a smaller state space than classical automata. We developed a quantum finite automaton using ternary rotation quantum gates and the Chrestenson family of ternary quantum gates. The main idea of this paper is to show how to combine rotation ternary quantum circuit-based Quantum Finite Automaton and quantum reversible circuit-based Deterministic Finite Automaton to build a more powerful machine. The combined machine can enable more complex language and pattern recognition. The developed quantum finite automaton and resulting combined machine can be used for robotics applications such as language, gesture, and motion recognition.
Abstract Quantum automata can solve certain problems with a smaller state space than classical automata. We developed a quantum finite automaton using ternary rotation quantum gates and the Chrestenson family of ternary quantum gates. The main idea of this paper is to show how to combine rotation ternary quantum circuit-based Quantum Finite Automaton and quantum reversible circuit-based Deterministic Finite Automaton to build a more powerful machine. The combined machine can enable more complex language and pattern recognition. The developed quantum finite automaton and resulting combined machine can be used for robotics applications such as language, gesture, and motion recognition.
This dissertation introduces a new type of quantum automata, their encoding and circuit realization. I concentrate on possible applications in robotics. Several methods and application of quantum automata and quantum circuit-based controllers for elementary robotic systems, with a focus on humanoid robot motion, emotion, and behavior generation are illustrated in detail. The research introduces several novel methodologies that bridge quantum computing principles with robotic control, aiming to overcome the limitations of classical deterministic and probabilistic approaches. The dissertation first presents a quantum-circuit-based framework for generating non-repetitive and expressive (e)motions in a humanoid robot actor, using superposition and entanglement to produce families of synchronized yet probabilistic behaviors. It then introduces a flowchart-based synthesis method for quantum automata using one-hot encoding, which significantly reduces quantum circuit cost by leveraging EXOR-based logic and restricting gate sets to NOT, CNOT, and Toffoli gates. Finally, the work expands into ternary quantum logic, developing hybrid quantum finite automata (QFA) using Chrestenson-family gates and uniformization ternary quantum gates, enabling more efficient pattern and language recognition with smaller state spaces. The key contributions of this dissertation are multifold. First, it presents the first practical implementation of a quantum-controlled humanoid robot for theatrical performance, demonstrating visually distinct, expressive, and entertaining behaviors that extend beyond the capabilities of classical control systems. Second, it introduces a direct synthesis methodology for quantum sequential circuits derived from high-level flowcharts, achieving up to a 95% reduction in quantum cost compared to existing design approaches. Third, the dissertation develops the generalized hybrid quantum finite automata (GHQFA), integrating ternary quantum logic with classical automata to enable complex pattern recognition and robotic gesture interpretation while requiring minimal quantum cost. Although the illustrative example of a robot car simulated in the CoppeliaSim environment is very simple based only on Chrestenson gates, the integration of all methods proposed herein establishes a foundation for controlling highly expressive humanoid robotic systems. Furthermore, the proposed models can be applied to real-world robotic tasks, including gesture recognition, motion synthesis, and adaptive behavior generation, with validation through both physical robotic performances and simulation studies. Finally, this work introduces an r-of-n encoding method that can enable to encode large machines for quantum circuits and can be integrated with the entanglement and superposition methods presented in this dissertation. This dissertation lays the groundwork for scalable and practical quantum-robotic systems, offering a pathway toward more intelligent, adaptive, and engaging robotic agents through quantum-enhanced control architectures.
In the contemporary era we dwell in, every now and then, new technologies are developed by master brains such as researchers and scientists. This also paves the way to discover replacements to classical computers. One such progression among the great inventions is the essence of quantum computing. They are brought to light for the purpose of solving problems and scenarios solved by classical computers but in a more effective way and in the least span of time. The study of quantum computing focuses on finding new ways to compute by using quantum physics phenomena. A qubit, in contrast to a typical computer bit, can be either 0 or 1, or it can be a superposition of both 0 and 1. Quantum theory commemorates with automata theory, thereby formulating quantum finite automata. Quantum finite automaton, or basically a deterministic finite automaton, is one of the simplest models of computation, which is an input-driven model, which takes an input, and according to the input, we just read the machine, and it changes its state. This proves that any quantum finite automata are completely capable of recognizing languages like Tally with given cut point too. Such languages recognized by a cut point, by quantum finite automata, are called stochastic languages. It further collaborates with the chemical industry with its qubit power over molecular collide, interactive models, and collaborative string processing using nonregular languages.
There are several papers that define quantum finite automaton analogous to classical finite automaton. Some papers describe the power of quantum automaton. In general, in quantum automata unitary matrices are associated to input symbols. Even though quantum circuits (or unitary matrices) are shown in specific cases, there is no general method given to construct a circuit or unitary matrix is found in the literature. This research focuses on construction of unitary matrices for each input symbol from the classical definition of a Deterministic Finite State Machine (DFSM). An algorithm is developed to associate a quantum circuit to an input symbol which considered as a mapping of classical DFSM states. IBM quantum composer is used to design circuits and build examples.
Quantum finite automata were introduced by C.Moore and J.P.Crutchfield in [MC 97] and by A.Kondacs and J.Watrous in [KW 97]. This notion is not a generalization of the deterministic finite automata, but rather a generalization of deterministic reversible (permutation) automata. In [AF 98] A.Ambainis and R.Freivalds raised the question what kind of probabilistic automata can be viewed as a special case of quantum finite automata. To answer that question and study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We give the necessary condition for a language to be recognized by PRA. We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. In these thesis we regard quantum automata, probabilistic reversible and deterministic reversible automata as reversible automata. At least two non-equivalent definitions of language recognition are used for one-way reversible finite automata in various papers. Both of these definitions have their own advantages and disadvantages, summarized in our classification of one-way reversible automata. Further, we introduce a notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite multitape automaton but not by deterministic finite multitape automata. Additionally we discover unexpected probabilistic automata recognizing complicated languages. Finally, we revise the concept of quantum pushdown automata (QPA), first introduced by C.Moore and J.P.Cruthchfield in [MC 97]. We give the definition of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [KW 97]. It is established that the unitary criteria of QPA are not equivalent to the corresponding unitary criteria of quantum Turing machines [BV 97]. We show that QPA can recognize every regular language. We also present some simple non-context-free languages recognized by QPA (hence not recognizable by deterministic and nondeterministic pushdown automata).
Herein we survey the main results concerning quantum automata and machines with classical control. These machines were originally proposed by Sernadas et al in [37], during the FCT QuantLog project. First, we focus on the expressivity of quantum automata with both quantum and classical states. We revise the result obtained in [32] where it was proved that such automata are able to recognise, with exponentially less states than deterministic finite automata, a family of regular languages that cannot be recognised by other types of quantum automata. Finally, we revise the concept of quantum Turing machine with classical control introduced in [25]. The novelty of these machines consists in the fact that their termination problem is completely deterministic, in opposition to other notions in the literature. Concretely, we revisit the result that such machines fulfil the s-m-n property, while keeping the expressivity of a quantum model for computation.
This paper introduces a variant of two-way quantum finite automata named two-way multihead quantum finite automata. A two-way quantum finite automaton is more powerful than classical two-way finite automata. However, the generalizations of two-way quantum finite automata have not been defined so far as compared to one-way quantum finite automata model. We have investigated the newly introduced automata from two aspects: the language recognition capability and its comparison with classical and quantum counterparts. It has been proved that a language which cannot be recognized by any one-way and multi-letter quantum finite automata can be recognized by two-way quantum finite automata. Further, it has been shown that a language which cannot be recognized by two-way quantum finite automata can be recognized by two-way multihead quantum finite automata with two heads. Furthermore, it has been investigated that quantum variant of two-way deterministic multihead finite automata takes less number of heads to recognize a language containing of all words whose length is a prime number.