Superiority of exact quantum automata for promise problems
From MaRDI portal
Publication:413305
DOI10.1016/J.IPL.2012.01.001zbMATH Open1237.68082arXiv1101.3837OpenAlexW2032508026MaRDI QIDQ413305FDOQ413305
Abuzer Yakaryılmaz, Andris Ambainis
Publication date: 4 May 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in realtime mode, whereas the size of the corresponding classical automata grow without bound.
Full work available at URL: https://arxiv.org/abs/1101.3837
Recommendations
- Promise problems solved by quantum and classical finite automata
- Complexity of promise problems on classical and quantum automata
- Classical and Quantum Counter Automata on Promise Problems
- Unary probabilistic and quantum automata on promise problems
- Unary probabilistic and quantum automata on promise problems
- On a poset of quantum exact promise problems
- Exact results for accepting probabilities of quantum automata.
- Potential of quantum finite automata with exact acceptance
- scientific article; zbMATH DE number 1834645
- The complexity of probabilistic versus quantum finite automata
computational complexitysuccinctnesspromise problemsclassical finite automatonexact quantum computationquantum finite automaton
Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)
Cites Work
- Unbounded-error quantum computation with small space bounds
- Quantum Complexity Theory
- Title not available (Why is that?)
- Encyclopedia of Complexity and Systems Science
- Quantum lower bounds by polynomials
- On quantum and probabilistic communication
- Quantum automata and quantum grammars
- Quantum zero-error algorithms cannot be composed
- Quantum computation with write-only memory
- Quantum Queries on Permutations with a Promise
- Title not available (Why is that?)
Cited In (41)
- State succinctness of two-way finite automata with quantum and classical states
- Quantum online streaming algorithms with logarithmic memory
- Title not available (Why is that?)
- Affine Computation and Affine Automaton
- Generalizations of the distributed Deutsch–Jozsa promise problem
- Modeling of RNA secondary structures using two-way quantum finite automata
- Unbounded-error quantum computation with small space bounds
- Size lower bounds for quantum automata
- The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
- On a Conjecture by Christian Choffrut
- Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
- Promise problems solved by quantum and classical finite automata
- On language varieties without Boolean operations
- Uncountable classical and quantum complexity classes
- Title not available (Why is that?)
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- On the Power of One-Way Automata with Quantum and Classical States
- Quantum alternation
- From Quantum Query Complexity to State Complexity
- Unary probabilistic and quantum automata on promise problems
- 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
- Classical and Quantum Counter Automata on Promise Problems
- Potential of Quantum Finite Automata with Exact Acceptance
- On the Computational Power of Affine Automata
- An exact quantum algorithm for a restricted subtraction game
- Quantum versus classical online streaming algorithms with logarithmic size of memory
- Quaternionic quantum automata
- Deterministic construction of QFAs based on the quantum fingerprinting technique
- Quantum online algorithms with respect to space and advice complexity
- Quantum finite automata: advances on Bertoni's ideas
- Quantum \(\omega\)-automata over infinite words and their relationships
- Quantum Finite Automata: A Modern Introduction
- Quantum Pushdown Automata with Garbage Tape
- Improved constructions for succinct affine automata
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Two-way and one-way quantum and classical automata with advice for online minimization problems
- Language Recognition Power and Succinctness of Affine Automata
- Classical and Quantum Computations with Restricted Memory
This page was built for publication: Superiority of exact quantum automata for promise problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q413305)
