Superiority of exact quantum automata for promise problems
arXiv:1101.3837 · doi:10.1016/j.ipl.2012.01.001
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.
A completely new version. 6 pages. (The previous version contains some errata.)
References in corpus (1)
Cited by in corpus (13)
- On the state complexity of semi-quantum finite automata
- Generalizations of the distributed Deutsch-Jozsa promise problem
- Potential of quantum finite automata with exact acceptance
- Quantum finite automata: survey, status and research directions
- Language recognition power and succintness of affine automata
- Space Complexity of Streaming Algorithms on Universal Quantum Computers
- Nuclear Electric Resonance for Spatially-Resolved Spin Control via Pulsed Optical Excitation in the UV-Visible Spectrum
- Communication complexity of promise problems and their applications to finite automata
- Exact quantum algorithms have advantage for almost all Boolean functions
- State succinctness of two-way finite automata with quantum and classical states
- Quantum Pushdown Automata with a Garbage Tape
- Promise problems solved by quantum and classical finite automata
- Classically Time-Controlled Quantum Automata: Definition and Properties