The complexity of probabilistic versus quantum finite automata

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

Authors: Gatis Midrijānis 

Publication date: 1 April 2011

Published in: SOFSEM 2002: Theory and Practice of Informatics (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

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

Mathematics Subject Classification ID

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

Cited In (22)

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

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)