Classical and quantum algorithms for constructing text from dictionary problem

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.

Appendices

Appendix A: Implementation of segment tree’s operations

Assume that the following elements associated with each vertex v of the segment tree:

• g(v) is the target value for a segment tree. If it is not assigned, then $g(v)=-\infty$

• h(v) is an additional value.

• l(v) is the left border of the segment that is associated with the vertex v.

• r(v) is the right border of the segment that is associated with the vertex v.

• LeftC(v) is the left child of the vertex.

• RightC(v) is the right child of the vertex

If a vertex v is a leaf, then $LeftC(v)=RightC(v)=NULL$.

Let st is associated with the root of the tree.

Let us present the algorithm for Update operation. It is recursive procedure.

Let us present the algorithm for Push operation. It is recursive procedure.

Appendix B: Quantum algorithm for comparing two strings with different length

Let us present a quantum algorithm for Comparing two strings with possibly different length. There is a quantum algorithm for comparing two strings of the same length l:

Lemma 4

(Khadiev and Ilikaev 2019) There is a quantum algorithm that compares two strings of length l in the lexicographical order in $O(\sqrt{l}\log \gamma )$ running time and $O\left( \frac{1}{ \gamma ^3}\right)$ error probability for a positive integer $\gamma$.

This algorithm is based on modification of Grover’s search algorithm (Grover 1996; Boyer et al. 1998) that finds the minimal argument satisfying the required property (Kothari 2014; Lin and Lin 2016; Kapralov et al. 2020). Similar idea was used, for example in Ambainis et al. (2020).

Let QC$\textsc {ompare\_strings\_base}(u,v,l)$ be a quantum subroutine for comparing two strings u and v of length l in the lexicographical order. We choose $\gamma = m\log n$. In fact, the procedure compares prefixes of u and v of the length l. QC$\textsc {ompare\_strings\_base}(u,v,l)$ returns 1 if $u>v$; it returns $-1$ if $u<v$; and it returns 0 if $u=v$.

Next, we use a QC$\textsc {ompare}(u,v)$ that compares u and v strings in the lexicographical order. Assume that $\vert u\vert <\vert v\vert$. Then, if u is a prefix of v, then $u<v$. If u is not a prefix of v, then the result is the same as for QC$\textsc {ompare\_strings\_base}(u,v,\vert u\vert )$. In the case of $\vert u\vert >\vert v\vert$, the algorithm is similar. The idea is presented in Algorithm 8.