带有通配符的量子模式匹配-计算机科学-机器学习-模式匹配-量子算法.pdfVIP

带有通配符的量子模式匹配

MasoudSeddighinSaeedSeddighin

摘要

模式匹配是计算机科学中的一个基本问题。经典版本的问题以及输入中可以出现通配符的更

复杂版本都可以分别使用KMP算法和快速傅里叶变换在接近线性时间内解决。2000年，

Ramesh和Vinay[17]给出了一种可以在亚线性时间内解决经典模式匹配问题的量子算法，并

询问是否通配符问题也可以在亚线性时间内解决？在这项工作中，我们给出了一种在通配符数

本量由中的限制时运行时间为的带通配符的模式匹配量子算法。这导致了一

译个只要通配符的数量是亚线性的就能够在亚线性时间内运行的算法。

中

11介绍

v

5

8字符串问题在计算机科学中，无论是经典设置还是量子设置下都得到了广泛的研究[17,16,5,

8

312,2,18,15,14,7,13,4,3,19,1,8,9]。模式匹配可能是最基础的字符串问题，在文本处理、生物

1.信息学和数据分析等领域有着广泛应用。在量子计算领域，它也成为了评估量子算法相对于经典方

7

0法潜在加速效果的关键问题。尽管现有的量子算法为经典的模式匹配提供了有意义的改进，但在允

5许通配符出现在模式和文本中的情况下，尚未知道存在任何量子算法的加速。

2

:经典版本的问题以及输入中也可以出现通配符的更复杂版本都可以分别使用KMP算

v

i

x法[10]和快速傅里叶变换[7]在近似线性时间内解决。在2000年，Ramesh和Vinay[17]提出

r

a了一种量子算法来在线性时间内解决经典模式匹配问题，并询问通配符问题是否也可以在亚线性时

间解决？在这项工作中，我们提出了一种用于具有通配符的模式匹配的量子算法，在通配符数量由

1

限制为的情况下，该算法运行时间为。这产生了一个在时间max

内运行的算法。

2预备知识

我们将两个字符串表示为（代表文本）和（代表模式）。我们将的大小记为，将的

大小记为，并且不失一般性地假设。每个字符串是一系列从0开始索引的字符和通配符。

我们用表示和中通配符的总数。另外，我们将一个通配符字符表示为‘‘（不包括引号）。

1很容易证明，可以在不改变问题本质的情况下增加通配符的数量。例如，可以用两个字符$x替换两个字符串中的每

个字符x，其中$是一个在原始字符串中不存在的特殊字符。现在，可以任意将模式中的每个$字符转换为通配符，只要至

少有一个$字符保持不变，则不会改变问题的复杂度。

我们说两个字符匹配，如果它们相等或其中之一是通配符，否则我们称它们不匹配。我们说一

个字符串与另一个字符串匹配，如果它们的大小相同并且它们的字符逐个索引匹配。此外，我们将

两个大小相同的字符串和之间的不匹配数定义为这样的的数量，使得不匹配。

最后，对于字符串，我们用表示从索引开始到索引结束的的子串。