Time hierarchies for sublogarithmic-space quantum computation

DOI10.1016/J.TCS.2025.115639MaRDI QIDQ6884857zbMATH OpenFDO

Authors A. C. Cem Say

Publication date 12 December 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115639

zbMATH Keywords

quantum finite automataquantum Turing machinessublogarithmic space complexitytime complexity

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Quantum algorithms and complexity in the theory of computing (68Q12) Formal languages and automata (68Q45) Quantum computation (81P68)

Cites work

• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Finite state verifiers I
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• Lower space bounds for randomized computation
• On the complexity of simulating space-bounded quantum computations
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Succinctness of two-way probabilistic and quantum finite automata
• The power of a single qubit: two-way quantum finite automata and the word problem
• Two-way finite automata with quantum and classical states.
• Unconditional proofs of quantumness between small-space machines

This page was built for publication: Time hierarchies for sublogarithmic-space quantum computation

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