Promise problems solved by quantum and classical finite automata
From MaRDI portal
Publication:511009
DOI10.1016/j.tcs.2016.12.025zbMath1359.68181arXiv1411.3870OpenAlexW2964031227MaRDI QIDQ511009
Jozef Gruska, Shenggen Zheng, Lvzhou Li, Dao Wen Qiu
Publication date: 14 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1411.3870
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
Unary probabilistic and quantum automata on promise problems ⋮ Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game ⋮ Three Attacks on the Mediated Semi‐Quantum Key Distribution without Invoking Quantum Measurement ⋮ Modeling of RNA secondary structures using two-way quantum 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
Cites Work
- 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
- Exponentially more concise quantum recognition of non-RMM regular languages
- A lower bound for probabilistic algorithms for finite state machines
- On the complexity of minimizing probabilistic and quantum automata
- Characterizations of one-way general quantum finite automata
- Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
- Improved constructions of quantum automata
- Improved constructions of mixed state quantum automata
- Quantum automata and quantum grammars
- Characterization of sequential quantum machines
- Two-way finite automata with quantum and classical states.
- Characterizations of quantum automata
- Hierarchy and equivalence of multi-letter quantum finite automata
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- On hybrid models of quantum finite automata
- Small size quantum automata recognizing some regular languages
- Some formal tools for analyzing quantum automata.
- Determining the equivalence for one-way quantum finite automata
- Complexity of Promise Problems on Classical and Quantum Automata
- From Quantum Query Complexity to State Complexity
- Potential of Quantum Finite Automata with Exact Acceptance
- One-Way Finite Automata with Quantum and Classical States
- Implications of Quantum Automata for Contextuality
- The complexity of promise problems with applications to public-key cryptography
- Finite state verifiers I
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- On the Power of Quantum Computation
- On the state complexity of semi-quantum finite automata
- Algebra-coalgebra duality in brzozowski's minimization algorithm
- Classical Automata on Promise Problems
- GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
- Encyclopedia of Complexity and Systems Science
This page was built for publication: Promise problems solved by quantum and classical finite automata
