Unbounded-error quantum computation with small space bounds

DOI10.1016/J.IC.2011.01.008MaRDI QIDQ550246zbMATH OpenOpenAlexFDO

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

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

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

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.

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

Cites work

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

Cited in

(47)

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

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)