LIPIcs.CPM.2023.9.pdf
- Filesize: 1.04 MB
- 20 pages
Document
From Bit-Parallelism to Quantum String Matching for Labelled Graphs
Authors
Massimo Equi 
,
Arianne Meijer-van de Griend ,
Veli Mäkinen
-
Part of:
Volume:
34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-06-21
File
Document Identifiers
Author Details
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
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|).
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)
0PDF Downloads
References
-
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.
- 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.
- 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.
- 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.
-
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.
- 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.
-
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.
-
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical review letters, 100(16):160501, 2008.
- 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.
- 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.
- 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.
- 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.
-
Pradeep Niroula and Yunseong Nam. A quantum algorithm for string matching. npj Quantum Information, 7(1):1-5, 2021.
- 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.
- 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.
-
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.
-
Jorg Van Renterghem. The implications of breaking the strong exponential time hypothesis on a quantum computer. Master’s thesis, Ghent University, 2019.