Unbounded-error quantum computation with small space bounds

DOI10.1016/j.ic.2011.01.008zbMath1221.68092arXiv1007.3624OpenAlexW2164423904MaRDI 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 automataprobabilistic Turing machinesprobabilistic finite automatasublogarithmic spacequantum Turing machinesunbounded error

Mathematics Subject Classification ID

Related Items (44)

Polynomially ambiguous probabilistic automata on restricted languages ⋮ Unary probabilistic and quantum automata on promise problems ⋮ Quantum alternation ⋮ Very narrow quantum OBDDs and width hierarchies for classical OBDDs ⋮ One-Way Finite Automata with Quantum and Classical States ⋮ Complexity Bounds of Constant-Space Quantum Computation ⋮ Quantum hedging in two-round prover-verifier interactions ⋮ Affine automata verifiers ⋮ Unnamed Item ⋮ When are emptiness and containment decidable for probabilistic automata? ⋮ Quantum Finite Automata: A Modern Introduction ⋮ From Quantum Query Complexity to State Complexity ⋮ State succinctness of two-way finite automata with quantum and classical states ⋮ Unnamed Item ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ Language recognition power and succinctness of affine automata ⋮ Superiority of exact quantum automata for promise problems ⋮ Unnamed Item ⋮ On a Conjecture by Christian Choffrut ⋮ Exponentially more concise quantum recognition of non-RMM regular languages ⋮ The complexity of debate checking ⋮ Quantum Pushdown Automata with Garbage Tape ⋮ QUANTUM COUNTER AUTOMATA ⋮ SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES ⋮ On the complexity of minimizing probabilistic and quantum automata ⋮ TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES ⋮ More on quantum, stochastic, and pseudo stochastic languages with few states ⋮ Quantum computation with write-only memory ⋮ Affine Computation and Affine Automaton ⋮ Unbounded-error quantum computation with small space bounds ⋮ 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 ⋮ Uncountable classical and quantum complexity classes ⋮ Polynomially Ambiguous Probabilistic Automata on Restricted Languages ⋮ Looking for Pairs that Hard to Separate: A Quantum Approach ⋮ Characterizations of one-way general quantum finite automata ⋮ Multi-letter quantum finite automata: decidability of the equivalence and minimization of states ⋮ FINITE AUTOMATA WITH ADVICE TAPES ⋮ Improved constructions for succinct affine automata ⋮ Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata ⋮ On hybrid models of quantum finite automata ⋮ Computation with multiple CTCs of fixed length and width

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

This page was built for publication: Unbounded-error quantum computation with small space bounds