技术摘要：具有广义通配符的量子搜索

问题定义

本文研究了带有通配符的量子搜索问题，这是对 Ambainis 和 Montanaro [AM14] 引入的学习问题的推广。其目标是学习一个未知的比特串 $x \in \{-1, 1\}^n$。在标准模型中，算法可以查询任何索引子集 $S \subseteq [n]$，以单位代价检查子串 $x_S$ 是否等于选定的字符串 $b \in \{-1, 1\}^S$。

这项工作通过将允许的查询子集限制为任意固定的集合 $\mathcal{Q} \subseteq 2^{[n]}$，对该问题进行了推广。只有当 $S \in \mathcal{Q}$ 时，算法才能测试 $x_S = b$。本文研究了在不同 $\mathcal{Q}$ 约束下学习 $x$ 的量子查询复杂度（记作 $Q_{\mathcal{Q}}(\text{rec})$），包括：

• 有界大小集合： 满足 $|S| \le k$ 的 $S$。
• 连续块： $S = [i, j]$。
• 前缀： $S = [1, i]$。
• 仅全集： $S = [n]$。

在经典情况下，即使带有通配符，学习 $x$ 仍需要 $\Omega(n)$ 次查询，因为每次查询最多只能提供 1 比特的信息。在不受限的量子设置下（$\mathcal{Q} = 2^{[n]}$），Ambainis 和 Montanaro 实现了 $O(\sqrt{n} \log n)$，随后被 Belovs [Bel15] 紧缩为 $O(\sqrt{n})$。本文旨在刻画在受限 $\mathcal{Q}$ 下的复杂度。

方法论

作者开发了一个基于负权重对手界限（negative-weight adversary bound）的统一框架，特别利用了其原问题形式（primal formulation）（一个极大化半正定规划，SDP）。

1. 归约至奇偶校验

作者首先证明，对于向下封闭（downward-closed）的查询集 $\mathcal{Q}$，学习整个字符串的复杂度等价于计算奇偶校验函数 $\oplus(x) = \prod x_i$（在常数因子范围内）。这使得问题可以归约为分析 $Q_{\mathcal{Q}}(\oplus)$。

2. 对称性归约

利用布尔函数的原问题对手界限形式，作者应用了对称性归约。他们证明了对于奇偶校验函数，最优对手矩阵 $\Gamma$ 可以假设为 XOR 函数的通信矩阵。即，$\Gamma[x, y] = f(x \oplus y)$，其中 $f: \{-1, 1\}^n \to \mathbb{R}$ 是某个函数。这把对矩阵的优化简化为了对函数的优化。

3. 傅里叶分析

通过利用 XOR 通信矩阵在傅里叶基下是对角化的特性，作者将对手界限的谱范数约束转化为函数 $f$ 的解析性质。

• 分子（$\Gamma$ 的谱范数）对应于 $f$ 的最大绝对值（经缩放后）。
• 分母（由查询限制后的 $\Gamma$ 的谱范数）对应于 $f$ 在由查询集定义的子立方体上的标准差。

这导致将查询复杂度刻画为一个抽象优化程序 $val_{\mathcal{Q}}$ 的解。

核心贡献与结果

1. 通用刻画 (定理 1.1)

论文证明了使用查询集 $\mathcal{Q}$ 计算奇偶校验的量子查询复杂度由下式刻画：
$$Q_{\mathcal{Q}}(\oplus) = \Theta(val_{\mathcal{Q}})$$
其中
$$val_{\mathcal{Q}} := \max_{f \text{ 是奇函数}} \frac{\|f\|_\infty}{\max_{S \in \mathcal{Q}, b} \sqrt{\text{Var}(f_{S|b})}}$$
这里，$f$ 是奇函数（满足 $f(x) = -f(-x)$），且 $f_{S|b}$ 是 $f$ 在变量 $\bar{S}$ 固定为 $b$ 的子立方体上的限制。复杂度由函数的最大值与其在任何有效查询子立方体上的最大标准差的比值决定。

2. 特定界限 (定理 1.2 与 推论 1.3)

该框架被用于推导特定查询集的紧确界限：

• 有界大小集合 ($|S| \le k$)：
  复杂度为 $\Theta(n/\sqrt{k})$。
  • 意义： 当 $k=n$ 时，这恢复了标准带通配符搜索的最优 $O(\sqrt{n})$ 界限，与 Belovs 的结果一致，但采用了不同的技术。
• 连续块：
  复杂度为 $\tilde{\Theta}(n)$。
  • 意义： 这意味着在如基因组测序等仅能访问连续片段的场景中，量子算法相对于经典算法没有加速。它恢复了已知的 $\Omega(n/\log n)$ [CILG+12, BV23] 下界，并建立了匹配的上界。
• 前缀：
  复杂度为 $\Theta(n)$。
  • 意义： 这通过证明无法通过亚线性前缀查询恢复字符串，解决了一个开放问题 [XZL23]。
• 仅全集 ($S=[n]$)：
  复杂度为 $\Theta(2^{n/2})$。
  • 意义： 这恢复了在规模为 $N=2^n$ 的数据库中进行搜索的标准 Grover 搜索下界 $\Omega(\sqrt{N})$。

重要性与主张

本文声称了几项重要的贡献：

1. 首次使用原问题对手界限进行上界证明： 作者指出，据其所知，这是第一项使用原问题版本的负权重对手界限（通常作为下界工具）来证明新的量子查询上界，且无需显式求助于 SDP 对偶性的工作。
2. 统一框架： 该工作提供了一个单一的解析框架，既能恢复已知的紧确界限（如 Belovs 的 $O(\sqrt{n})$），又能推导出广义设置下的新界限，取代了复杂的算法构建或对偶 SDP 解，转而使用布尔超立方体上实值函数的组合分析。
3. 生物学相关性： 研究结果受到计算生物学（如 DNA/RNA 测序）的启发并适用于该领域，因为在这些领域中，测量往往被限制在连续的子字符串上。论文得出结论，在这些特定的受限模型中，量子算法不会提供超多项式的优势。

作者指出，虽然其框架给出了紧确界限，但与 Ambainis 和 Montanaro 或 Belovs 的构造性方法不同，它并未显式构造量子算法。然而，他们认为，当结合对称性和结构性洞察时，原问题形式是建立紧确复杂度界限的实用工具。