Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

De Gruyter eBooks

Chapter 8 Quantum computing in automata theory

G. Ignisha Rajathi, R. Vedhapriyavadhana, R. Niranjana, N. Pooranam, R. Johny Elton

Published Aug 7, 2023• 2 citations
Publisher

Abstract

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.

DOI
10.1515/9783110791402-008

Related papers

Quantum automata and quantum computing

Marats Golovkins

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).

•Jan 1, 2002•0 citations

Quantum Computing

Suraj Ghadge

Abstract: Quantum computing is a new type of computing that uses the principles of quantum physics to perform calculations in ways that are not possible with traditional computers. Unlike classical computers, which process information using bits that are either 0 or 1, quantum computers use quantum bits (qubits) that can exist in multiple states at the same time. This ability allows quantum systems to solve certain complex problems much faster than classical machines. This paper presents a simple and human-centered explanation of quantum computing, focusing on how it works, why it matters, and how it can be applied in real-world situations. The study discusses key concepts such as superposition, entanglement, and quantum gates using easy-to-understand language. It also explores practical applications including cryptography, optimization, drug discovery, and material simulation. In addition, this paper examines the current challenges in quantum computing, such as hardware instability, error correction, limited qubit scalability, and high implementation cost. A conceptual hybrid classical–quantum system model is proposed to show how quantum and classical computers can work together to solve complex problems more efficiently. The goal of this research is to make quantum computing more understandable to students, educators, and decision-makers, and to encourage early awareness and responsible development of this powerful technology. Keywords — quantum computing, qubit, superposition, entanglement, quantum gate, error correction, hybrid computing

International Scientific Journal of Engineering and Management•Dec 17, 2025•0 citations

Automata and quantum computing

Andris Ambainis, Abuzer Yakaryılmaz

Quantum computing is a new model of computation, based on quantum physics.Quantum computers can be exponentially faster than conventional computers for problems such as factoring.Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied.In this paper, we survey various models of quantum finite automata and their properties.We also provide some open questions and new directions for researchers.

•Aug 6, 2021•2 citations

Chapter 12 Quantum computing: application-specific need of the hour

R. Vedhapriyavadhana, G. Ignisha Rajathi, R. Niranjana +1 more

In this tech-savvy era, as new technologies are developed every day by researchers and scientists, this also paves way to discover replacements to classical computers. One such advancement is the uncovering of quantum computing. They are brought up to light for the purpose of solving problems and scenarios solved by classical computers but in a more effective way and at least a span of time. The study of quantum computing focuses on finding new ways to compute by utilizing 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 serving as the base to operate supercomputers is based on two aspects of quantum physics: superposition and entanglement. This quantum computing plays extraordinary roles in different zones of applications such as weather forecasting, logistics, finance, healthcare, and cybersecurity. They are discussed with clarity in this chapter by throwing bright light on these important inevitable topics.

De Gruyter eBooks•Aug 7, 2023•1 citation

Automata and quantum computing

Andris Ambainis, Abuzer Yakaryılmaz

Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity

EMS Press eBooks•Sep 13, 2021•33 citations

Superiority of one-way and realtime quantum machines

Abuzer Yakaryılmaz

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.

RAIRO - Theoretical Informatics and Applications•Oct 1, 2012•20 citations
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.
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).
Abstract: Quantum computing is a new type of computing that uses the principles of quantum physics to perform calculations in ways that are not possible with traditional computers. Unlike classical computers, which process information using bits that are either 0 or 1, quantum computers use quantum bits (qubits) that can exist in multiple states at the same time. This ability allows quantum systems to solve certain complex problems much faster than classical machines. This paper presents a simple and human-centered explanation of quantum computing, focusing on how it works, why it matters, and how it can be applied in real-world situations. The study discusses key concepts such as superposition, entanglement, and quantum gates using easy-to-understand language. It also explores practical applications including cryptography, optimization, drug discovery, and material simulation. In addition, this paper examines the current challenges in quantum computing, such as hardware instability, error correction, limited qubit scalability, and high implementation cost. A conceptual hybrid classical–quantum system model is proposed to show how quantum and classical computers can work together to solve complex problems more efficiently. The goal of this research is to make quantum computing more understandable to students, educators, and decision-makers, and to encourage early awareness and responsible development of this powerful technology. Keywords — quantum computing, qubit, superposition, entanglement, quantum gate, error correction, hybrid computing
In this tech-savvy era, as new technologies are developed every day by researchers and scientists, this also paves way to discover replacements to classical computers. One such advancement is the uncovering of quantum computing. They are brought up to light for the purpose of solving problems and scenarios solved by classical computers but in a more effective way and at least a span of time. The study of quantum computing focuses on finding new ways to compute by utilizing 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 serving as the base to operate supercomputers is based on two aspects of quantum physics: superposition and entanglement. This quantum computing plays extraordinary roles in different zones of applications such as weather forecasting, logistics, finance, healthcare, and cybersecurity. They are discussed with clarity in this chapter by throwing bright light on these important inevitable topics.
Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity
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.