.png){kind=icon}
返回
Quantum Divide and Conquer
.png){kind=icon}
PRE
AI
DOI：10.1145/3723884.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
分治框架在经典算法设计中得到了广泛应用，它递归地将规模为n的问题分解为更小的子问题（例如，每个大小为n/b的a个副本），并伴随一些辅助工作成本Caux(n)，从而给出经典复杂度C(n)的递推关系C(n) ≤ aC(n/b) + Caux(n)。我们描述了一种量子分治框架，在某些情况下，它产生一个类似的递推关系CQ(n) ≤ √aCQ(n/b) + O(CauxQ(n))，用以刻画量子查询复杂度。我们将此框架应用于获得各种字符串问题的近优量子查询复杂度，例如：(i) 识别字母表Σ = {0, 1, 2}上的正则语言Σ*20*2Σ*；(ii) String Rotation和String Suffix的判定版本；以及自然参数化版本下的(iii) Longest Increasing Subsequence和(iv) Longest Common Subsequence。
Keyword:
Quantum computing
quantum query complexity
divide and conquer
string algorithms
regular languages
期刊
A
IF:
6.8
论文数:
542
被引数:
508
机构
引用论文
.png){kind=icon}
查看更多内容