Document Open Access Logo

Quantum Algorithms for Computational Geometry Problems

Authors Andris Ambainis , Nikita Larka

PDF
Thumbnail PDF

File

LIPIcs.TQC.2020.9.pdf
  • Filesize: 0.58 MB
  • 10 pages

Document Identifiers

Author Details

Andris Ambainis
  • Faculty of Computing, University of Latvia, Raina bulvaris 19, Riga, LV-1586, Latvia
Nikita Larka
  • Faculty of Computing, University of Latvia, Raina bulvaris 19, Riga, LV-1586, Latvia

Funding

Supported by the ERDF project 1.1.1.5/18/A/020 "Quantum algorithms: from complexity theory to experiment".

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.TQC.2020.9

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum query complexity
  • Theory of computation → Computational geometry
Keywords
  • Quantum algorithms
  • quantum search
  • computational geometry
  • 3Sum problem
  • amplitude amplification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang. On the quantum complexity of closest pair and related problems. CoRR, abs/1911.01973, 2019. URL: http://arxiv.org/abs/1911.01973.
  2. Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210-239, 2007. URL: https://doi.org/10.1137/S0097539705447311.
  3. Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. Quantum speedups for exponential-time dynamic programming algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 1783-1793, Philadelphia, PA, USA, 2019. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3310435.3310542.
  4. Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis. Quadratic speedup for finding marked vertices by quantum walks. CoRR, abs/1903.07493, 2019. URL: http://arxiv.org/abs/1903.07493.
  5. Simon Apers, András Gilyén, and Stacey Jeffery. A unified framework of quantum walk search. CoRR, abs/1912.04233, 2019. URL: http://arxiv.org/abs/1912.04233.
  6. Aleksandrs Belovs and Robert Spalek. Adversary lower bound for the k-sum problem. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pages 323-328. ACM, 2013. URL: https://doi.org/10.1145/2422436.2422474.
  7. Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002. Google Scholar
  8. Harry Buhrman, Subhasree Patro, and Florian Speelman. The quantum strong exponential-time hypothesis. CoRR, abs/1911.05686, 2019. URL: http://arxiv.org/abs/1911.05686.
  9. Bernard Chazelle, Leo J. Guibas, and D. T. Lee. The power of geometric duality. BIT Numerical Mathematics, 25, 1985. URL: https://doi.org/10.1007/BF01934990.
  10. Andrew M. Childs and Jason M. Eisenberg. Quantum algorithms for subset finding. Quantum Information & Computation, 5(7):593-604, 2005. URL: http://portal.acm.org/citation.cfm?id=2011663.
  11. Bartholomew Furrow. A panoply of quantum algorithms. Quantum Information & Computation, 8(8):834-859, 2008. URL: http://www.rintonpress.com/xxqic8/qic-8-89/0834-0859.pdf.
  12. Anka Gajentaan and Mark H. Overmars. On a class of o(n2) problems in computational geometry. Comput. Geom., 5:165-185, 1995. URL: https://doi.org/10.1016/0925-7721(95)00022-2.
  13. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical review letters, 100:160501, April 2008. URL: https://doi.org/10.1103/PhysRevLett.100.160501.
  14. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 212-219, New York, NY, USA, 1996. ACM. URL: https://doi.org/10.1145/237814.237866.
  15. Allan Grønlund Jørgensen and Seth Pettie. Threesomes, degenerates, and love triangles. CoRR, abs/1404.0799, 2014. URL: http://arxiv.org/abs/1404.0799.
  16. Lov K. Grover. Framework for fast quantum mechanical algorithms. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 80, December 1997. URL: https://doi.org/10.1145/276698.276712.
  17. Frédéric Magniez, Miklos Santha, and Mario Szegedy. Quantum algorithms for the triangle problem. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pages 1109-1117, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1070432.1070591.
  18. Mario Szegedy. Quantum speed-up of markov chain based algorithms. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 32-41. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/FOCS.2004.53.
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 About DROPS Imprint Privacy Contact