Unbounded-error quantum computation with small space bounds

DOI10.1016/J.IC.2011.01.008zbMATH Open1221.68092arXiv1007.3624OpenAlexW2164423904MaRDI QIDQ550246FDOQ550246

Authors: Abuzer Yakaryılmaz, A. C. Cem Say 

Publication date: 8 July 2011

Published in: Information and Computation (Search for Journal in Brave)

Abstract: We prove the following facts about the language recognition power of quantum Turing machines (QTMs) in the unbounded error setting: QTMs are strictly more powerful than probabilistic Turing machines for any common space bound $s$ satisfying $s(n)=o(loglogn)$. For "one-way" Turing machines, where the input tape head is not allowed to move left, the above result holds for $s(n)=o(logn)$. We also give a characterization for the class of languages recognized with unbounded error by real-time quantum finite automata (QFAs) with restricted measurements. It turns out that these automata are equal in power to their probabilistic counterparts, and this fact does not change when the QFA model is augmented to allow general measurements and mixed states. Unlike the case with classical finite automata, when the QFA tape head is allowed to remain stationary in some steps, more languages become recognizable. We define and use a QTM model that generalizes the other variants introduced earlier in the study of quantum space complexity.

Full work available at URL: https://arxiv.org/abs/1007.3624

Recommendations

• Unbounded-Error Quantum Query Complexity
• Unbounded-error quantum query complexity
• scientific article; zbMATH DE number 6820203
• Space-bounded quantum complexity
• Complexity bounds of constant-space quantum computation
• Unbounded-Error Classical and Quantum Communication Complexity
• On the computational power of bounded error quantum Turing machines
• On the complexity of simulating space-bounded quantum computations
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 2038718

zbMATH Keywords

quantum finite automataprobabilistic Turing machinesprobabilistic finite automatasublogarithmic spacequantum Turing machinesunbounded error

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Two-way finite automata with quantum and classical states.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Succinctness of two-way probabilistic and quantum finite automata
• Unbounded-error quantum computation with small space bounds
• Title not available (Why is that?)
• Probabilistic automata
• Title not available (Why is that?)
• Quantum Complexity Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Turing machines with sublogarithmic space
• Encyclopedia of Complexity and Systems Science
• Title not available (Why is that?)
• Quantum automata and quantum grammars
• Algebraic results on quantum automata
• Determining the equivalence for one-way quantum finite automata
• Characterizations of 1-Way Quantum Finite Automata
• Languages recognized by nondeterministic quantum finite automata
• Superiority of exact quantum automata for promise problems
• Various Aspects of Finite Quantum Automata
• Undecidability on quantum finite automata
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• Lower space bounds for randomized computation
• Generalized Automata and Stochastic Languages
• On the complexity of simulating space-bounded quantum computations
• Decidable and Undecidable Problems about Quantum Automata
• Analogies and differences between quantum and stochastic automata
• Efficient probability amplification in two-way quantum finite automata
• Space-bounded quantum complexity
• Stochasticity of the languages acceptable by two-way finite probabilistic automata
• Title not available (Why is that?)
• A context-free language which is not acceptable by a probabilistic automaton
• Exponential separation of quantum and classical online space complexity

Cited In (50)

• State succinctness of two-way finite automata with quantum and classical states
• Superiority of exact quantum automata for promise problems
• Computation with multiple CTCs of fixed length and width
• Title not available (Why is that?)
• Unbounded-error quantum computation with small space bounds
• Title not available (Why is that?)
• Exponentially more concise quantum recognition of non-RMM regular languages
• From quantum query complexity to state complexity
• Quantum alternation
• Characterizations of one-way general quantum finite automata
• Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Uncountable classical and quantum complexity classes
• Finite automata with advice tapes
• Quantum hedging in two-round prover-verifier interactions
• Affine computation and affine automaton
• More on quantum, stochastic, and pseudo stochastic languages with few states
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Some languages recognized by two-way finite automata with quantum and classical states
• Quantum alternation
• One-way finite automata with quantum and classical states
• Unary probabilistic and quantum automata on promise problems
• Quantum pushdown automata with garbage tape
• Quantum computation with devices whose contents are never read
• Complexity bounds of constant-space quantum computation
• Potential of quantum finite automata with exact acceptance
• Space-bounded quantum complexity
• On hybrid models of quantum finite automata
• Language recognition power and succinctness of affine automata
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• Looking for Pairs that Hard to Separate: A Quantum Approach
• How does adiabatic quantum computation fit into quantum automata theory?
• Debates with small transparent quantum verifiers
• On a conjecture by Christian Choffrut
• One-way topological automata and the tantalizing effects of their topological features
• On the complexity of minimizing probabilistic and quantum automata
• Quantum counter automata
• Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
• Quantum finite automata: a modern introduction
• On the computational power of bounded error quantum Turing machines
• When is containment decidable for probabilistic automata?
• When are emptiness and containment decidable for probabilistic automata?
• The complexity of debate checking
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• Time-Space Complexity Advantages for Quantum Computing
• Title not available (Why is that?)
• Improved constructions for succinct affine automata
• Polynomially ambiguous probabilistic automata on restricted languages
• Affine automata verifiers
• Language Recognition Power and Succinctness of Affine Automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q550246)