Quantum time-space tradeoffs for sorting

DOI10.1145/780542.780553MaRDI QIDQ3581266zbMATH OpenOpenAlexWikidataFDO

Authors Hartmut Klauck

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/780542.780553

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum computation (81P68)

Recommendations

• Quantum complexities of ordered searching, sorting, and element distinctness
• scientific article; zbMATH DE number 2119639
• scientific article; zbMATH DE number 1756014
• A simple proof of a time-space trade-off for sorting with linear comparisons
• On the time-space tradeoff for sorting with linear queries

Cited in

(8)

• scientific article; zbMATH DE number 1756014 (Why is no real title available?)
• Quantum switching and quantum merge sorting
• Time-Space Complexity Advantages for Quantum Computing
• Lifting query complexity to time-space complexity for two-way finite automata
• Quantum time-space tradeoff for finding multiple collision pairs
• Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• Randomized vs. deterministic separation in time-space tradeoffs of multi-output functions
• On the time-space tradeoff for sorting with linear queries

This page was built for publication: Quantum time-space tradeoffs for sorting

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