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.
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.
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
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
Quantum computing is concerned with computer technology based on the principles of quantum mechanics, with operations performed at the quantum level. Quantum computational models make it possible to analyze the resources required for computations. Quantum automata can be classified thusly: quantum finite automata, quantum sequential machine, quantum pushdown automata, quantum Turing machine and orthomodular lattice-valued automata. These models are useful for determining the expressive power and boundaries of various computational features. In light of the current state of quantum computation theory research, a systematic review of the literature seems timely. This article seeks to provide a comprehensive and systematic analysis of quantum finite automata models, quantum finite automata models with density operators and quantum finite automata models with classical states, interactive proof systems, quantum communication complexity and query complexity as described in the literature. The statistics of quantum finite automata related papers are shown and open problems are identified for more advanced research. The current status of quantum automata theory is distributed into various categories. This research work also highlights the previous research, current status and future directions of quantum automata models.
On the basis of its unrivalled potential to solve factorization problems and further application in cryptography, quantum computing is considered as one of the most promising computational models for the future. It provides a new angle for thinking of computation and a new approach for attack various computationally difficult problems. In this article, we give a comprehensive survey of developments in the last twenty years on quantum algorithms, quantum complexity, quantum programming theory, quantum circuits, and quantum cryptography that we hope will serve as references for researchers in related fields. We also outline various research directions and open problems in this area, with the hope of prompting further progress or even solutions.
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.
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.