量子科技中心_量科网

在k-不匹配问题中，给定模式串和长度分别为n和m的文本，我们需要找到文本中是否存在与模式串汉明距离不超过k的子串。该问题自1982年（Landau和Vishkin，1986）起就在经典计算环境中被研究，最近Jin和Nogler（Jin和Nogler，2022）以及Kociumaka、Nogler和Wellnitz（Kociumaka等人，2024）在量子计算环境中进行了研究。该研究团队提出了一种简单的量子算法，以近似方式解决该问题，给定参数ϵ∈(0,1]。该算法仅当出现(1+ϵ)k-不匹配时才会返回匹配位置。如果未返回任何出现位置，则不存在k-不匹配。该算法具有Õ(ϵ⁻¹√(m√(nk)))的时间（规模）复杂度。