DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2020.9

Quantum Algorithms for Computational Geometry Problems

Authors: Andris Ambainis and Nikita Larka

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract

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.

Cite as

Andris Ambainis and Nikita Larka. Quantum Algorithms for Computational Geometry Problems. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 9:1-9:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2020.9,
  author =	{Ambainis, Andris and Larka, Nikita},
  title =	{{Quantum Algorithms for Computational Geometry Problems}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{9:1--9:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.9},
  URN =		{urn:nbn:de:0030-drops-120687},
  doi =		{10.4230/LIPIcs.TQC.2020.9},
  annote =	{Keywords: Quantum algorithms, quantum search, computational geometry, 3Sum problem, amplitude amplification}
}

Search Results

Documents authored by Larka, Nikita

Quantum Algorithms for Computational Geometry Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message