Time-Space Complexity Advantages for Quantum Computing

DOI10.1007/978-3-319-71069-3_24MaRDI QIDQ5055992zbMATH OpenOpenAlexFDO

Authors Shenggen Zheng, Jozef Gruska, Daowen Qiu

Publication date 9 December 2022

Published in Theory and Practice of Natural Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-71069-3_24

zbMATH Keywords

quantum computingtime-space complexity

Mathematics Subject Classification ID

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

Recommendations

• Unbounded-error quantum computation with small space bounds
• Space-bounded quantum complexity
• scientific article; zbMATH DE number 1335895
• State succinctness of two-way finite automata with quantum and classical states
• Exponential separation of quantum and classical online space complexity

Cites work

• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 7204504 (Why is no real title available?)
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Communication Complexity
• Complexity measures and decision tree complexity: a survey.
• Dense quantum coding and quantum finite automata
• Design and analysis of randomized algorithms. Introduction to design paradigms.
• Deterministic communication vs. partition number
• From quantum query complexity to state complexity
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Nearly optimal separations between communication (or query) complexity and partitions
• On hybrid models of quantum finite automata
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• On the distributional complexity of disjointness
• On the state complexity of semi-quantum finite automata
• One-way finite automata with quantum and classical states
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Quantum finite automata
• Quantum search of spatial regions
• Quantum time-space tradeoffs for sorting
• Separations in query complexity using cheat sheets
• Succinctness of two-way probabilistic and quantum finite automata
• Superlinear advantage for exact quantum algorithms
• Two-way finite automata with quantum and classical states.

Cited in

(1)

• Lifting query complexity to time-space complexity for two-way finite automata

This page was built for publication: Time-Space Complexity Advantages for Quantum Computing

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