Improved Constructions of Quantum Automata

DOI10.1007/978-3-540-89304-2_5zbMATH Open1162.68468OpenAlexW2184879887MaRDI QIDQ5503296FDOQ5503296

Authors Nikolajs Nahimovs, Andris Ambainis

Publication date 13 January 2009

Published in Theory of Quantum Computation, Communication, and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.1686

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68)

Abstract: We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use frac{4}{epsilon} log 2p + O(1) states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.

Recommendations

• Improved constructions of quantum automata
• The complexity of probabilistic versus quantum finite automata
• Improved constructions of mixed state quantum automata
• Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
• scientific article; zbMATH DE number 1839434

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 1839459 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (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

(9)

• Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
• Hamming, Permutations and Automata
• Improved constructions of quantum automata
• Quantum online algorithms with respect to space and advice complexity
• Analysis of properties of quantum hashing
• Improved constructions of mixed state quantum automata
• Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations
• Deterministic construction of QFAs based on the quantum fingerprinting technique
• On quantum realisation of Boolean functions by the 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 Q5503296)