2026-07-24T03:37:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23203 2025-10-02T12:42:55Z ddc:004 open_access

Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction Fukuzawa, Shion Goodrich, Michael T. Irani, Sandy quantum computing computational geometry divide and conquer convex hulls maxima sets 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 Õ(√{nh}) time, w.h.p., where h is the size of the output. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shion Fukuzawa and Michael T. Goodrich and Sandy Irani 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.51 urn:nbn:de:0030-drops-232035 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.51 eng https://creativecommons.org/licenses/by/4.0/legalcode