Unbounded-error quantum computation with small space bounds
From MaRDI portal
Publication:550246
DOI10.1016/j.ic.2011.01.008zbMath1221.68092arXiv1007.3624MaRDI QIDQ550246
A. C. Cem Say, Abuzer Yakaryılmaz
Publication date: 8 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1007.3624
quantum finite automata; probabilistic Turing machines; probabilistic finite automata; sublogarithmic space; quantum Turing machines; unbounded error
68Q45: Formal languages and automata
68Q12: Quantum algorithms and complexity in the theory of computing
Related Items
Unnamed Item, On a Conjecture by Christian Choffrut, Quantum Pushdown Automata with Garbage Tape, QUANTUM COUNTER AUTOMATA, SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES, TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES, Uncountable classical and quantum complexity classes, FINITE AUTOMATA WITH ADVICE TAPES, Affine Computation and Affine Automaton, Debates with Small Transparent Quantum Verifiers, Computation with multiple CTCs of fixed length and width, State succinctness of two-way finite automata with quantum and classical states, Superiority of exact quantum automata for promise problems, Exponentially more concise quantum recognition of non-RMM regular languages, The complexity of debate checking, Unbounded-error quantum computation with small space bounds, On the complexity of minimizing probabilistic and quantum automata, Characterizations of one-way general quantum finite automata, Multi-letter quantum finite automata: decidability of the equivalence and minimization of states, Unary probabilistic and quantum automata on promise problems, Quantum computation with write-only memory, More on quantum, stochastic, and pseudo stochastic languages with few states, Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata, On hybrid models of quantum finite automata, Quantum alternation, Very narrow quantum OBDDs and width hierarchies for classical OBDDs, Language Recognition Power and Succinctness of Affine Automata, Looking for Pairs that Hard to Separate: A Quantum Approach, Quantum Finite Automata: A Modern Introduction, From Quantum Query Complexity to State Complexity, Potential of Quantum Finite Automata with Exact Acceptance, One-Way Finite Automata with Quantum and Classical States, Complexity Bounds of Constant-Space Quantum Computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Superiority of exact quantum automata for promise problems
- Unbounded-error quantum computation with small space bounds
- Exponential separation of quantum and classical online space complexity
- Efficient probability amplification in two-way quantum finite automata
- Turing machines with sublogarithmic space
- Quantum automata and quantum grammars
- Two-way finite automata with quantum and classical states.
- On the complexity of simulating space-bounded quantum computations
- Space-bounded quantum complexity
- Algebraic results on quantum automata
- Determining the equivalence for one-way quantum finite automata
- Undecidability on quantum finite automata
- Characterizations of 1-Way Quantum Finite Automata
- Languages Recognized with Unbounded Error by Quantum Finite Automata
- Various Aspects of Finite Quantum Automata
- Stochasticity of the languages acceptable by two-way finite probabilistic automata
- Quantum Complexity Theory
- Lower space bounds for randomized computation
- Decidable and Undecidable Problems about Quantum Automata
- Probabilistic automata
- Generalized Automata and Stochastic Languages
- A context-free language which is not acceptable by a probabilistic automaton
- Encyclopedia of Complexity and Systems Science
- Analogies and differences between quantum and stochastic automata
