量子科技中心_量科网

在“带通配符搜索问题”[Ambainis, Montanaro, Quantum Inf. Comput.”14]中，研究目标是学习一个未知的比特串x ∈ {−1, 1}^n。算法可以以单位成本测试隐藏字符串的任意子集是否与其选择的字符串相等。Ambainis和Montanaro提出了成本为O(√n log n)的量子算法，并给出了近乎匹配的Ω(√n)下界。Belovs [Comput. Comp.”15]随后证明了紧致的O(√n)上界。 该研究团队考虑该问题的一个自然推广，通过子集Q ⊆ 2^[n]参数化，允许算法以单位成本测试任意S ∈ Q和自选的b ∈ {−1, 1}^S是否满足x_S = b。研究发现： - 对于所有k ∈ [n]，当Q是大小不超过k的所有集合时，量子查询复杂度为Θ(n/√k)。特别地，当k=n时，这对应于标准带通配符搜索场景。该结果使用完全不同的技术，恢复并推广了Belovs以及Ambainis和Montanaro的紧致表征。 - 当Q是连续区块集合时，量子查询复杂度为Θ(e^n)。 - 当Q是前缀集合时，量子查询复杂度为Θ(n)。 所有结果均通过团队开发的新框架得出。研究人员对负权重对抗边界原始形式进行对称性约简，证明学习x的量子查询复杂度（至多常数倍）可由特定优化程序表征。该程序可简洁描述为：“对于所有奇函数f: {-1, 1}^n → R，最大化f的最大值与（在Q中T上）f在自由变量恰好为T的子立方体上的标准偏差最大值的比值”。 据该团队所知，这是首次在不显式依赖SDP对偶性的情况下，利用负权重对抗边界的原始形式（通常用于证明下界的最大化程序）来实现新型量子查询上界的工作。