Improved constructions of quantum automata
From MaRDI portal
Publication:1017403
DOI10.1016/j.tcs.2009.01.027zbMath1163.68020OpenAlexW2034563250MaRDI QIDQ1017403
Andris Ambainis, Nikolajs Nahimovs
Publication date: 19 May 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.01.027
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Related Items (15)
One-Way Finite Automata with Quantum and Classical States ⋮ Quantum Finite Automata: A Modern Introduction ⋮ From Quantum Query Complexity to State Complexity ⋮ State succinctness of two-way finite automata with quantum and classical states ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ Quantum algorithm for dynamic programming approach for DAGs and applications ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ GAPs for Shallow Implementation of Quantum Finite Automata ⋮ Exponentially more concise quantum recognition of non-RMM regular languages ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ Promise problems solved by quantum and classical finite automata ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Quantum automata and quantum grammars
- Estimates on exponential sums related to the Diffie-Hellman distributions
- Construction of a Thin Set with small Fourier Coefficients
- Dense quantum coding and quantum finite automata
- Constructing Small Sets that are Uniform in Arithmetic Progressions
This page was built for publication: Improved constructions of quantum automata