Superiority of exact quantum automata for promise problems
From MaRDI portal
Publication:413305
DOI10.1016/j.ipl.2012.01.001zbMath1237.68082arXiv1101.3837MaRDI 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 complexity; succinctness; promise problems; classical finite automaton; exact quantum computation; quantum finite automaton
68Q45: Formal languages and automata
68Q12: Quantum algorithms and complexity in the theory of computing
Related Items
On a Conjecture by Christian Choffrut, Quantum Pushdown Automata with Garbage Tape, Unnamed Item, Unnamed Item, Uncountable classical and quantum complexity classes, The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints, On the Power of One-Way Automata with Quantum and Classical States, On the Computational Power of Affine Automata, Affine Computation and Affine Automaton, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, 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, Quaternionic quantum automata, Classical and Quantum Computations with Restricted Memory, State succinctness of two-way finite automata with quantum and classical states, Size lower bounds for quantum automata, Promise problems solved by quantum and classical finite automata, Quantum finite automata: advances on Bertoni's ideas, Unbounded-error quantum computation with small space bounds, Quantum online algorithms with respect to space and advice complexity, Comparative complexity of quantum and classical OBDDs for total and partial functions, Unary probabilistic and quantum automata on promise problems, Quantum \(\omega\)-automata over infinite words and their relationships, Improved constructions for succinct affine automata, Two-way and one-way quantum and classical automata with advice for online minimization problems, An exact quantum algorithm for a restricted subtraction game, Modeling of RNA secondary structures using two-way quantum finite automata, On language varieties without Boolean operations, Quantum online streaming algorithms with logarithmic memory, Quantum alternation, Very narrow quantum OBDDs and width hierarchies for classical OBDDs, Nondeterministic unitary OBDDs, Language Recognition Power and Succinctness of Affine Automata, Looking for Pairs that Hard to Separate: A Quantum Approach, Complexity of Promise Problems on Classical and Quantum Automata, Quantum Finite Automata: A Modern Introduction, From Quantum Query Complexity to State Complexity, Potential of Quantum Finite Automata with Exact Acceptance, Generalizations of the distributed Deutsch–Jozsa promise problem
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
