Quantum Combine And Conquer And Its Applications To Sublinear Quantum Convex Hull And Maxima Set Construction | Awesome Quantum Computing Papers

Quantum Combine And Conquer And Its Applications To Sublinear Quantum Convex Hull And Maxima Set Construction

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.

Explore more on:
Quantum Algorithms
Similar Work
Loading…