Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the"marriage-before-conquest"technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in $\tilde{O}(\sqrt{nh})$ time, w.h.p., where $h$ is the size of the output.