1 Search Results for "Larka, Nikita"

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-dev.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}
}
  • Refine by Author
  • 1 Ambainis, Andris
  • 1 Larka, Nikita

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Quantum query complexity

  • Refine by Keyword
  • 1 3Sum problem
  • 1 Quantum algorithms
  • 1 amplitude amplification
  • 1 computational geometry
  • 1 quantum search

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact