Document Open Access Logo

From Bit-Parallelism to Quantum String Matching for Labelled Graphs

Authors Massimo Equi , Arianne Meijer-van de Griend , Veli Mäkinen

PDF

File

Thumbnail PDF
PDF
LIPIcs.CPM.2023.9.pdf
  • Filesize: 1.04 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Parallel algorithms
  • Theory of computation → Pattern matching
  • Theory of computation → Graph algorithms analysis
Keywords
  • Bit-parallelism
  • quantum computation
  • string matching
  • level DAGs

Metrics

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

Abstract

Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor w, where w is the computer word size. A classic example is computing the edit distance of two strings of length n, which can be solved in O(n²/w) time. In a reasonable classical model of computation, one can assume w = Θ(log n), and obtaining significantly better speed-ups is unlikely in the light of conditional lower bounds obtained for such problems.
In this paper, we study the connection of bit-parallelism to quantum computation, aiming to see if a bit-parallel algorithm could be converted to a quantum algorithm with better than logarithmic speed-up. We focus on string matching in labeled graphs, the problem of finding an exact occurrence of a string as the label of a path in a graph. This problem admits a quadratic conditional lower bound under a very restricted class of graphs (Equi et al. ICALP 2019), stating that no algorithm in the classical model of computation can solve the problem in time O(|P||E|^(1-ε)) or O(|P|^(1-ε)|E|). We show that a simple bit-parallel algorithm on such restricted family of graphs (level DAGs) can indeed be converted into a realistic quantum algorithm that attains subquadratic time complexity O(|E|√|P|).

Cite As Get BibTex

Massimo Equi, Arianne Meijer-van de Griend, and Veli Mäkinen. From Bit-Parallelism to Quantum String Matching for Labelled Graphs. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CPM.2023.9

Author Details

Massimo Equi
  • Department of Computer Science, University of Helsinki, Finland
Arianne Meijer-van de Griend
  • Department of Computer Science, University of Helsinki, Finland
Veli Mäkinen
  • Department of Computer Science, University of Helsinki, Finland

Funding

  • Equi, Massimo: Partially funded by the European Union’s Horizon 2020 research and innovation programme under the European Research Council (ERC) grant agreement No. 851093 (SAFEBIO) and by the Helsinki Institute for Information Technology (HIIT).

References

  1. Mai Alzamel, Lorraine A. K. Ayad, Giulia Bernardini, Roberto Grossi, Costas S. Iliopoulos, Nadia Pisanti, Solon P. Pissis, and Giovanna Rosone. Comparing degenerate strings. Fundam. Informaticae, 175(1-4):41-58, 2020. Google Scholar
  2. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput., 47(3):1087-1097, 2018. URL: https://doi.org/10.1137/15M1053128.
  3. Ricardo A. Baeza-Yates and Gaston H. Gonnet. A new approach to text searching. Commun. ACM, 35(10):74-82, 1992. URL: https://doi.org/10.1145/135239.135243.
  4. Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, and Veli Mäkinen. Linear-time string indexing and analysis in small space. ACM Trans. Algorithms, 16(2), March 2020. URL: https://doi.org/10.1145/3381417.
  5. Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46(4-5):493-505, 1998. Google Scholar
  6. Parisa Darbari, Daniel Gibney, and Sharma V. Thankachan. Quantum time complexity and algorithms for pattern matching on labeled graphs. In String Processing and Information Retrieval - 29th International Symposium, SPIRE 2022, Concepción, Chile, November 8-10, 2022, Proceedings, volume 13617 of Lecture Notes in Computer Science, pages 303-314. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-20643-6_22.
  7. Massimo Equi, Roberto Grossi, Veli Mäkinen, and Alexandru I. Tomescu. On the complexity of string matching for graphs. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 55:1-55:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  8. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical review letters, 100(16):160501, 2008. Google Scholar
  9. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212-219. ACM, 1996. URL: https://doi.org/10.1145/237814.237866.
  10. Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323-350, 1977. URL: https://doi.org/10.1137/0206024.
  11. Gene Myers. A fast bit-vector algorithm for approximate string matching based on dynamic programming. J. ACM, 46(3):395-415, 1999. URL: https://doi.org/10.1145/316542.316550.
  12. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511976667.
  13. Pradeep Niroula and Yunseong Nam. A quantum algorithm for string matching. npj Quantum Information, 7(1):1-5, 2021. Google Scholar
  14. Hariharan Ramesh and V Vinay. String matching in O(√n+√m) quantum time. Journal of Discrete Algorithms, 1(1):103-110, 2003. Combinatorial Algorithms. URL: https://doi.org/10.1016/S1570-8667(03)00010-8.
  15. Mikko Rautiainen, Veli Mäkinen, and Tobias Marschall. Bit-parallel sequence-to-graph alignment. Bioinform., 35(19):3599-3607, 2019. URL: https://doi.org/10.1093/bioinformatics/btz162.
  16. Kapil Kumar Soni and Ashwini Kumar Malviya. Design and analysis of pattern matching algorithms based on quram processing. Arabian Journal for Science and Engineering, 46(4):3829-3851, 2021. Google Scholar
  17. Jorg Van Renterghem. The implications of breaking the strong exponential time hypothesis on a quantum computer. Master’s thesis, Ghent University, 2019. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact