Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910400218398720 |
|---|---|
| author | Keil, J. Mark McLeod, Fraser Mondal, Debajyoti |
| author_facet | Keil, J. Mark McLeod, Fraser Mondal, Debajyoti |
| contents | The classical 3SUM conjecture states that the class of 3SUM-hard problems does not admit a truly subquadratic $O(n^{2-δ})$-time algorithm, where $δ>0$, in classical computing. The geometric 3SUM-hard problems have widely been studied in computational geometry and recently, these problems have been examined under the quantum computing model. For example, Ambainis and Larka [TQC'20] designed a quantum algorithm that can solve many geometric 3SUM-hard problems in $O(n^{1+o(1)})$-time, whereas Buhrman [ITCS'22] investigated lower bounds under quantum 3SUM conjecture that claims there does not exist any sublinear $O(n^{1-δ})$-time quantum algorithm for the 3SUM problem. The main idea of Ambainis and Larka is to formulate a 3SUM-hard problem as a search problem, where one needs to find a point with a certain property over a set of regions determined by a line arrangement in the plane. The quantum speed-up then comes from the application of the well-known quantum search technique called Grover search over all regions.
This paper further generalizes the technique of Ambainis and Larka for some 3SUM-hard problems when a solution may not necessarily correspond to a single point or the search regions do not immediately correspond to the subdivision determined by a line arrangement. Given a set of $n$ points and a positive number $q$, we design $O(n^{1+o(1)})$-time quantum algorithms to determine whether there exists a triangle among these points with an area at most $q$ or a unit disk that contains at least $q$ points. We also give an $O(n^{1+o(1)})$-time quantum algorithm to determine whether a given set of intervals can be translated so that it becomes contained in another set of given intervals and discuss further generalizations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04535 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond Keil, J. Mark McLeod, Fraser Mondal, Debajyoti Computational Geometry Data Structures and Algorithms 68Q12 F.2 The classical 3SUM conjecture states that the class of 3SUM-hard problems does not admit a truly subquadratic $O(n^{2-δ})$-time algorithm, where $δ>0$, in classical computing. The geometric 3SUM-hard problems have widely been studied in computational geometry and recently, these problems have been examined under the quantum computing model. For example, Ambainis and Larka [TQC'20] designed a quantum algorithm that can solve many geometric 3SUM-hard problems in $O(n^{1+o(1)})$-time, whereas Buhrman [ITCS'22] investigated lower bounds under quantum 3SUM conjecture that claims there does not exist any sublinear $O(n^{1-δ})$-time quantum algorithm for the 3SUM problem. The main idea of Ambainis and Larka is to formulate a 3SUM-hard problem as a search problem, where one needs to find a point with a certain property over a set of regions determined by a line arrangement in the plane. The quantum speed-up then comes from the application of the well-known quantum search technique called Grover search over all regions. This paper further generalizes the technique of Ambainis and Larka for some 3SUM-hard problems when a solution may not necessarily correspond to a single point or the search regions do not immediately correspond to the subdivision determined by a line arrangement. Given a set of $n$ points and a positive number $q$, we design $O(n^{1+o(1)})$-time quantum algorithms to determine whether there exists a triangle among these points with an area at most $q$ or a unit disk that contains at least $q$ points. We also give an $O(n^{1+o(1)})$-time quantum algorithm to determine whether a given set of intervals can be translated so that it becomes contained in another set of given intervals and discuss further generalizations. |
| title | Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond |
| topic | Computational Geometry Data Structures and Algorithms 68Q12 F.2 |
| url | https://arxiv.org/abs/2404.04535 |