Document Open Access Logo

On the Quantum Complexity of Closest Pair and Related Problems

Authors Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.16.pdf
  • Filesize: 0.83 MB
  • 43 pages

Document Identifiers

Author Details

Scott Aaronson
  • The University of Texas at Austin, TX, USA
Nai-Hui Chia
  • The University of Texas at Austin, TX, USA
Han-Hsuan Lin
  • The University of Texas at Austin, TX, USA
Chunhao Wang
  • The University of Texas at Austin, TX, USA
Ruizhe Zhang
  • The University of Texas at Austin, TX, USA

Funding

SA was supported by a Vannevar Bush Fellowship from the US Department of Defense, a Simons Investigator Award, and the Simons "It from Qubit" collaboration. NHC, HHL, and CW were supported by SA’s Vannevar Bush Faculty Fellowship. RZ received support from the National Science Foundation (grant CCF-1648712).

Acknowledgements

We would like to thank Lijie Chen and Pasin Manurangsi for helpful discussion. We would like to thank anonymous reviewers for their valuable suggestions on this paper.

Cite AsGet BibTex

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang. On the Quantum Complexity of Closest Pair and Related Problems. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 16:1-16:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.16

Abstract

The closest pair problem is a fundamental problem of computational geometry: given a set of n points in a d-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in O(n log n) time in constant dimensions (i.e., when d = O(1)). This paper asks and answers the question of the problem’s quantum time complexity. Specifically, we give an Õ(n^(2/3)) algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In polylog(n) dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover’s algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover’s algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an n^o(1) factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Quantum complexity theory
Keywords
  • Closest pair
  • Quantum computing
  • Quantum fine grained reduction
  • Quantum strong exponential time hypothesis
  • Fine grained complexity

Metrics

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

