Quantum jumbled pattern matching

Abstract

Let $S_1,S_2\in {\Sigma }^{\ast }$ 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 {\Sigma }^{\ast }$, 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 $\Omega (N^{2-\epsilon })$ preprocessing time and space for $O(1)$ query time, or $\Omega (N^{1-\delta })$ query time in the online version, with $\epsilon ,\delta >0$. In this paper, we present a quantum algorithm for the online JPM in $O(\sqrt{N})$ time.

six pages, three figures