Superiority of exact quantum automata for promise problems
From MaRDI portal
(Redirected from Publication:413305)
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.
Recommendations
- Promise problems solved by quantum and classical finite automata
- Complexity of promise problems on classical and quantum automata
- 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
Cites work
- scientific article; zbMATH DE number 2040892 (Why is no real title available?)
- scientific article; zbMATH DE number 1839459 (Why is no real title available?)
- Encyclopedia of Complexity and Systems Science
- On quantum and probabilistic communication: Las Vegas and one-way protocols
- Quantum Complexity Theory
- Quantum Queries on Permutations with a Promise
- Quantum automata and quantum grammars
- Quantum lower bounds by polynomials
- Quantum zero-error algorithms cannot be composed
- Unbounded-error quantum computation with small space bounds
Cited in
(40)- State succinctness of two-way finite automata with quantum and classical states
- Language Recognition Power and Succinctness of Affine Automata
- Quantum online streaming algorithms with logarithmic memory
- Classical and Quantum Computations with Restricted Memory
- On the power of one-way automata with quantum and classical states
- On the computational power of affine automata
- scientific article; zbMATH DE number 7104930 (Why is no real title available?)
- 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
- Implications of quantum automata for contextuality
- From quantum query complexity to state complexity
- Generalizations of the distributed Deutsch-Jozsa promise problem
- The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
- Promise problems solved by quantum and classical finite automata
- On language varieties without Boolean operations
- Uncountable classical and quantum complexity classes
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Affine computation and affine automaton
- Quantum alternation
- Quantum pushdown automata with garbage tape
- Nondeterministic unitary OBDDs
- Complexity of promise problems on classical and quantum automata
- Potential of quantum finite automata with exact acceptance
- Looking for Pairs that Hard to Separate: A Quantum Approach
- Language recognition power and succinctness of affine automata
- On a conjecture by Christian Choffrut
- One-way topological automata and the tantalizing effects of their topological features
- Quantum finite automata: a modern introduction
- Real-valued affine automata compute beyond Turing machines
- An exact quantum algorithm for a restricted subtraction game
- Quantum versus classical online streaming algorithms with logarithmic size of memory
- Quaternionic quantum automata
- Quantum online algorithms with respect to space and advice complexity
- Quantum finite automata: advances on Bertoni's ideas
- Deterministic construction of QFAs based on the quantum fingerprinting technique
- Quantum \(\omega\)-automata over infinite words and their relationships
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Improved constructions for succinct affine automata
- Two-way and one-way quantum and classical automata with advice for online minimization problems
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)
