Learning quantum finite automata with queries
From MaRDI portal
Abstract: {it Learning finite automata} (termed as {it model learning}) has become an important field in machine learning and has been useful realistic applications. Quantum finite automata (QFA) are simple models of quantum computers with finite memory. Due to their simplicity, QFA have well physical realizability, but one-way QFA still have essential advantages over classical finite automata with regard to state complexity (two-way QFA are more powerful than classical finite automata in computation ability as well). As a different problem in {it quantum learning theory} and {it quantum machine learning}, in this paper, our purpose is to initiate the study of {it learning QFA with queries} (naturally it may be termed as {it quantum model learning}), and the main results are regarding learning two basic one-way QFA: (1) We propose a learning algorithm for measure-once one-way QFA (MO-1QFA) with query complexity of polynomial time; (2) We propose a learning algorithm for measure-many one-way QFA (MM-1QFA) with query complexity of polynomial-time, as well.
Recommendations
Cites work
- Algebraic results on quantum automata
- An improved lower bound on query complexity for quantum PAC learning
- Automata and quantum computing
- Automata theory based on quantum logic: reversibilities and pushdown automata
- Characterizations of 1-Way Quantum Finite Automata
- Determination of equivalence between quantum sequential machines
- Equivalences and Separations Between Quantum and Classical Learnability
- Exponentially more concise quantum recognition of non-RMM regular languages
- Grammatical inference. Learning automata and grammars.
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 2040892 (Why is no real title available?)
- scientific article; zbMATH DE number 1916673 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 3371972 (Why is no real title available?)
- Inference of Reversible Languages
- Learning Behaviors of Automata from Multiplicity and Equivalence Queries
- Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
- Learning probabilistic automata and Markov chains via queries
- Learning regular sets from queries and counterexamples
- Learning weighted automata
- Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
- Optimal quantum sample complexity of learning algorithms
- Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Quantum discriminant analysis for dimensionality reduction and classification
- Quantum finite automata
- Quantum finite automata: a modern introduction
- Quantum predictive learning and communication complexity with single input
- Quantum recommendation systems
- Queries and concept learning
- The learnability of quantum states
This page was built for publication: Learning quantum finite automata with queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149966)
