arXiv:2503.05596cs.DScs.IR2025-03被引 1

将经典位并行字符串匹配转为量子算法,实现二次加速。

Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism

  • 在位并行模型中嵌入格罗弗搜索,实现量子加速。
  • 对精确匹配和最多k个错误的近似匹配均达成二次提速。
  • 为量子时代高效文本搜索提供可复用的技术框架。

字符串匹配是计算机科学中的基础问题,在文本检索、生物信息学和数据分析中有重要应用。近年来,位并行算法显著提升了其实际效率,催生了多种针对精确与近似匹配的优化方法。然而,这些方法在量子计算中的潜力尚未被充分探索。本文提出一种新路径,将位并行字符串匹配算法转化为量子框架,并通过格罗弗搜索实现二次加速。通过在位并行模型中嵌入量子搜索,我们降低了字符串匹配的时间复杂度,建立了一条将经典算法转化为具有可证明计算优势的量子解法的结构化路径。该方法不仅适用于精确匹配,还可拓展至多种非标准字符串匹配问题,为量子时代的高效文本搜索开辟新途径。为验证该技术的简洁性与适应性,本文将其应用于两个标志性位并行算法:用于精确模式匹配的 Shift-And 和用于最多 k 个错误的近似匹配的 Shift-Add。

原文摘要 · Abstract (English)

String matching is a fundamental problem in computer science, with critical applications in text retrieval, bioinformatics, and data analysis. Among the numerous solutions that have emerged for this problem in recent decades, bit-parallelism has significantly enhanced their practical efficiency, leading to the development of several optimized approaches for both exact and approximate string matching. However, their potential in quantum computing remains largely unexplored. This paper presents a novel pathway that not only translates bit-parallel string matching algorithms into the quantum framework but also enhances their performance to achieve a quadratic speedup through Grover's search. By embedding quantum search within a bit-parallel model, we reduce the time complexity of string matching, establishing a structured pathway for transforming classical algorithms into quantum solutions with provable computational advantages. Beyond exact matching, this technique offers a foundation for tackling a wide range of non-standard string matching problems, opening new avenues for efficient text searching in the quantum era. To demonstrate the simplicity and adaptability of the technique presented in this paper, we apply this translation and adaptation process to two landmark bit-parallel algorithms: Shift-And for exact pattern matching and Shift-Add for approximate string matching with up to k errors.

字符串匹配量子计算位并行格罗弗搜索

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。