Unary probabilistic and quantum automata on promise problems
From MaRDI portal
Publication:1617185
DOI10.1007/s11128-017-1799-0zbMath1402.81087DBLPjournals/qip/GainutdinovaY18arXiv1502.01462OpenAlexW2778651353WikidataQ96370035 ScholiaQ96370035MaRDI QIDQ1617185
Abuzer Yakaryılmaz, Aida Gainutdinova
Publication date: 7 November 2018
Published in: Quantum Information Processing, Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.01462
Formal languages and automata (68Q45) Quantum computation (81P68) Algebraic theory of languages and automata (68Q70)
Related Items (11)
Unary probabilistic and quantum automata on promise problems ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game ⋮ Classical and Quantum Counter Automata on Promise Problems ⋮ Quantum versus classical online streaming algorithms with logarithmic size of memory ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ Language recognition power and succinctness of affine automata ⋮ Mirrors and memory in quantum automata ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ Language Recognition Power and Succinctness of Affine Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- State succinctness of two-way finite automata with quantum and classical states
- Superiority of exact quantum automata for promise problems
- Promise problems solved by quantum and classical finite automata
- Unbounded-error quantum computation with small space bounds
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Quantum automata and quantum grammars
- Unary probabilistic and quantum automata on promise problems
- Two-way finite automata with quantum and classical states.
- More on quantum, stochastic, and pseudo stochastic languages with few states
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- Algebraic results on quantum automata
- On the computational power of probabilistic and quantum branching program
- Complexity of Promise Problems on Classical and Quantum Automata
- Quantum Finite Automata: A Modern Introduction
- Classical and Quantum Counter Automata on Promise Problems
- Potential of Quantum Finite Automata with Exact Acceptance
- Generalizations of the distributed Deutsch–Jozsa promise problem
- Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
- On quantum and probabilistic communication
- Implications of Quantum Automata for Contextuality
- Quantum Pushdown Automata with a Garbage Tape
- On the State Complexity of Semi-quantum Finite Automata
- Developments in Language Theory
- Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
- Classical Automata on Promise Problems
- Analogies and differences between quantum and stochastic automata
This page was built for publication: Unary probabilistic and quantum automata on promise problems
