Quantum State Complexity of Formal Languages
From MaRDI portal
Publication:5500700
DOI10.1007/978-3-319-19225-3_24zbMath1432.68249OpenAlexW956147778MaRDI QIDQ5500700
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
advicequantum finite automatonminimal automatonpermutation automatonapproximate matrix rankquantum state complexitytimed crossing sequence
Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12) Classical models of computation (Turing machines, etc.) (68Q04)
Related Items (5)
Classically time-controlled quantum automata ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ How does adiabatic quantum computation fit into quantum automata theory? ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
Cites Work
- Unnamed Item
- Unnamed Item
- One-way reversible and quantum finite automata with advice
- An application of quantum finite automata to interactive proof systems
- Improved constructions of mixed state quantum automata
- Geometric arguments yield better bounds for threshold circuits and distributed computing
- Quantum automata and quantum grammars
- On the complexity of simulating space-bounded quantum computations
- Amount of nonconstructivity in deterministic finite automata
- Space-bounded quantum complexity
- Polynomial time quantum computation with advice
- Covering spheres with spheres
- Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
- Characterizations of 1-Way Quantum Finite Automata
- Lower Bounds in Communication Complexity
- Dense quantum coding and quantum finite automata
- Automata that take advice
- On the state complexity of semi-quantum finite automata
This page was built for publication: Quantum State Complexity of Formal Languages
