Search results for "quantum finite automata"
showing 10 items of 73 documents
Exact affine counter automata
2017
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k-counter automata. We also show that a certain promise problem, which is conjectured not to be solved by two-way quantum finite automata in polynomial time, can be solved by Las Vegas affine finite automata. Lastly, we show that how a counter helps for affine finite automata by showing that the language MANYTWINS, which is conjectured not to be recognized by affin…
Quantum inductive inference by finite automata
2008
AbstractFreivalds and Smith [R. Freivalds, C.H. Smith Memory limited inductive inference machines, Springer Lecture Notes in Computer Science 621 (1992) 19–29] proved that probabilistic limited memory inductive inference machines can learn with probability 1 certain classes of total recursive functions, which cannot be learned by deterministic limited memory inductive inference machines. We introduce quantum limited memory inductive inference machines as quantum finite automata acting as inductive inference machines. These machines, we show, can learn classes of total recursive functions not learnable by any deterministic, nor even by probabilistic, limited memory inductive inference machin…
Complexity of probabilistic versus deterministic automata
2005
Exact results for accepting probabilities of quantum automata
2001
One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most 0.7726...
Mathematical logic and quantum finite state automata
2009
AbstractThis paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.
Representation of Autonomous Automata
2001
An autonomous automaton is a finite automaton with output in which the input alphabet has cardinality one when special reduced. We define the transition from automata to semigroups via a representation successful if given two incomparable automata (neither simulate the other), the semigroups representing the automata are distinct. We show that representation by the transition semigroup is not successful. We then consider a representation of automata by semigroups of partial transformations. We show that in general transition from automata to semigroups by this representation is not successful either. In fact, the only successful transition presented is the transiton to this semigroup of par…
Quantum Finite One-Counter Automata
1999
In this paper the notion of quantum finite one-counter automata (QF1CA) is introduced. Introduction of the notion is similar to that of the 2-way quantum finite state automata in [1]. The well-formedness conditions for the automata are specified ensuring unitarity of evolution. A special kind of QF1CA, called simple, that satisfies the well-formedness conditions is introduced. That allows specify rules for constructing such automata more naturally and simpler than in general case. Possible models of language recognition by QF1CA are considered. The recognition of some languages by QF1CA is shown and compared with recognition by probabilistic counterparts.
A description based on languages of the final non-deterministic automaton
2014
The study of the behaviour of non-deterministic automata has traditionally focused on the languages which can be associated to the different states. Under this interpretation, the different branches that can be taken at every step are ignored. However, we can also take into account the different decisions which can be made at every state, that is, the branches that can be taken, and these decisions might change the possible future behaviour. In this case, the behaviour of the automata can be described with the help of the concept of bisimilarity. This is the kind of description that is usually obtained when the automata are regarded as labelled transition systems or coalgebras. Contrarily t…
Complexity of operations on cofinite languages
2010
International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.
Implementing Quantum Finite Automata Algorithms on Noisy Devices
2021
Quantum finite automata (QFAs) literature offers an alternative mathematical model for studying quantum systems with finite memory. As a superiority of quantum computing, QFAs have been shown exponentially more succinct on certain problems such as recognizing the language \(\mathtt {MOD}_\mathrm{p}= \{{a^{j}} \mid {j \equiv 0 \mod p}\} \) with bounded error, where p is a prime number. In this paper we present improved circuit based implementations for QFA algorithms recognizing the \(\mathtt {MOD}_\mathrm{p}\) problem using the Qiskit framework. We focus on the case \(p=11\) and provide a 3 qubit implementation for the \(\mathtt {MOD}_\mathrm{11}\) problem reducing the total number of requi…