Quantum state complexity of formal languages

DOI10.1007/978-3-319-19225-3_24MaRDI QIDQ5500700zbMATH OpenOpenAlexFDO

Authors Marcos Villagra, Tomoyuki Yamakami

Publication date 7 August 2015

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19225-3_24

zbMATH Keywords

adviceapproximate matrix rankminimal automatonpermutation automatonquantum finite automatonquantum state complexitytimed crossing sequence

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Quantum algorithms and complexity in the theory of computing (68Q12) Formal languages and automata (68Q45)

Recommendations

• The complexity of probabilistic versus quantum finite automata
• On the state complexity of semi-quantum finite automata
• On the state complexity of semi-quantum finite automata
• From quantum query complexity to state complexity
• Quantum automata: an overview.

Cites work

• Amount of nonconstructivity in deterministic finite automata
• An application of quantum finite automata to interactive proof systems
• Automata that take advice
• Characterizations of 1-Way Quantum Finite Automata
• Covering spheres with spheres
• Dense quantum coding and quantum finite automata
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• scientific article; zbMATH DE number 1688355 (Why is no real title available?)
• Improved constructions of mixed state quantum automata
• Lower bounds in communication complexity
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• On the complexity of simulating space-bounded quantum computations
• On the state complexity of semi-quantum finite automata
• Polynomial time quantum computation with advice
• Quantum automata and quantum grammars
• Space-bounded quantum complexity
• Succinctness of two-way probabilistic and quantum finite automata

Cited in

(10)

• Formal semantics of a classical-quantum language
• Superposition as memory: unlocking quantum automatic complexity
• From quantum query complexity to state complexity
• Complexity of Grammar Induction for Quantum Types
• scientific article; zbMATH DE number 7561601 (Why is no real title available?)
• Quantum finite automata: advances on Bertoni's ideas
• A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
• How does adiabatic quantum computation fit into quantum automata theory?
• Classically time-controlled quantum automata
• Power of counting by nonuniform families of polynomial-size finite automata

This page was built for publication: Quantum state complexity of formal languages

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