Improved constructions of quantum automata

DOI10.1016/J.TCS.2009.01.027MaRDI QIDQ1017403zbMATHOpenAlexFDO

Authors 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)

Recommendations

• Improved Constructions of Quantum Automata
• Improved constructions of mixed state quantum automata
• Quantum finite automata
• Quantum Turing automata
• Characterizations of quantum automata
• Quantum finite automata: advances on Bertoni's ideas
• Quantum counter automata
• Quantum automata theory -- a review
• Some remarks on quantum automata

Cites work

• scientific article; zbMATH DE number 1688355 (Why is no real title available?)
• scientific article; zbMATH DE number 2040892 (Why is no real title available?)
• scientific article; zbMATH DE number 1759400 (Why is no real title available?)
• scientific article; zbMATH DE number 1839459 (Why is no real title available?)
• Constructing Small Sets that are Uniform in Arithmetic Progressions
• Construction of a Thin Set with small Fourier Coefficients
• Dense quantum coding and quantum finite automata
• Estimates on exponential sums related to the Diffie-Hellman distributions
• Quantum automata and quantum grammars

Cited in

(18)

• Promise problems solved by quantum and classical finite automata
• One-way finite automata with quantum and classical states
• State succinctness of two-way finite automata with quantum and classical states
• Improved Constructions of Quantum Automata
• Quantum finite automata: a modern introduction
• GAPs for Shallow Implementation of Quantum Finite Automata
• Quantum algorithm for dynamic programming approach for DAGs and applications
• Lifting query complexity to time-space complexity for two-way finite automata
• Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
• Hamming, Permutations and Automata
• Exponentially more concise quantum recognition of non-RMM regular languages
• Quantum online algorithms with respect to space and advice complexity
• From quantum query complexity to state complexity
• Improved constructions of mixed state quantum automata
• Potential of quantum finite automata with exact acceptance
• Quantum finite automata: advances on Bertoni's ideas
• Descriptional complexity of iterated uniform finite-state transducers
• Deterministic construction of QFAs based on the quantum fingerprinting technique

This page was built for publication: Improved constructions of quantum automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017403)