Superiority of exact quantum automata for promise problems
From MaRDI portal
Publication:413305
DOI10.1016/j.ipl.2012.01.001zbMath1237.68082arXiv1101.3837OpenAlexW2032508026MaRDI QIDQ413305
Abuzer Yakaryılmaz, Andris Ambainis
Publication date: 4 May 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1101.3837
computational complexitysuccinctnesspromise problemsclassical finite automatonexact quantum computationquantum finite automaton
Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (40)
Unary probabilistic and quantum automata on promise problems ⋮ Quantum alternation ⋮ Very narrow quantum OBDDs and width hierarchies for classical OBDDs ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Nondeterministic unitary OBDDs ⋮ Unnamed Item ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ Quantum Finite Automata: A Modern Introduction ⋮ From Quantum Query Complexity to State Complexity ⋮ State succinctness of two-way finite automata with quantum and classical states ⋮ Unnamed Item ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ 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 ⋮ Size lower bounds for quantum automata ⋮ An exact quantum algorithm for a restricted subtraction game ⋮ Quaternionic quantum automata ⋮ On the Power of One-Way Automata with Quantum and Classical States ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Modeling of RNA secondary structures using two-way quantum finite automata ⋮ Comparative complexity of quantum and classical OBDDs for total and partial functions ⋮ On a Conjecture by Christian Choffrut ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ On language varieties without Boolean operations ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ Quantum \(\omega\)-automata over infinite words and their relationships ⋮ Quantum Pushdown Automata with Garbage Tape ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ Promise problems solved by quantum and classical finite automata ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ On the Computational Power of Affine Automata ⋮ Affine Computation and Affine Automaton ⋮ Unbounded-error quantum computation with small space bounds ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Language Recognition Power and Succinctness of Affine Automata ⋮ Uncountable classical and quantum complexity classes ⋮ Looking for Pairs that Hard to Separate: A Quantum Approach ⋮ Improved constructions for succinct affine automata ⋮ The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
Cites Work
- Unnamed Item
- Unnamed Item
- Unbounded-error quantum computation with small space bounds
- Quantum zero-error algorithms cannot be composed
- Quantum automata and quantum grammars
- Quantum computation with write-only memory
- On quantum and probabilistic communication
- Quantum Queries on Permutations with a Promise
- Quantum Complexity Theory
- Quantum lower bounds by polynomials
- Encyclopedia of Complexity and Systems Science
This page was built for publication: Superiority of exact quantum automata for promise problems
