Improved constructions of quantum automata

Simple item page
dc.creatorAmbainis, Andris
dc.creatorNahimovs, Nikolajs
dc.date2008-05-12
dc.date.accessioned2026-07-07T09:38:24Z
dc.date.available2026-07-07T09:38:24Z
dc.descriptionWe present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use \frac{4}ε \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.
dc.description9 pages
dc.identifierhttps://arxiv.org/abs/0805.1686
dc.identifierhttp://arxiv.org/abs/0805.1686
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/160795
dc.subjectQuantum Physics
dc.titleImproved constructions of quantum automata
dc.typetext

Files

Collections

arXiv