Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States

DOI10.1007/978-3-540-92182-0_81zbMath1183.68339OpenAlexW1552615231MaRDI QIDQ3597891

Rūsiņš Freivalds

Publication date: 29 January 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92182-0_81

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)