论文标题
量子混乱的模式匹配
Quantum jumbled pattern matching
论文作者
论文摘要
令$ s_1，s_2 \在σ^*$弦乐中，我们说$ s_1 $ {\ em jumble match} $ s_2 $如果它们彼此排列。给定一个尺寸$ n $的文本$ t $和σ^*$中的字符串$ s \，\ emph {jumbled pattern匹配}（jpm）的问题是确定$ t $ jumbled匹配$ s $的所有子字符。在经典计算中，广泛的猜想是，jpm需要$ω（n^{2-ε}）$ $ o（1）$查询时间或$ω（n^{1-Δ}）$查询时间的预处理时间和空间，在线版本中，$ε，δ> 0 $。在本文中，我们为在线jpm介绍$ o（\ sqrt {n}）$时间的量子算法。
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.
