On the quantum time complexity of divide and conquer

DOI10.4230/LIPICS.ICALP.2025.9MaRDI QIDQ7346436zbMATH OpenFDO

Authors Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.9

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A framework of quantum strong exponential-time hypotheses
• A note on quantum divide and conquer for minimal string rotation
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 3871387 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2038718 (Why is no real title available?)
• scientific article; zbMATH DE number 7561744 (Why is no real title available?)
• scientific article; zbMATH DE number 7829263 (Why is no real title available?)
• Klee's measure problem made easy
• Near-optimal quantum algorithms for string problems
• On some fine-grained questions in algorithms and complexity
• On the robustness of bucket brigade quantum RAM
• Quantum algorithm for lexicographically minimal string rotation
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum Walk Algorithm for Element Distinctness
• Quicksort
• Subcubic equivalences between path, matrix, and triangle problems
• Tight hardness results for maximum weight rectangles

This page was built for publication: On the quantum time complexity of divide and conquer

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