The string matching problem is one of the fundamental problems in computer science with applications in a variety of fields. Basically, it consists in finding all occurrences of a given pattern within a larger text. Despite its straightforward formulation, it has given rise to a huge number of solutions based on very different approaches and varied computational paradigms. But it is only very recently that the first solution based on quantum computation has been proposed by Niroula and Nam, allowing the problem to be solved in O(n(log2(n)+log(m))) time, with a quadratic speed-up compared to classical computation. To date, these two research fields have remained almost entirely separate, mainly because the technical aspects typical of the quantum computation field remain almost obscure to those involved in text processing. This paper aims to reconcile the two fields by unfolding the technical aspects of the Niroula-Nam quantum solution and providing a detailed general procedure working in O(nlog2(n)) time that can be used as a framework for solving other string matching problems, including nonstandard ones. In this direction, the paper also proposes an extension of the algorithm to the approximate string matching problem with swaps, reporting the configuration of the occurrence together with its position, and achieving a quasi-linear O(nlog2(n)) time complexity when m= O(log (n)).
Cantone D., Faro S., Pavone A. (2023). Quantum String Matching Unfolded and Extended. In Reversible Computation 15th International Conference, RC 2023 Giessen, Germany, July 18–19, 2023 Proceedings (pp. 117-133). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-031-38100-3_9].
Quantum String Matching Unfolded and Extended
Pavone A.
2023-01-01
Abstract
The string matching problem is one of the fundamental problems in computer science with applications in a variety of fields. Basically, it consists in finding all occurrences of a given pattern within a larger text. Despite its straightforward formulation, it has given rise to a huge number of solutions based on very different approaches and varied computational paradigms. But it is only very recently that the first solution based on quantum computation has been proposed by Niroula and Nam, allowing the problem to be solved in O(n(log2(n)+log(m))) time, with a quadratic speed-up compared to classical computation. To date, these two research fields have remained almost entirely separate, mainly because the technical aspects typical of the quantum computation field remain almost obscure to those involved in text processing. This paper aims to reconcile the two fields by unfolding the technical aspects of the Niroula-Nam quantum solution and providing a detailed general procedure working in O(nlog2(n)) time that can be used as a framework for solving other string matching problems, including nonstandard ones. In this direction, the paper also proposes an extension of the algorithm to the approximate string matching problem with swaps, reporting the configuration of the occurrence together with its position, and achieving a quasi-linear O(nlog2(n)) time complexity when m= O(log (n)).File | Dimensione | Formato | |
---|---|---|---|
Quantum String Matching Unfolded.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
454.13 kB
Formato
Adobe PDF
|
454.13 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.