Document Open Access Logo

Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems

Authors François Le Gall, Saeed Seddighin

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.97.pdf
  • Filesize: 0.74 MB
  • 23 pages

Document Identifiers

Author Details

François Le Gall
  • Nagoya University, Japan
Saeed Seddighin
  • Toyota Technological Institute at Chicago, IL, USA

Funding

  • Le Gall, François: FLG was supported by the JSPS KAKENHI grants Nos. JP16H01705, JP19H04066, JP20H00579 and JP20H04139, and by the MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grant No. PMXS0120319794.
  • Seddighin, Saeed: SS was supported by a Google Research Gift.

Acknowledgements

The authors are grateful to Michael Saks and C. Seshadhri for helpful correspondence.

Cite AsGet BibTex

François Le Gall and Saeed Seddighin. Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 97:1-97:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.97

Abstract

Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for LCS and LPS are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact Õ(√n) time algorithm for LPS, we prove that LCS needs at least time ̃ Ω(n^{2/3}) even for 0/1 strings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Longest common substring
  • Longest palindrome substring
  • Quantum algorithms
  • Sublinear algorithms

Metrics

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

Related Versions

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. In Proceedings of the 35th Computational Complexity Conference, pages 16:1-16:43, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.16.
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the 56th Annual IEEE Symposium on the Foundations of Computer Science, pages 59-78, 2015. Google Scholar
  3. Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210-239, 2007. Google Scholar
  4. 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 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1783-1793, 2019. Google Scholar
  5. Andris Ambainis and Ashley Montanaro. Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information and Computation, 14(5-6):439-453, 2014. URL: https://doi.org/10.26421/QIC14.5-6-4.
  6. Amihood Amir, Panagiotis Charalampopoulos, Solon P Pissis, and Jakub Radoszewski. Longest common substring made fully dynamic. In Proceedings of the 27th Annual European Symposium on Algorithms, pages 6:1-6:17, 2018. Google Scholar
  7. Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Polylogarithmic approximation for edit distance and the asymmetric query complexity. In Proceedings of the 51st Annual IEEE Symposium on the Foundations of Computer Science, pages 377-386, 2010. Google Scholar
  8. Alexandr Andoni and Huy L. Nguyen. Near-optimal sublinear time algorithms for Ulam distance. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 76-86, 2010. URL: https://doi.org/10.1137/1.9781611973075.8.
  9. Alexandr Andoni and Negev Shekel Nosatzki. Edit distance in near-linear time: it’s a constant factor. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, 2020. Google Scholar
  10. Avinatan Hassidim Aram W. Harrow and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103:150502, 2006. Google Scholar
  11. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM Journal on Computing, 47(3):1087-1097, 2018. URL: https://doi.org/10.1137/15M1053128.
  12. Ziv Bar-Yossef, TS Jayram, Robert Krauthgamer, and Ravi Kumar. Approximating edit distance efficiently. In Proceedings of the 45th Annual IEEE Symposium on the Foundations of Computer Science, pages 550-559, 2004. Google Scholar
  13. Tuğkan Batu, Funda Ergun, and Cenk Sahinalp. Oblivious string embeddings and edit distance approximations. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 792-801, 2006. Google Scholar
  14. Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: Quantum and MapReduce. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1170-1189, 2018. Google Scholar
  15. Joshua Brakensiek and Aviad Rubinstein. Constant-factor approximation of near-linear edit distance in near-linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 685-698, 2020. Google Scholar
  16. Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002. Google Scholar
  17. Harry Buhrman, Subhasree Patro, and Florian Speelman. A framework of quantum strong exponential-time hypotheses. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, volume 187 of LIPIcs, pages 19:1-19:19, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.19.
  18. Harry Buhrman and Robert Špalek. Quantum verification of matrix products. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 880-889, 2006. Google Scholar
  19. Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucky, and Michael Saks. Approximating edit distance within constant factor in truly sub-quadratic time. In Proceedings of the 59th Annual IEEE Symposium on the Foundations of Computer Science, pages 979-990, 2018. Google Scholar
  20. Moses Charikar and Robert Krauthgamer. Embedding the Ulam metric into 𝓁₁. Theory of Computing, 2(11):207-224, 2006. Google Scholar
  21. Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, and Shigeru Yamashita. Reconstructing strings from substrings with quantum queries. In Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, pages 388-397, 2012. URL: https://doi.org/10.1007/978-3-642-31155-0_34.
  22. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. Google Scholar
  23. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. Google Scholar
  24. Martin Farach. Optimal suffix tree construction with large alphabets. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 137-143, 1997. Google Scholar
  25. Michael L Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1):29-35, 1975. Google Scholar
  26. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pages 212-219, 1996. URL: https://doi.org/10.1145/237814.237866.
  27. Phillip Kaye, Raymond Laflamme, Michele Mosca, et al. An introduction to quantum computing. Oxford university press, 2007. Google Scholar
  28. Tomasz Kociumaka, Tatiana Starikovskaya, and Hjalte Wedel Vildhøj. Sublinear space algorithms for the longest common substring problem. In Proceedings of the 22th Annual European Symposium on Algorithms, pages 605-617, 2014. Google Scholar
  29. Michal Kouckỳ and Michael Saks. Constant factor approximations to edit distance on far input pairs in nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 699-712, 2020. Google Scholar
  30. 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. URL: https://doi.org/10.1137/090745854.
  31. Frédéric Magniez, Miklos Santha, and Mario Szegedy. Quantum algorithms for the triangle problem. SIAM Journal on Computing, 37(2):413-424, 2007. Google Scholar
  32. William J Masek and Michael S Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980. Google Scholar
  33. Michael Mitzenmacher and Saeed Seddighin. Dynamic algorithms for LIS and distance to monotonicity. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 671-684, 2020. URL: https://doi.org/10.1145/3357713.3384240.
  34. Timothy Naumovitz, Michael E. Saks, and C. Seshadhri. Accurate and nearly optimal sublinear approximations to Ulam distance. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2012-2031, 2017. Revised version available at https://users.soe.ucsc.edu/~sesh/publication.html. URL: https://doi.org/10.1137/1.9781611974782.131.
  35. Prakash Ramanan. Tight Ω (n lg n) lower bound for finding a longest increasing subsequence. International journal of computer mathematics, 65(3-4):161-164, 1997. Google Scholar
  36. Hariharan Ramesh and V Vinay. String matching in Õ(√n+ √m) quantum time. Journal of Discrete Algorithms, 1(1):103-110, 2003. Google Scholar
  37. Aviad Rubinstein. Quantum DNA sequencing and the ultimate hardness hypothesis. https://theorydish.blog/2019/12/09/quantum-dna-sequencing-the-ultimate-hardness-hypothesis/, 2019.
  38. Michael E. Saks and C. Seshadhri. Estimating the longest increasing sequence in polylogarithmic time. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, pages 458-467, 2010. URL: https://doi.org/10.1109/FOCS.2010.51.
  39. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484-1509, 1997. URL: https://doi.org/10.1137/S0097539795293172.
  40. Mario Szegedy. Quantum speed-up of markov chain based algorithms. In Proceedings of the 45th Annual IEEE symposium on foundations of computer science, pages 32-41, 2004. 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