TY - GEN
T1 - Quantum algorithms for computational geometry problems
AU - Ambainis, Andris
AU - Larka, Nikita
N1 - Publisher Copyright:
© Andris Ambainis and Nikita Larka.
PY - 2020/6/1
Y1 - 2020/6/1
N2 - 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 ?(n2-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(nc) time quantumly, for c < 2? We answer this question affirmatively, by constructing a quantum algorithm that solves Point-On-3-Lines in time O(n1+o(1)). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n1+o(1)) time algorithm for many 3Sum-Hard geometrical problems.
AB - 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 ?(n2-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(nc) time quantumly, for c < 2? We answer this question affirmatively, by constructing a quantum algorithm that solves Point-On-3-Lines in time O(n1+o(1)). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n1+o(1)) time algorithm for many 3Sum-Hard geometrical problems.
KW - 3Sum problem
KW - Amplitude amplification
KW - Computational geometry
KW - Quantum algorithms
KW - Quantum search
UR - https://drops.dagstuhl.de/opus/volltexte/2020/12068/
UR - https://www.scopus.com/pages/publications/85092627624
U2 - 10.4230/LIPIcs.TQC.2020.9
DO - 10.4230/LIPIcs.TQC.2020.9
M3 - Conference paper
SN - 978-395977146-7
SN - 9783959771467
VL - 158
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
CY - Wadern
ER -