Characterizations of 1-Way Quantum Finite Automata
From MaRDI portal
Abstract: The 2-way quantum finite automaton introduced by Kondacs and Watrous can accept non-regular languages with bounded error in polynomial time. If we restrict the head of the automaton to moving classically and to moving only in one direction, the acceptance power of this 1-way quantum finite automaton is reduced to a proper subset of the regular languages. In this paper we study two different models of 1-way quantum finite automata. The first model, termed measure-once quantum finite automata, was introduced by Moore and Crutchfield, and the second model, termed measure-many quantum finite automata, was introduced by Kondacs and Watrous. We characterize the measure-once model when it is restricted to accepting with bounded error and show that, without that restriction, it can solve the word problem over the free group. We also show that it can be simulated by a probabilistic finite automaton and describe an algorithm that determines if two measure-once automata are equivalent. We prove several closure properties of the classes of languages accepted by measure-many automata, including inverse homomorphisms, and provide a new necessary condition for a language to be accepted by the measure-many model with bounded error. Finally, we show that piecewise testable languages can be accepted with bounded error by a measure-many quantum finite automaton, in the process introducing new construction techniques for quantum automata.
Recommendations
- Characterizations of one-way general quantum finite automata
- One-way finite automata with quantum and classical states
- Some algebraic properties of measure-once two-way quantum finite automata
- scientific article; zbMATH DE number 2040892
- Languages Recognized with Unbounded Error by Quantum Finite Automata
Cited in
(80)- Some algebraic properties of measure-once two-way quantum finite automata
- An application of quantum finite automata to interactive proof systems
- Efficient probability amplification in two-way quantum finite automata
- On a class of languages recognizable by probabilistic reversible decide-and-halt automata
- A note on quantum sequential machines
- Exact results for accepting probabilities of quantum automata.
- Simulation methods for quantum walks on graphs applied to formal language recognition
- Quantum \(\omega\)-automata over infinite words and their relationships
- A probabilistic model of computing with words
- Quantum versus deterministic counter automata
- Regular languages accepted by quantum automata
- Characterizations of quantum automata
- More on quantum, stochastic, and pseudo stochastic languages with few states
- Characterization of tree automata based on quantum logic
- Energy complexity of regular language recognition
- Equivalence checking of quantum finite-state machines
- On injectivity of quantum finite automata
- On language varieties without Boolean operations
- Hierarchy and equivalence of multi-letter quantum finite automata
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- On hybrid models of quantum finite automata
- Automata theory based on quantum logic: reversibilities and pushdown automata
- Quantum automata for some multiperiodic languages
- Small size quantum automata recognizing some regular languages
- Some formal tools for analyzing quantum automata.
- Determination of equivalence between quantum sequential machines
- Determining the equivalence for one-way quantum finite automata
- Interference automata
- scientific article; zbMATH DE number 1688355 (Why is no real title available?)
- Undecidability on quantum finite automata
- Dense quantum coding and a lower bound for 1-way quantum automata
- Analysis of finite 1-qubit quantum automata unitary operators of which are rotations
- Complexity of promise problems on classical and quantum automata
- From quantum query complexity to state complexity
- Potential of quantum finite automata with exact acceptance
- Quantum automata theory -- a review
- Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
- One-way finite automata with quantum and classical states
- Languages Recognized with Unbounded Error by Quantum Finite Automata
- Quantum finite automata with control language
- Complexity bounds of constant-space quantum computation
- Lower Bounds for Generalized Quantum Finite Automata
- State succinctness of two-way finite automata with quantum and classical states
- Size lower bounds for quantum automata
- Another approach to the equivalence of measure-many one-way quantum finite automata and its application
- scientific article; zbMATH DE number 2044497 (Why is no real title available?)
- scientific article; zbMATH DE number 1759400 (Why is no real title available?)
- Quantum pushdown automata with garbage tape
- Exponentially more concise quantum recognition of non-RMM regular languages
- scientific article; zbMATH DE number 1839434 (Why is no real title available?)
- On the Size of One-way Quantum Finite Automata with Periodic Behaviors
- Some languages recognized by two-way finite automata with quantum and classical states
- Acceptance Ambiguity for Quantum Automata
- Quantum finite automata: advances on Bertoni's ideas
- On the decidability of the intersection problem for quantum automata and context-free languages
- Algebraic characterization of the class of languages recognized by measure only quantum automata
- Quantum finite automata and linear context-free languages: a decidable problem
- Two-tape finite automata with quantum and classical states
- Quantum state complexity of formal languages
- Unbounded-error quantum computation with small space bounds
- GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
- On the power of one-way automata with quantum and classical states
- How does adiabatic quantum computation fit into quantum automata theory?
- Trace monoids with idempotent generators and measure-only quantum automata
- Automata theory based on quantum logic: Some characterizations
- Classically time-controlled quantum automata
- Energy complexity of computation
- Learning quantum finite automata with queries
- Mirrors and memory in quantum automata
- Energy complexity of regular languages
- Quantum Büchi automata
- The power of a single qubit: two-way quantum finite automata and the word problem
- On the complexity of minimizing probabilistic and quantum automata
- State complexity of one-way quantum finite automata together with classical states
- Latvian quantum finite state automata for unary languages
- Latvian quantum finite state automata for unary languages
- Characterizations of one-way general quantum finite automata
- Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
- On relation between linear temporal logic and quantum finite automata
- Quantum inductive inference by finite automata
This page was built for publication: Characterizations of 1-Way Quantum Finite Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3149877)
