Size lower bounds for quantum automata

DOI10.1016/J.TCS.2014.07.004zbMATH Open1360.68540OpenAlexW1995944540MaRDI QIDQ403023FDOQ403023

Authors: Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano 

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

Recommendations

• Size lower bounds for quantum automata
• Lower bounds on the size of semi-quantum finite automata
• scientific article; zbMATH DE number 1759400
• Lower Bounds for Generalized Quantum Finite Automata
• Lower bounds on the size of quantum automata accepting unary languages.

zbMATH Keywords

descriptional complexityquantum finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Probabilistic automata
• One-way finite automata with quantum and classical states
• Quantum finite automata with control language
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum automata and quantum grammars
• Algebraic results on quantum automata
• Characterizations of 1-Way Quantum Finite Automata
• Superiority of exact quantum automata for promise problems
• 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
• On Varieties of Literally Idempotent Languages
• Lower Bounds for Generalized Quantum Finite Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the state complexity of semi-quantum finite automata
• Angles in complex vector spaces
• Trace monoids with idempotent generators and measure-only quantum automata

Cited In (8)

• On the power of one-way automata with quantum and classical states
• Lower bounds on the size of semi-quantum finite automata
• Lower Bounds for Generalized Quantum Finite Automata
• Quantum bounds for 2D-grid and Dyck language
• Size lower bounds for quantum automata
• Title not available (Why is that?)
• GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
• Quantum finite automata: advances on Bertoni's ideas

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

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