References

  1. Scott Aaronson and Yaoyun Shi. Quantum Lower Bounds for the Collision and the Element Distinctness Problems. J. ACM, 51(4):595-605, July 2004. Google Scholar
  2. Amir Abboud, Ryan Williams, and Huacheng Yu. More Applications of the Polynomial Method to Algorithm Design. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, pages 218-230, 2015. Google Scholar
  3. Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs. Discrete &Computational Geometry, 6(3):407-422, September 1991. Google Scholar
  4. A. Ambainis. Quantum Search Algorithms. SIGACT News, 35(2):22-35, June 2004. URL: https://doi.org/10.1145/992287.992296.
  5. Andris Ambainis. Quantum Walk Algorithm for Element Distinctness. SIAM Journal on Computing, 37(1):210-239, 2007. Google Scholar
  6. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  7. Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks. In Advances in Neural Information Processing Systems, pages 4308-4318, 2017. Google Scholar
  8. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Proofs of Useful Work. IACR Cryptology ePrint Archive, 2017:203, 2017. Google Scholar
  9. C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing, 26(5):1510-1523, 1997. Google Scholar
  10. Jon Louis Bentley and Michael Ian Shamos. Divide-and-Conquer in Multidimensional Space. In Proceedings of the eighth annual ACM symposium on Theory of computing, pages 220-230. ACM, 1976. Google Scholar
  11. Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer. Quantum Algorithms for the Subset-Sum Problem. In Post-Quantum Cryptography, pages 16-33. Springer Berlin Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-38616-9_2.
  12. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential Improvement In Precision for Simulating Sparse Hamiltonians. Forum of Mathematics, Sigma, 5, 2017. URL: https://doi.org/10.1017/fms.2017.2.
  13. Sergei N Bespamyatnikh. An Optimal Algorithm for Closest-Pair Maintenance. Discrete &Computational Geometry, 19(2):175-195, 1998. Google Scholar
  14. Harry Buhrman, Christoph Durr, Mark Heiligman, Peter Hoyer, Frédéric Magniez, Miklos Santha, and Ronald De Wolf. Quantum Algorithms for Element Distinctness. In Proceedings 16th Annual IEEE Conference on Computational Complexity, pages 131-137. IEEE, 2001. Google Scholar
  15. Harry Buhrman, Subhasree Patro, and Florian Speelman. The Quantum Strong Exponential-Time Hypothesis. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.05686.
  16. Timothy M Chan and Ryan Williams. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1246-1255. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  17. Lijie Chen. On the Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.02325.
  18. Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 21-40. SIAM, 2019. Google Scholar
  19. Kenneth L Clarkson. A Randomized Algorithm for Closest-Point Queries. SIAM Journal on Computing, 17(4):830-847, 1988. Google Scholar
  20. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to Algorithms. MIT press, 2009. Google Scholar
  21. Evgeny Dantsin, Vladik Kreinovich, and Alexander Wolpert. On Quantum Versions of Record-breaking Algorithms for SAT. SIGACT News, 36(4):103-108, December 2005. URL: https://doi.org/10.1145/1107523.1107524.
  22. R. David, K. S., and B. Laekhanukit. On the Complexity of Closest Pair via Polar-Pair of Point-Sets. SIAM Journal on Discrete Mathematics, 33(1):509-527, 2019. Google Scholar
  23. Christoph Durr and Peter Hoyer. A quantum algorithm for finding the minimum. arXiv preprint, 1996. URL: http://arxiv.org/abs/quant-ph/9607014.
  24. Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-eighth ACM Symposium on Theory of Computing - STOC quotesingle96. ACM Press, 1996. URL: https://doi.org/10.1145/237814.237866.
  25. Timon Hertli. Improved Exponential Algorithms for SAT and ClSP. PhD thesis, ETH Zurich, 2015. Google Scholar
  26. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, March 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  27. Toshiya Itoh, Tatsuya Nagatani, and Jun Tarui. Explicit Construction for k-Wise Nearly Random Permutations by Iterated Feistel Transform. Workshop on Randomness and Computation, 2005. Google Scholar
  28. Stacey Jeffery. Frameworks for Quantum Algorithms. PhD thesis, University of Waterloo, 2014. Google Scholar
  29. CS Karthik and Pasin Manurangsi. On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. 10th Innovations in Theoretical Computer Science, 2019. Google Scholar
  30. S. Khuller and Y. Matias. A Simple Randomized Sieve Algorithm for the Closest-Pair Problem. Information and Computation, 118(1):34-37, 1995. Google Scholar
  31. Victor Klee. On the Complexity of d-Dimensional Voronoi Diagrams. Archiv der Mathematik, 34(1):75-80, 1980. URL: https://doi.org/10.1007/bf01224932.
  32. Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson Education India, 2006. Google Scholar
  33. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. Search via Quantum Walk. SIAM Journal on Computing, 40(1):142-164, 2011. Google Scholar
  34. Chris Marriott and John Watrous. Quantum ArthurendashMerlin games. Computational Complexity, 14(2):122-152, 2005. URL: https://doi.org/10.1007/s00037-005-0194-x.
  35. Abdullah Mueen, Eamonn Keogh, Qiang Zhu, Sydney Cash, and Brandon Westover. Exact Discovery of Time Series Motifs. In Proceedings of the 2009 SIAM international conference on data mining, pages 473-484. SIAM, 2009. Google Scholar
  36. Alexandros Nanopoulos, Yannis Theodoridis, and Yannis Manolopoulos. C2P: Clustering based on Closest Pairs. In VLDB, 2001. Google Scholar
  37. Michael A Nielsen and Isaac Chuang. Quantum Computation and Quantum Information, 2002. Google Scholar
  38. Ramamohan Paturi and Pavel Pudlák. On the Complexity of Circuit Satisfiability. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 241-250. ACM, 2010. Google Scholar
  39. Ramamohan Paturi, Pavel Pudlák, Michael E Saks, and Francis Zane. An Improved Exponential-Time Algorithm for k-SAT. Journal of the ACM (JACM), 52(3):337-364, 2005. Google Scholar
  40. Michael O Rabin. Probabilistic Algorithms Algorithms and Complexity: New Directions and Recent Results, 1976. Google Scholar
  41. Kunihiko Sadakane, Norito Sugawara, and Takeshi Tokuyama. Quantum Algorithms for Intersection and Proximity Problems. In Peter Eades and Tadao Takaoka, editors, Algorithms and Computation, pages 148-159, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. Google Scholar
  42. Dominik Scheder and John P Steinberger. PPSZ for General k-SAT-Making Hertli’s Analysis Simpler and 3-SAT Faster. In 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  43. T Schoning. A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 410-414. IEEE, 1999. Google Scholar
  44. M. I. Shamos and D. Hoey. Closest-Point Problems. In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pages 151-162, 1975. Google Scholar
  45. Mario Szegedy. Quantum Speed-Up of Markov Chain Based Algorithms. In 45th Annual IEEE symposium on foundations of computer science, pages 32-41. IEEE, 2004. Google Scholar
  46. Virginia Vassilevska Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (invited talk). In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  47. Nilton Volpato and Arnaldo Moura. A fast quantum algorithm for the closest bichromatic pair problem, 2010. Google Scholar
  48. Ryan Williams. Pairwise comparison of bit vectors. Theoretical Computer Science Stack Exchange. URL: https://cstheory.stackexchange.com/q/37369.
  49. Ryan Williams. A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications. Theoretical Computer Science, 348(2-3):357-365, 2005. Google Scholar
  50. Ryan Williams and Huacheng Yu. Finding Orthogonal Vectors In Discrete Structures. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1867-1877. SIAM, 2014. Google Scholar
  51. Raymond Chi-Wing Wong, Yufei Tao, Ada Wai-Chee Fu, and Xiaokui Xiao. On Efficient Spatial Matching. In Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB '07, pages 579-590, 2007. Google Scholar
  52. A. C. . Yao. Lower Bounds for Algebraic Computation Trees with Integer Inputs. In 30th Annual Symposium on Foundations of Computer Science, pages 308-313, 1989. Google Scholar
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