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

nite automata with quantum and classical states

Alex B. Grilo, Arnaldo Vieira Moura

Published Jan 1, 2012• 0 citations
OpenAlex

Abstract

In order to discover how Quantum Mechanics would improve the power of computational devices, Quantum Computation was proposed by Feynman [6] in 1982 and since then some important breakthroughs in this area were achieved. The two main models, Quantum Turing Machines [4] and Quantum Circuits [5], allowed computer scientists, mathematicians and physicists to develop algorithms that extract computational power from the quantum structure of matter and compare their eciency with the classical ones. The most expressive results were Shor’s Algorithm [19], that factorizes integers in polynomial time, and Grover’s Algorithm [8], that presents a quadratic speedup for unordered database search problem. Within this context, the topic of Quantum Automata was proposed to study the inuence of Quantum Mechanics in simpler computational models. Several quantum counterparts of classical automata were proposed, whose dierences usually involve characteristics of the tape head and interaction with external elements, such as quantum and classical states and pushdown stacks. In this work, we consider two-way

Related papers

Computational Power of the Quantum Turing Automata

Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri +1 more

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future

•Apr 1, 2007•0 citations

Quantum Computing

Oscar Humberto Montiel Ross, Roberto Sepulveda

In the twenty-fi rst century, many signifi cant developments in science and engineering have been achieved through interdisciplinary research. Quantum computing (QC) is about computing with quantum systems, called quantum computers. A quantum computer is a computational device that makes use of the quantum mechanics (QM) phenomena such as entanglement, superposition and interference to perform operations on data. Quantum computers are different from classical binary digital computers since they work with quantum bits. The theoretical model is the quantum turing machine (QTM) which is a normal turing machine (TM) with quantum parallelism. Richard Feynman introduced this fi eld for the fi rst time in the 80’s (Feynman 1982) since he observed that certain quantum-mechanical effects cannot be simulated in an effi cient way using a classical computer. Such observation let to speculate that using quantum effects may become more effi cient computing. The interest grew up in 1994 when Peter Shor published the paper entitled “Algorithms for Quantum Computation : Discrete Logarithms and Factoring” (Shor 1994) where he described polynomial time quantum algorithms for fi nding discrete logarithms and factoring integers.

CRC Press eBooks•Jan 9, 2014•0 citations

Superiority of one-way and realtime quantum machines and new directions

Abuzer Yakaryılmaz

In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.

arXiv:1102.3093•NCMA•Feb 15, 2011•2 citations

Quantum vs. classical pushdown automata in exact computation

Yumiko Murakami

Since some quantum algorithms were introduced by Shor [1] or by Grover [2], much attention has been given to the field of quantum computation.The quantum computation is so useful for solving certain problems, however, the classical computation is more powerful in some cases.Thus, it is significant to compare the ability of quantum computation with the ability of classical counterpart, based on simple computation models, like automata.In this paper, we focus on the quantum pushdown automata, QPAs, which was defined by Golovkins in 2000 [4].It is shown that the class of languages recognized by QPAs contains the class of languages recognized by finite automata.However, no one knows the relationships between the cognitive ablity of QPAs and the classical counterparts.We make a proposition in this paper, the QPAs that deterministically solve a certain problem, which cannot be solved by deterministic pushdown automata.

•Mar 24, 2004•0 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

Quantum Pushdown Automata with Classical Stack and Tape Head.

Jismy Joseph, K. S. Dersanambika

International Journal of Software and Informatics•Jan 1, 2014•0 citations
In order to discover how Quantum Mechanics would improve the power of computational devices, Quantum Computation was proposed by Feynman [6] in 1982 and since then some important breakthroughs in this area were achieved. The two main models, Quantum Turing Machines [4] and Quantum Circuits [5], allowed computer scientists, mathematicians and physicists to develop algorithms that extract computational power from the quantum structure of matter and compare their eciency with the classical ones. The most expressive results were Shor’s Algorithm [19], that factorizes integers in polynomial time, and Grover’s Algorithm [8], that presents a quadratic speedup for unordered database search problem. Within this context, the topic of Quantum Automata was proposed to study the inuence of Quantum Mechanics in simpler computational models. Several quantum counterparts of classical automata were proposed, whose dierences usually involve characteristics of the tape head and interaction with external elements, such as quantum and classical states and pushdown stacks. In this work, we consider two-way
Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future
In the twenty-fi rst century, many signifi cant developments in science and engineering have been achieved through interdisciplinary research. Quantum computing (QC) is about computing with quantum systems, called quantum computers. A quantum computer is a computational device that makes use of the quantum mechanics (QM) phenomena such as entanglement, superposition and interference to perform operations on data. Quantum computers are different from classical binary digital computers since they work with quantum bits. The theoretical model is the quantum turing machine (QTM) which is a normal turing machine (TM) with quantum parallelism. Richard Feynman introduced this fi eld for the fi rst time in the 80’s (Feynman 1982) since he observed that certain quantum-mechanical effects cannot be simulated in an effi cient way using a classical computer. Such observation let to speculate that using quantum effects may become more effi cient computing. The interest grew up in 1994 when Peter Shor published the paper entitled “Algorithms for Quantum Computation : Discrete Logarithms and Factoring” (Shor 1994) where he described polynomial time quantum algorithms for fi nding discrete logarithms and factoring integers.
In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.
Since some quantum algorithms were introduced by Shor [1] or by Grover [2], much attention has been given to the field of quantum computation.The quantum computation is so useful for solving certain problems, however, the classical computation is more powerful in some cases.Thus, it is significant to compare the ability of quantum computation with the ability of classical counterpart, based on simple computation models, like automata.In this paper, we focus on the quantum pushdown automata, QPAs, which was defined by Golovkins in 2000 [4].It is shown that the class of languages recognized by QPAs contains the class of languages recognized by finite automata.However, no one knows the relationships between the cognitive ablity of QPAs and the classical counterparts.We make a proposition in this paper, the QPAs that deterministically solve a certain problem, which cannot be solved by deterministic pushdown automata.
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.