Quantum Speedup for Geometric 3SUM-Hard Problems

Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond J. Mark Keil Debajyoti Mondal Fraser McLeod Department of Computer Science University of Saskatchewan, Saskatoon, Canada The 36th Canadian Conference on Computational Geometry (CCCG 2024)

3SUM-hard Problems Given a set S of n numbers, the 3SUM problem asks whether there are elements a, b, c S such that a + b + c = 0. The class of 3SUM-hard problems consists of problems that are at least as hard as the 3SUM problem. Classical 3SUM-hard Conjecture: 3SUM-hard problems does not admit a truly subquadratic O(n2 )-time algorithm, where > 0, in classical computing. The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Solving 3SUM in a Quantum Computer Grover s Search Algorithm [STOC 96]:Given a set of n elements, there is a bounded error quantum procedure that can find an element x with ?queries By combining Grover Search with a technique called Amplitude Amplification a constant number of times, we can achieve a high success probability Brassard et al. [Contemporary Mathematics 02] The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Solving 3SUM in a Quantum Computer Grover s Search Algorithm [STOC 96]:Given a set of n elements, there is a bounded error quantum procedure that can find an element x with ?queries By combining Grover Search with a technique called Amplitude Amplification a constant number of times, we can achieve a high success probability Brassard et al. [Contemporary Mathematics 02] Solving 3SUM in O(n log n) quantum time Maintain the elements of S in a balanced binary search tree so that for each pair a and b, we can decide the existence of (a + b) S in O(log n) time. There are O(n2) pairs and using Grover search on them takes O(n log n) quantum time The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Geometric 3SUM-hard Problems q-Points in a Disk Is there a unit disk that contains at least q points? q-Area Triangle Is there a triangle of area at most q? Point-On-3-Lines Is there a point that lies on three lines? Area q q = 4 The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Geometric 3SUM-hard Problems Disjoint projections* Determine a line such that the objects project disjointly on that line? Polygon Cutting Is there a line that intersects e and cuts the polygon into exactly K pieces? Interval Containment Can P be translated so that it gets contained in Q? P e Q *Can be solved in O(n2 log n) time but not yet known to be 3SUM-hard K = 4 The 36th Canadian Conference on Computational Geometry (CCCG 2024)

How Fast Can We Solve in a Quantum Computer? q-Points in a Disk Is there a unit disk that contains at least q points? q-Area Triangle Is there a triangle of area at most q? Point-On-3-Lines Is there a point that lies on three lines? Area q q = 4 The 36th Canadian Conference on Computational Geometry (CCCG 2024)

How Fast Can We Solve in a Quantum Computer? Point-On-3-Lines Is there a point that lies on three lines? Ambainis and Larka [TQC'2020] showed how to solve a variety of 3SUM-Hard problems in ? ??+?(?)quantum time. Point-On-3-Lines Triangles-Cover-Triangle Point-Covering IDEA: Formulate the problem as a point search problem over a set of regions determined by a line arrangement The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Ambainis and Larkas Approach [TQC'2020] Consider a random set of k lines Point-On-3-Lines Is there a point that lies on three lines? Triangulate the arrangement to get O(k2) regions ? ? ? Check each corner of these regions in O(nk2) time ? ?? ? ? ? ? ? Search over O(k2) regions recursively using Grover search The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Ambainis and Larkas Approach [TQC'2020] Consider a random set of k lines Point-On-3-Lines Is there a point that lies on three lines? Triangulate the arrangement to get O(k2) regions ? ? ? Check each corner of these regions in O(nk2) time ? ?? ? ? ? ? ? Search over O(k2) regions recursively using Grover search What to do if a subproblem size is large? The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Ambainis and Larkas Approach [TQC'2020] Consider a random set of k lines Point-On-3-Lines Is there a point that lies on three lines? getting a large subproblem is small If a large subproblem appears, then return error and repeat Choose k such that The probability of Triangulate the arrangement to get O(k2) regions ? ? ? Check each corner of these regions in O(nk2) time ? ?? ? ? ? ? ? Search over O(k2) regions recursively using Grover search What to do if a subproblem size is large? The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Motivating Question q-Points in a Disk q-Area Triangle Can we speed up 3SUM-hard problems when a solution does not necessarily correspond to a single point, or Disjoint projections* Polygon Cutting Interval Containment the search regions are not determined by a line arrangement? P e Q The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Motivating Question q-Points in a Disk q-Area Triangle Can we speed up 3SUM-hard problems when a solution does not necessarily correspond to a single point, or Contribution All of these problems can be Disjoint projections* Polygon Cutting Interval Containment solved in O(n1+o(1)) quantum time the search regions are not determined by a line arrangement? P e Q The 36th Canadian Conference on Computational Geometry (CCCG 2024)

