Improved Constructions of Quantum Automata

DOI10.1007/978-3-540-89304-2_5zbMATH Open1162.68468arXiv0805.1686OpenAlexW2184879887MaRDI 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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum automata and quantum grammars
• Estimates on exponential sums related to the Diffie-Hellman distributions
• Dense quantum coding and quantum finite automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Construction of a Thin Set with small Fourier Coefficients
• Constructing Small Sets that are Uniform in Arithmetic Progressions

Cited In (9)

• Improved constructions of quantum automata
• Analysis of properties of quantum hashing
• On quantum realisation of Boolean functions by the fingerprinting technique
• 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
• Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
• Quantum online algorithms with respect to space and advice complexity
• Hamming, Permutations and Automata

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)