Languages recognized by nondeterministic quantum finite automata

MaRDI QIDQ3171611zbMATH OpenFDO

Authors Abuzer Yakaryılmaz, A. C. Cem Say

Publication date 5 October 2011

zbMATH Keywords

nondeterministic quantum finite automataone-sided unbounded errorprobabilistic automatasublogarithmic space complexitytwo-sided unbounded error

Mathematics Subject Classification ID

Error bounds for numerical methods for ordinary differential equations (65L70) Quantum algorithms and complexity in the theory of computing (68Q12) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80) Quantum computation (81P68)

Recommendations

• Implementation and Application of Automata
• scientific article; zbMATH DE number 1688355
• Two-way finite automata with quantum and classical states.
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• The complexity of probabilistic versus quantum finite automata

Cited in

(31)

• More on quantum, stochastic, and pseudo stochastic languages with few states
• Improved constructions for succinct affine automata
• Affine automata verifiers
• Quantum alternation
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Nondeterministic unitary OBDDs
• scientific article; zbMATH DE number 1688355 (Why is no real title available?)
• Language Recognition Power and Succinctness of Affine Automata
• Looking for Pairs that Hard to Separate: A Quantum Approach
• Quantum finite automata: a modern introduction
• The complexity of probabilistic versus quantum finite automata
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• scientific article; zbMATH DE number 6533717 (Why is no real title available?)
• State succinctness of two-way finite automata with quantum and classical states
• scientific article; zbMATH DE number 35744 (Why is no real title available?)
• On a conjecture by Christian Choffrut
• Exponentially more concise quantum recognition of non-RMM regular languages
• scientific article; zbMATH DE number 1405684 (Why is no real title available?)
• Uncountable classical and quantum complexity classes
• scientific article; zbMATH DE number 7104930 (Why is no real title available?)
• STACS 2004
• Unbounded-error quantum computation with small space bounds
• Affine computation and affine automaton
• Implementation and Application of Automata
• Deterministic construction of QFAs based on the quantum fingerprinting technique
• Language recognition power and succinctness of affine automata
• Computational limitations of affine automata and generalized affine automata
• The power of a single qubit: two-way quantum finite automata and the word problem
• Classical and quantum Merlin-Arthur automata
• Unconditional proofs of quantumness between small-space machines
• Real-valued affine automata compute beyond Turing machines

This page was built for publication: Languages recognized by nondeterministic quantum finite automata

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