State succinctness of two-way finite automata with quantum and classical states

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

zbMATH Keywords

state complexityquantum finite automatacomputing modelsstate succinctness

Mathematics Subject Classification ID

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