Advertisement
Published in:
06-08-2021
Classical and quantum algorithms for constructing text from dictionary problem
Published in: Natural Computing | Issue 4/2021
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We study algorithms for solving a problem of constructing a text (a long string) from a dictionary (a sequence of small strings). The problem has an application in bioinformatics and has a connection with the sequence assembly method for reconstructing a long DNA sequence from small fragments. Our problem is the construction a string t of length n using strings \(s^1,\dots , s^m\) with possible overlapping. Firstly, we provide a classical (randomized) algorithm with running time \(O\left( n+L +m(\log n)^2\right) =\tilde{O}(n+L)\) where L is the sum of lengths of \(s^1,\dots ,s^m\). Secondly, we provide a quantum algorithm with running time \(O\left( n +\log n\cdot (\log m+\log \log n)\cdot \sqrt{m\cdot L}\right) =\tilde{O}\left( n +\sqrt{m\cdot L}\right) \). Additionally, we show that the lower bound for a classical (randomized or deterministic) algorithm is \(\varOmega (n+L)\). Thus, our classical algorithm is optimal up to a log factor, and our quantum algorithm shows a speed-up when compared with any classical (randomized or deterministic) algorithm in the case of non-constant length of strings in the dictionary.