State succinctness of two-way finite automata with quantum and classical states
From MaRDI portal
Publication:391188
DOI10.1016/j.tcs.2013.06.005zbMath1296.68098arXiv1202.2651OpenAlexW2058773739WikidataQ59196655 ScholiaQ59196655MaRDI QIDQ391188
Paulo Mateus, Jozef Gruska, Lvzhou Li, Shenggen Zheng, Dao Wen Qiu
Publication date: 10 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1202.2651
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (15)
Unary probabilistic and quantum automata on promise problems ⋮ One-Way Finite Automata with Quantum and Classical States ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ From Quantum Query Complexity to State Complexity ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ Quaternionic quantum automata ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ Application of distributed semi-quantum computing model in phase estimation ⋮ Promise problems solved by quantum and classical finite automata ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ On the power of two-way multihead quantum finite automata ⋮ On coverings of products of uninitialized sequential quantum machines ⋮ Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
Cites Work
- Superiority of exact quantum automata for promise problems
- Unbounded-error quantum computation with small space bounds
- Characterizations of one-way general quantum finite automata
- Improved constructions of quantum automata
- A note on the reduction of two-way automata to one-way automata
- Quantum automata and quantum grammars
- Two-way finite automata with quantum and classical states.
- Quantum communication and complexity.
- Hierarchy and equivalence of multi-letter quantum finite automata
- Algebraic results on quantum automata
- Determination of equivalence between quantum sequential machines
- Determining the equivalence for one-way quantum finite automata
- Characterizations of 1-Way Quantum Finite Automata
- One-Way Finite Automata with Quantum and Classical States
- Quantum finite automata with control language
- Dense quantum coding and quantum finite automata
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- Finite state verifiers I
- Communication Complexity
- SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES
- State-complexity of finite-state devices, state compressibility and incompressibility
- Encyclopedia of Complexity and Systems Science
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: State succinctness of two-way finite automata with quantum and classical states
