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

APS

Computation in Finitary Quantum Processes

Karoline Wiesner, James P. Crutchfield

Published Mar 1, 2006• 4 citations
OpenAlex

Abstract

We introduce quantum finite-state generators as a first step toward completing a computational description of observing individual quantum systems over time. We develop the mathematical foundations of quantum finite-state machines and compare nondeterministic and deterministic versions to stochastic generators and recognizers, summarizing their relative computational power via a hierarchy of finitary process languages. Quantum finite-state generators are explored via several physical examples, including the iterated beam splitter, the quantum kicked top, and atoms in an ion trap--a special case of which implements the Deutsch quantum algorithm. We show that the behavior of these systems, and so their information processing capacity, depends sensitively on measurement protocol.

Related papers

Language Diversity of Measured Quantum Processes

Karoline Wiesner, James P. Crutchfield

The behavior of a quantum system depends on how it is measured. How much of what is observed comes from the structure of the quantum system itself and how much from the observer's choice of measurement? We explore these questions by analyzing the \emph{language diversity} of quantum finite-state generators. One result is a new way to distinguish quantum devices from their classical (stochastic) counterparts. While the diversity of languages generated by these two computational classes is the same in the case of periodic processes, quantum systems generally generate a wider range of languages than classical systems.

arXiv:quant-ph/0611203•Nov 19, 2006•4 citations

Chapter 8 Quantum computing in automata theory

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

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.

De Gruyter eBooks•Aug 7, 2023•2 citations

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

Infinite Correlation in Measured Quantum Processes

Karoline Wiesner, James P. Crutchfield

We show that quantum dynamical systems can exhibit infinite correlations in their behavior when repeatedly measured. We model quantum processes using quantum finite-state generators and take the stochastic language they generate as a representation of their behavior. We analyze two spin-1 quantum systems that differ only in how they are observed. The corresponding language generated has short-range correlation in one case and infinite correlation in the other.

arXiv:quant-ph/0611143•Nov 14, 2006•0 citations

AN OBSERVER-BASED DE-QUANTISATION OF DEUTSCH'S ALGORITHM

Cristian S. Calude, Matteo Cavaliere, Radu Mardare

Deutsch's problem is the simplest and most frequently examined example of computational problem used to demonstrate the superiority of quantum computing over classical computing. Deutsch's quantum algorithm has been claimed to be faster than any classical ones solving the same problem, only to be discovered later that this was not the case. Various de-quantised solutions for Deutsch's quantum algorithm—classical solutions which are as efficient as the quantum one—have been proposed in the literature. These solutions are based on the possibility of classically simulating "superpositions", a key ingredient of quantum algorithms, in particular, Deutsch's algorithm. The de-quantisation proposed in this note is based on a classical simulation of the quantum measurement achieved with a model of observed system. As in some previous de-quantisations of Deutsch's quantum algorithm, the resulting de-quantised algorithm is deterministic. Finally, we classify observers (as finite state automata) that can solve the problem in terms of their "observational power".

International Journal of Foundations of Computer Science•Jan 1, 2011•1 citation

Bounded Quantum Regular Language Generator

YoungMin Kwon, Gul Agha

We develop a quantum algorithm to verify the correctness of systems modeled by nondeterministic finite-state automata-a problem that is computationally intractable on conventional computers. Specifically, our algorithm solves the language containment problem in three steps. First, we translate a nondeterministic finite-state automaton into a quantum finite state automaton (QFA) circuit. Second, the QFA is embedded into a larger circuit which generates a superposed set of all bounded strings that are marked to indicate whether they are accepted or not. Finally, we amplify the amplitudes of accepted strings so that they are measured more frequently. The last step may be done either by using Grover's algorithm, or by using FnR, a custom algorithm that we have developed for the cases where Grover's algorithm is not effective. Our work represents the first proposal to apply quantum computing to the problem of verifying conventional systems; our approach would facilitate software verification, program analysis, protocol design, and verification of circuits, among other applications.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•2 citations
We introduce quantum finite-state generators as a first step toward completing a computational description of observing individual quantum systems over time. We develop the mathematical foundations of quantum finite-state machines and compare nondeterministic and deterministic versions to stochastic generators and recognizers, summarizing their relative computational power via a hierarchy of finitary process languages. Quantum finite-state generators are explored via several physical examples, including the iterated beam splitter, the quantum kicked top, and atoms in an ion trap--a special case of which implements the Deutsch quantum algorithm. We show that the behavior of these systems, and so their information processing capacity, depends sensitively on measurement protocol.
The behavior of a quantum system depends on how it is measured. How much of what is observed comes from the structure of the quantum system itself and how much from the observer's choice of measurement? We explore these questions by analyzing the \emph{language diversity} of quantum finite-state generators. One result is a new way to distinguish quantum devices from their classical (stochastic) counterparts. While the diversity of languages generated by these two computational classes is the same in the case of periodic processes, quantum systems generally generate a wider range of languages than classical systems.
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).
Deutsch's problem is the simplest and most frequently examined example of computational problem used to demonstrate the superiority of quantum computing over classical computing. Deutsch's quantum algorithm has been claimed to be faster than any classical ones solving the same problem, only to be discovered later that this was not the case. Various de-quantised solutions for Deutsch's quantum algorithm—classical solutions which are as efficient as the quantum one—have been proposed in the literature. These solutions are based on the possibility of classically simulating "superpositions", a key ingredient of quantum algorithms, in particular, Deutsch's algorithm. The de-quantisation proposed in this note is based on a classical simulation of the quantum measurement achieved with a model of observed system. As in some previous de-quantisations of Deutsch's quantum algorithm, the resulting de-quantised algorithm is deterministic. Finally, we classify observers (as finite state automata) that can solve the problem in terms of their "observational power".
We develop a quantum algorithm to verify the correctness of systems modeled by nondeterministic finite-state automata-a problem that is computationally intractable on conventional computers. Specifically, our algorithm solves the language containment problem in three steps. First, we translate a nondeterministic finite-state automaton into a quantum finite state automaton (QFA) circuit. Second, the QFA is embedded into a larger circuit which generates a superposed set of all bounded strings that are marked to indicate whether they are accepted or not. Finally, we amplify the amplitudes of accepted strings so that they are measured more frequently. The last step may be done either by using Grover's algorithm, or by using FnR, a custom algorithm that we have developed for the cases where Grover's algorithm is not effective. Our work represents the first proposal to apply quantum computing to the problem of verifying conventional systems; our approach would facilitate software verification, program analysis, protocol design, and verification of circuits, among other applications.