Size lower bounds for quantum automata

DOI10.1016/j.tcs.2014.07.004zbMath1360.68540OpenAlexW1995944540MaRDI QIDQ403023

Maria Paola Bianchi, Beatrice Palano, Carlo Mereghetti

Publication date: 29 August 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.004

zbMATH Keywords

descriptional complexityquantum finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Lower bounds on the size of semi-quantum finite automata ⋮ On the Power of One-Way Automata with Quantum and Classical States ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superiority of exact quantum automata for promise problems
• Quantum automata and quantum grammars
• Algebraic results on quantum automata
• Quantum automata for some multiperiodic languages
• Small size quantum automata recognizing some regular languages
• Some formal tools for analyzing quantum automata.
• Behaviours of Unary Quantum Automata
• Characterizations of 1-Way Quantum Finite Automata
• One-Way Finite Automata with Quantum and Classical States
• Quantum finite automata with control language
• On Varieties of Literally Idempotent Languages
• Lower Bounds for Generalized Quantum Finite Automata
• On the State Complexity of Semi-quantum Finite Automata
• Probabilistic automata
• Angles in complex vector spaces
• Trace monoids with idempotent generators and measure-only quantum automata

This page was built for publication: Size lower bounds for quantum automata