Improved Constructions of Quantum Automata

DOI10.1007/978-3-540-89304-2_5MaRDI QIDQ5503296zbMATH OpenOpenAlexFDO

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
• Ambainis-Freivalds' algorithm for measure-once automata

Cites work

• 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
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• On the class of languages recognizable by 1-way quantum finite automata
• Quantum automata and quantum grammars
• Quantum computing: 1-way quantum automata
• Quantum reversibility and a new model of quantum automaton

Cited in

(10)

• Improved constructions of quantum automata
• Improved constructions of mixed state quantum automata
• Analysis of properties of quantum hashing
• On quantum realisation of Boolean functions by the fingerprinting technique
• Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
• Hamming, Permutations and Automata
• Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations
• Deterministic construction of QFAs based on the quantum fingerprinting technique
• Quantum online algorithms with respect to space and advice complexity
• Implementation of quantum Fourier transform and quantum hashing for quantum devices with arbitrary qubit connectivity graphs

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)