The Complexity of Probabilistic versus Quantum Finite Automata

DOI10.1007/3-540-36137-5_21zbMATH Open1278.68137arXivquant-ph/0309080OpenAlexW2139519154MaRDI QIDQ3085986

Author name not available (Why is that?)

Publication date: 1 April 2011

Published in: (Search for Journal in Brave)

Abstract: We present a language $L_n$ which is recognizable by a probabilistic finite automaton (PFA) with probability $1-epsilon$ for all $epsilon>0$ with $O(lo{g}^{2}n)$ states, with a deterministic finite automaton (DFA) with O(n) states, but a quantum finite automaton (QFA) needs at least $2^{Omega(n/logn)}$ states.

Full work available at URL: https://arxiv.org/abs/quant-ph/0309080

Mathematics Subject Classification ID

No records found.

This page was built for publication: The Complexity of Probabilistic versus Quantum Finite Automata

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