2026-08-18T03:15:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12068 2024-03-06T10:49:12Z ddc:004 open_access

Quantum Algorithms for Computational Geometry Problems Ambainis, Andris Larka, Nikita Quantum algorithms quantum search computational geometry 3Sum problem amplitude amplification We study quantum algorithms for problems in computational geometry, such as Point-On-3-Lines problem. In this problem, we are given a set of lines and we are asked to find a point that lies on at least 3 of these lines. Point-On-3-Lines and many other computational geometry problems are known to be 3Sum-Hard. That is, solving them classically requires time Ω(n^{2-o(1)}), unless there is faster algorithm for the well known 3Sum problem (in which we are given a set S of n integers and have to determine if there are a, b, c ∈ S such that a + b + c = 0). Quantumly, 3Sum can be solved in time O(n log n) using Grover’s quantum search algorithm. This leads to a question: can we solve Point-On-3-Lines and other 3Sum-Hard problems in O(n^c) time quantumly, for c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves Point-On-3-Lines in time O(n^{1 + o(1)}). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n^{1 + o(1)}) time algorithm for many 3Sum-Hard geometrical problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andris Ambainis and Nikita Larka 2020 Is Part Of LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2020.9 urn:nbn:de:0030-drops-120687 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode