在计算机科学中，简并字符串是字符集合的序列，而广义简并（GD）字符串则扩展了这一概念，成为字符串集合的序列，其中同一集合中的字符串长度相等。通过 Ascone 等人在 WABI 2024 的研究，找到 GD 字符串中模式字符串的精确匹配的时间复杂度为 $O(mn+N)$，其中 $m$ 是模式长度，$n$ 是字符串数量，$N$ 是构成 GD 字符串的字符串总长度。这是目前为止最佳的经典算法，尚未显示任何匹配的下限，无论是无条件还是有条件。
我们在此基础上提出了一种量子算法，其运行时间为 $\tilde{O}(\sqrt{mnN})$，超越了当前最佳的经典解决方案。据我们所知，这是在 GD 字符串背景下提出的第一种量子算法。我们从经典并行计算的框架出发，提出我们的结果，这使得它们易于理解，并可能容易推广到其他类似结构。
博主点评： 本文提出的量子算法在广义简并字符串的模式匹配中展现了较经典算法的显著提升，标志着量子计算在字符串处理领域的潜力，值得关注其在实际应用中的表现和可扩展性。