The complexity of probabilistic versus quantum finite automata

DOI10.1007/3-540-36137-5_21MaRDI QIDQ3085986zbMATHOpenAlexFDO

Authors Gatis Midrijānis

Publication date 1 April 2011

Published in SOFSEM 2002: Theory and Practice of Informatics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

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.

Recommendations

• The complexity of probabilistic versus deterministic finite automata
• Succinctness of two-way probabilistic and quantum finite automata
• Languages recognized by nondeterministic quantum finite automata

Cited in

(23)

• The complexity of probabilistic versus deterministic finite automata
• The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
• Succinctness of two-way probabilistic and quantum finite automata
• scientific article; zbMATH DE number 1490003 (Why is no real title available?)
• scientific article; zbMATH DE number 1839434 (Why is no real title available?)
• Languages recognized by nondeterministic quantum finite automata
• Improved Constructions of Quantum Automata
• Superiority of exact quantum automata for promise problems
• scientific article; zbMATH DE number 1405684 (Why is no real title available?)
• Lifting query complexity to time-space complexity for two-way finite automata
• Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
• On the complexity of minimizing probabilistic and quantum automata
• On the size of unary probabilistic and nondeterministic automata
• Quantum state complexity of formal languages
• scientific article; zbMATH DE number 2080922 (Why is no real title available?)
• Improved constructions of mixed state quantum automata
• Complexity classes of equivalence problems revisited
• The complexity properties of probabilistic automata with isolated cut point
• scientific article; zbMATH DE number 1834645 (Why is no real title available?)
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• Exact results for accepting probabilities of quantum automata.
• scientific article; zbMATH DE number 2090013 (Why is no real title available?)
• Postselection finite quantum automata

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)