Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908308311375872 |
|---|---|
| author | Fukuzawa, Shion Goodrich, Michael T. Irani, Sandy |
| author_facet | Fukuzawa, Shion Goodrich, Michael T. Irani, Sandy |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06376 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction Fukuzawa, Shion Goodrich, Michael T. Irani, Sandy Computational Geometry Quantum Physics 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. |
| title | Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction |
| topic | Computational Geometry Quantum Physics |
| url | https://arxiv.org/abs/2504.06376 |