量子查询算法中的多项式与对称化下界

# 量子查询算法中的多项式与对称化下界 ## 1. 多项式与元素独特性问题 ### 1.1 多项式与接受概率 在量子算法中，多项式可用于精确计算算法的接受概率。例如，某些多项式能输出样本中是否存在冲突的信息，像 $p_g$ 若样本包含冲突则输出 1，否则输出 0；而 $q_g(x)$ 输出样本不包含冲突，但 Grover 搜索找到“交叉冲突”（即样本外与样本内元素冲突的项）的概率。 ### 1.2 元素独特性函数 元素独特性函数 $k$-ED 将输入视为大小为 $R$ 的范围内的 $N$ 个数字列表 $(k_1, \cdots, k_N)$，当且仅当列表中存在某个范围项至少出现 $k$ 次时输出 -1。当 $k = 2$ 时，即为元素独特性问题（ED）。对于 $R > N$ 的情况，ED 的近似度有一个 $\Omega(N^{2/3})$ 的下界，下面我们将探讨其匹配的上界。 ### 1.3 简单量子算法 为了说明，我们先给出一个对 ED 取反的简单量子算法，该算法进行 $O(N^{5/6})$ 次查询，这意味着存在一个度数为 $O(N^{5/6})$ 的近似多项式来近似 ED。此算法利用了一个具有特定性质的子程序： - **子程序 1**： 1. 随机采样 $b = N^{1/3}$ 个输入，即随机选取大小为 $b$ 的集合 $S \subseteq [N]$ 并查询 $\{k_i: i \in S\}$。 2. 令 $\{r_1, \cdots, r_b\}$ 表示采样范围项的多重集。若存在不同的 $i, j \in [b]$ 使得 $r_i = r_j$，则停止并接受。 3. 否则，对未采样的项 $\{k_i: i \notin S\}$ 进行 Grover 搜索，若找到 $r_1, \cdots, r_b$ 中的任何一个出现，则接受，否则拒绝。此过程的查询成本为 $O(b + \sqrt{N})$。 若列表中存在参与冲突的项，子程序 1 至少以 $b/N > \Omega(1/N^{2/3})$ 的概率采样到这样的项，并且在此事件发生的条件下，子程序接受的概率至少为 $2/3$。若列表中不存在参与冲突的项，子程序接受的概率为 0。根据相关定理，子程序 1 可转化为一个度数至多为 $O(b + \sqrt{N})$ 的多项式 $p$，使得对于所有 $x \in (ED)^{-1}(-1)$ 有 $p(x) = 0$，对于所有 $x \in (ED)^{-1}(1)$ 有 $p(x) > b/N$。 ### 1.4 振幅放大技术 使用量子算法设计中的振幅放大技术，可将成功概率从 $\Omega(b/N)$ 提升到 $2/3$，同时度数增加一个 $O(\sqrt{N/b}) = O(N^{1/3})$ 的因子，从而得到查询上界为 $O(N^{1/2} \cdot N^{1/3}) = O(N^{5/6})$。以下定理给出了在近似度背景下振幅放大的类似结果： **定理 4.5**：设 $f: \{-1, 1\}^n \to \{-1, 1\}$。假设存在一个度数至多为 $d$ 的多项式 $p$，使得对于所有 $x \in f^{-1}(-1)$ 有 $p(x) = 0$，对于所有 $x \in f^{-1}(1)$ 有 $\delta < p(x) < 1$。那么 $f$ 的 $(1/3)$ - 近似度至多为 $O(d \cdot \sqrt{1/\delta})$。 **证明**：使用切比雪夫多项式，可构造一个度数为 $O(\sqrt{1/\delta})$ 的单变量多项式 $A$，使得 $A(0) = 1$ 且对于所有 $x \in [-1 + \delta, 1]$ 有 $A(t) \in [-4/3, -2/3]$。则 $-A(p(x))$ 以 $1/3$ 的误差近似 $f$，且度数为 $d \cdot \text{deg}(A) < O(d \cdot \sqrt{1/\delta})$。 综上所述，我们得到一个近似 ED 的多项式形式为 $-A \circ p$，其中 $A$ 是定理 4.5 证明中度数为 $O(N^{1/3})$ 的多项式，$p(x)$ 是子程序 1 在输入 $x$ 上的接受概率。 ### 1.5 改进尝试 为了改进 $O(N^{5/6})$ 的近似度上界，我们可以将子程序 1 中的 Grover 搜索替换为精确搜索（精确搜索的查询成本为 $\Omega(N)$，但失败概率为 0）。设 $q$ 表示此算法的接受概率，那么 $-A \circ q$ 也是 ED 的 $(1/3)$ - 近似，但度数比 $-A \circ p$ 大得多。 然而，由于 $A \circ q$ 的复合结构，它本身可以被一个度数仅为 $O(N^{2/3})$ 的多项式逐点近似。为了近似 $A \circ q$，我们将其表示为 $2^{O(\text{deg}(A))}$ 项的加权和，每一项为 $(1 - q)$ 的幂，即形式为 $C_j \cdot (1 - q(x))^i$，其中 $C_j \in \mathbb{R}$ 且 $i < \text{deg}(A)$。然后将每一项近似到指数级小的误差，确保各项近似的和是 $A \circ q$ 的良好近似。 例如，若 $A(t) = 2t^3 - 4t^2 + 3t - 1$，则 \[ \begin{align*} (A \circ q)(x) &= 2q(x)^3 - 4q(x)^2 + 3q(x) - 1\\ &= -2(1 - q(x))^3 + 2(1 - q(x))^2 - (1 - q(x)) \end{align*} \] 若将表达式中的三项 $-2(1 - q(x))^3$、$2(1 - q(x))^2$ 和 $-(1 - q(x))$ 分别近似到误差 $1/12$ 并求和，我们得到一个多项式 $Q$，使得对于 ED 定义域内的所有 $x$ 有 $|Q(x) - (A \circ q)(x)| < 3 \cdot 1/12 = 1/4$。 ### 1.6 近似度分析 由于多项式 $A$ 由切比雪夫多项式导出，其系数的 $l_1$ - 范数为 $2^{O(\text{deg}(A))}$。因此，只需将 $(1 - q(x))^i$ 的每一次幂近似到误差 $\epsilon = 2^{-\Omega(\text{deg}(A))}$。将这些近似求和得到一个多项式 $Q$，使得对于 ED 的所有输入 $x$ 有 $|Q(x) - (A \circ q)(x)| < \epsilon \cdot 2^{O(\text{deg}(A))} < o(1)$。 为了将 $(1 - q(x))^i$ 近似到误差 $\epsilon$，我们发现可以通过一次搜索来替代 $\text{deg}(A)$ 次独立搜索。使用 $\epsilon$ - 误差 Grover 搜索执行此单次搜索过程，该算法的接受概率可以近似到误差 $\epsilon = 2^{-\Omega(\text{deg}(A))}$，且度数为 $O(b \cdot \text{