Quantum jumbled pattern matching

Let $S_1, S_2 \in Σ^*$ strings, we say that $S_1$ {\em jumble match} $S_2$ if they are permutations of each other. Given a text $T$ of size $N$ and a string $S \in Σ^*$, the problem of \emph{Jumbled Pattern Matching} (JPM) is to determine all substrings in $T$ jumbled matching $S$. In classical computing, a widespread conjecture is that JPM requires $Ω(N^{2-ε})$ preprocessing time and space for $O(1)$ query time, or $Ω(N^{1-δ})$ query time in the online version, with $ε, δ>0$. In this paper, we present a quantum algorithm for the online JPM in $O(\sqrt{N})$ time.

No reviews yet.

No comments yet.