A Recursive Quantum Search Framework If the problem size is small (base case), then search exhaustively Else decompose the subproblem and search for a solution that spans two or more subproblems If any of the subproblems is large, then return error Else every subproblem is of small size, and we can apply Grover search to obtain the desired speed up The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Using the Quantum Search Framework Point-On-3-Lines: Is there a point that lies on three lines? If the problem size is small (base case), then search exhaustively Else decompose the subproblem and search for a solution that spans two or more subproblems If any of the subproblems is large, then return error ? ? ? ? ?? ? ? ? ? ? Else every subproblem is of small size, and we can apply Grover search to obtain the desired speed up The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Using the Quantum Search Framework for q-Area Triangle Is there a triangle of area at most q? Area q The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Adapt the Classical O(n2)-time Algorithm for Finding a Minimum Area Triangle o a c b Dual Lines Primal Plane Let o be the intersection of two dual lines a and b The dual line c with the smallest vertical distance from o determines the minimum area triangle containing a and b. Find the vertex-edge pair (o,c ) by examining the faces in O(n2) time The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Quantum Search Framework for q-Area Triangle (Search for o,c* in the Dual Plane) If the problem size is small (base case), then search exhaustively Else decompose the subproblem and search for a solution that spans two or more subproblems If any of the subproblems is large, then return error o o a c c b Else every subproblem is of small size, and we can apply Grover search to obtain the desired speed up Examples when no subproblem contains both o and c* The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Using the Quantum Search Framework for q-Points in a Disk Is there a unit disk that contains at least q points? q = 4 The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Using the Quantum Search Framework for q-Points in a Disk Find a Point that Hits q-Disks q-Points in a Disk The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Using the Quantum Search Framework for q-Points in a Disk Create 4 pseudo-lines per disk to create an arrangement this helps proving subproblem sizes are small Find a Point that Hits q-Disks The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Quantum Search Framework for q-Points in a Disk (Search for a point that hits q disks) If the problem size is small (base case), then search exhaustively Else decompose the subproblem and search for a solution that spans two or more subproblems If any of the subproblems is large, then return error Else every subproblem is of small size, and we can apply Grover search to obtain the desired speed up Example when no subproblem contains the entire solution region The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Using Quantum Search Framework Pair Search in a grid Disjoint projections* Determine a line such that the objects project disjointly on that line? Polygon Cutting Is there a line that intersects e and cuts the polygon into exactly K pieces? Interval Containment Can P be translated so that it gets contained in Q? P e Q *Can be solved in O(n2 log n) time but not yet known to be 3SUM- hard K = 4 The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Using Quantum Search Framework Pair Search in a grid Interval Containment Can P be translated so that it gets contained in Q? P Q The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Further Extensions The technique is useful also for d-tuple search when d O(1) Search in a d-dimensional arrangement where the cells are hypercubes kSUM hard in O(n1+o(1)) quantum time when k O(1) x1, x2, , xk S such that x1 + x2+ + xk = 0. a, b, c S such that a + b + c = 0. The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Direction for Future Research Prove that no sublinear-time quantum algorithm exists for these problems there already are some work along this line of research by Buhrman et al. [STACS 21, ITCS 22] Expand the class of problems for which we can obtain the speed up many 3SUM-hard problems listed by Gajentaan and Overmars in [CGTA 95] are still open Triangle-Measure Visibility-From-Infinity Planar-Motion-Planning 3D-Motion-Planning The 36th Canadian Conference on Computational Geometry (CCCG 2024)

Direction for Future Research Prove that no sublinear-time quantum algorithm exists for these problems there already are some work along this line of research by Buhrman et al. [STACS 21, ITCS 22] Expand the class of problems for which we can obtain the speed up many 3SUM-hard problems listed by Gajentaan and Overmars in [CGTA 95] are still open Triangle-Measure Visibility-From-Infinity Planar-Motion-Planning 3D-Motion-Planning Thank You! The 36th Canadian Conference on Computational Geometry (CCCG 2024)