Quantum jumbled pattern matching

Let S1, S2 ∈ Sigma^* strings, we say that S1 em jumble match S2 if they are permutations of each other. Given a text T of size N and a string S ∈ Sigma^*, the problem of 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(N2-ε) preprocessing time and space for O(1) query time, or Omega(N1-δ) query time in the online version, with ε, δ >0. In this paper, we present a quantum algorithm for the online JPM in O(√N) time.