超越块组合函数：理论与应用探索

# 超越块组合函数：深入探究函数近似度与应用 ## 1 引言 在函数分析领域，块组合函数的研究一直是一个重要的方向。然而，非块组合函数与块组合函数之间的联系以及它们的近似度问题，同样值得我们深入探讨。本文将围绕这些问题展开，通过具体的函数示例，如 Surjectivity 函数，详细分析其近似度的上下界、阈值度等性质，并探讨这些结果在量子查询复杂度和 AC0 电路近似度等方面的应用。 ## 2 Surjectivity 函数分析 ### 2.1 Surjectivity 函数定义 Surjectivity 函数（SURJ）以向量 \(x \in \{ -1, 1 \}^n\) 为输入，其中 \(n = N \log_2 R\)。该函数将向量解释为 \(N\) 个来自范围 \([R] = \{ 1, \ldots, R \}\) 的数字（\(k_1, \ldots, k_N\)）的列表。当且仅当对于每个 \(i \in [R]\)，至少存在一个索引 \(j\) 使得 \(k_j = i\) 时，函数输出为 \(-1\)。 ### 2.2 近似度上界 我们将 SURJ 与块组合函数 \(AND_R \circ OR_N\) 建立联系。通过引入一组 \(N \cdot R\) 个变量 \(y(x) = \{ y_{ij} : i \in [R], j \in [N] \}\) 来表示列表 \((k_1, \ldots, k_N)\)，其中 \(y_{ij} = -1\) 当且仅当 \(k_j = i\)，否则 \(y_{ij} = 1\)。可以发现，每个变量 \(y_{ij}\) 仅依赖于 \(x\) 的 \(\log_2 R\) 位，并且有 \(SURJ(x) = (AND_R \circ OR_N)(y(x))\)。 对于任何输入 \(x\) 到 SURJ，对应的向量 \(y(x)\) 的汉明重量恰好为 \(N\)。这意味着，如果多项式 \(p\) 以误差 \(\epsilon\) 近似 \((AND_R \circ OR_N)^{\leq N}\)，那么 \(p(y(x))\) 以误差 \(\epsilon\) 近似 SURJ，且其度数至多为 \(\deg(p) \cdot \log_2 R\)。由此可得观察结果：\(\text{deg}_\epsilon(SURJ) < \text{deg}_\epsilon((AND_R \circ OR_N)^{\leq N}) \cdot \log_2 R\)。 已知 \(\text{deg}(AND_R \circ OR_N) = O(\sqrt{R N})\)，并且当近似仅需在汉明重量至多为 \(N\) 的输入上准确时，\(AND_R \circ OR_N\) 更容易近似。以下是相关定理： - **定理 8.2**：\(\text{deg}((AND_R \circ OR_N)^{\leq N}) < O(R^{1/4} \cdot N^{1/2})\)。 - **证明**：设 \(q\) 是定义在域 \(\{ -1, 1 \}^R\) 上的度数为 \(O(\sqrt{R})\) 的多项式，它以误差 \(1/4\) 近似 \(AND_R\)。通过基变换，可将 \(q\) 表示为析取式的线性组合，即 \(q = \sum_{S \subseteq [R]} c_S \cdot OR_S\)，其中 \(OR_S(y) = \bigvee_{i \in S} y_i\)。由于任意两个析取式的组合仍是析取式，所以 \(q \circ OR_N\) 是定义在域 \(\{ -1, 1 \}^{RN}\) 上的析取式的线性组合。 我们利用仅需在汉明重量至多为 \(N\) 的输入上准确近似 \(AND_R \circ OR_N\) 这一事实。对于任意 \(\epsilon > 0\)，有 \(\text{deg}_\epsilon(OR_{S}) < O(\sqrt{N} \log(1/\epsilon))\)。令 \(\epsilon = 1/(12N)\)，将 \(q \circ OR_N\) 中的每个析取式 \(OR_{S}\) 替换为其 \(\epsilon\) - 近似多项式。得到的多项式 \(p\) 的度数为 \(O(\sqrt{N} \log N) = O(R^{1/4} N^{1/2})\)。在任何汉明重量至多为 \(N\) 的输入 \(y\) 上，有 \(| (q \circ OR_N)(y) - p(y) | < 1/12\)，因此 \(| (AND_R \circ OR_N)(y) - p(y) | < 1/12 + 1/4 = 1/3\)。 ### 2.3 近似度下界 尽管上面构造的 SURJ 近似多项式仅考虑了 \(y(x)\) 的汉明重量至多为 \(N\) 这一事实，但实际上，向量 \(y(x)\) 的额外结构（例如，对于每个 \(j \in [N]\)，恰好有一个索引 \(i \in [R]\) 使得 \(y_{ij} = -1\)）无法被低度数多项式利用。这意味着 SURJ 的近似度不仅上界由 \((AND_R \circ OR_N)^{\leq N}\) 的近似度决定，实际上两者是等价的。 - **引理 8.3**：\(\text{deg}_\epsilon(SURJ) > \Omega (\text{deg}_\epsilon((AND_R \circ OR_N)^{\leq N}))\)。 - **定理 8.4**：\(\text{deg}((AND_R \circ OR_N)^{\leq N}) > \Omega(R^{1/4} \cdot N^{1/2})\)。 - **证明概要**：设 \(\psi\) 是任意一个证明 \(\text{deg}_{7/8}(AND_R) > \Omega(\sqrt{R})\) 的对偶多项式，令 \(N' := N/R^{1/2}\)。考虑函数 \((AND_R \circ OR_{N'})^{\leq N}\) 而非 \((AND_R \circ OR_N)^{\leq N}\)，因为前者是后者的子函数，对前者的下界将意味着对后者的所需下界。 设 \(\phi\) 是在第 6.1 节中构造的用于证明 \(\text{deg}_{7/8}(OR_{N'}) > \Omega(\sqrt{N'})\) 的对偶多项式。根据引理 7.2 - 7.4，\(\psi * \phi\) 是证明 \(\text{deg}(AND_R \circ OR_{N'}) > \Omega(\sqrt{R} \cdot N') > \Omega(R^{1/4} \cdot N^{1/2})\) 的对偶多项式。 关键性质是 \(|\psi * \phi|\) 在汉明重量大于 \(N\) 的输入上的质量非常小，即 \(\sum_{y \in \{ -1, 1 \}^{R N'} : |y| > N} |(\psi * \phi)(y)| < 2^{-\Omega(R^{1/4} N^{1/2})}\)。假设多项式 \(p\) 在所有汉明重量至多为 \(N\) 的输入上近似 \(AND_R \circ OR_{N'}\)，则对于所有 \(|y| < d < N\)，有 \(|p(y)| < 4/3\)。根据 Razborov 和 Sherstov 的插值论证，这意味着对于所有输入，甚至是汉明重量非常大的输入，\(p\) 的幅度都被 \(e^{O(d)}\) 所限制。结合对偶多项式的性质，可得 \(p\) 至少需要度数 \(d = R^{1/4} \cdot N^{1/2} / \log N\)。 ### 2.4 阈值度 由于观察结果 8.1 和定理 8.3 对每个 \(\epsilon > 0\) 都成立，因此，在对数因子范围内，\(\text{deg}_\pm(SURJ)\) 等价于 \(\text{deg}_\pm(AND_R \circ OR_N)^{\leq N}\)。而 \(\text{deg}_\pm(AND_R \circ O