Unbounded-error quantum computation with small space bounds

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

zbMATH Keywords

quantum finite automata; probabilistic Turing machines; probabilistic finite automata; sublogarithmic space; quantum Turing machines; unbounded error

Mathematics Subject Classification ID

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, Quantum hedging in two-round prover-verifier interactions, Unnamed Item, Unnamed Item, QUANTUM COUNTER AUTOMATA, SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES, Unnamed Item, TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES, Uncountable classical and quantum complexity classes, Polynomially Ambiguous Probabilistic Automata on Restricted Languages, FINITE AUTOMATA WITH ADVICE TAPES, Affine Computation and Affine Automaton, Debates with Small Transparent Quantum Verifiers, How does adiabatic quantum computation fit into quantum automata theory?, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, Language recognition power and succinctness of affine automata, 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, Improved constructions for succinct affine automata, Polynomially ambiguous probabilistic automata on restricted languages, Affine automata verifiers, 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, When are emptiness and containment decidable for probabilistic automata?, 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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item