Text searching problems are fundamental problems in computer science whose applications are found in a variety of fields. The string matching problem is the common framework for the class of text searching problems where the objective is to find all, possibly approximate, occurrences of a given pattern of length m within a larger text of length n. In this paper, we present the quantum path parallelism approach, a general strategy based on quantum computation that can be easily adapted to a variety of nonstandard text searching problems. Our method translates a text searching problem to an automata-based string recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favourable conditions, our proposed method solves the approximate search problem in O(nmlog2(n)) time, offering a quadratic speed-up over classical solutions. In other cases such speed-up is achieved only for short patterns, i.e. assuming m=O(log(n)). As a demonstration of the flexibility of our method, we show how it can be adapted for solving some approximate string matching problems, obtaining a significant quantum advantage.
Faro S., Pavone A., Viola C. (2024). Quantum Path Parallelism: A Circuit-Based Approach to Text Searching. In Theory and Applications of Models of Computation 18th Annual Conference, TAMC 2024, Hong Kong, China, May 13–15, 2024, Proceedings (pp. 247-259). Springer Science and Business Media Deutschland GmbH [10.1007/978-981-97-2340-9_21].
Quantum Path Parallelism: A Circuit-Based Approach to Text Searching
Pavone A.;
2024-01-01
Abstract
Text searching problems are fundamental problems in computer science whose applications are found in a variety of fields. The string matching problem is the common framework for the class of text searching problems where the objective is to find all, possibly approximate, occurrences of a given pattern of length m within a larger text of length n. In this paper, we present the quantum path parallelism approach, a general strategy based on quantum computation that can be easily adapted to a variety of nonstandard text searching problems. Our method translates a text searching problem to an automata-based string recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favourable conditions, our proposed method solves the approximate search problem in O(nmlog2(n)) time, offering a quadratic speed-up over classical solutions. In other cases such speed-up is achieved only for short patterns, i.e. assuming m=O(log(n)). As a demonstration of the flexibility of our method, we show how it can be adapted for solving some approximate string matching problems, obtaining a significant quantum advantage.File | Dimensione | Formato | |
---|---|---|---|
Pubblicazione 2024-TAMC.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
243.13 kB
Formato
Adobe PDF
|
243.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.