Improved constructions of quantum automata

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

zbMATH Keywords

quantum computationquantum finite automataexponential advantage

Mathematics Subject Classification ID

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