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)

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

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)