本文档为一份发表于2006年第四十七届IEEE计算机科学基础研讨会（FOCS’06）的学术论文，作者是来自清华大学高等研究中心的孙晓明与姚期智（Andrew C. Yao）。论文标题为《关于二维和三维网格图中局部搜索的量子查询复杂度》。
本研究属于理论计算机科学领域，具体关注于量子查询复杂度（Quantum query complexity）这一研究方向。查询复杂度是计算复杂性理论中的一个核心概念，它衡量的是解决一个计算问题所需访问输入数据（即“查询”）的最少次数。在经典计算中，这对应于决策树模型；而在量子计算中，则发展为量子查询模型，其中算法可以以量子叠加态的形式同时查询多个输入位。理解不同问题的量子查询复杂度对于揭示量子计算相对于经典计算的优势与局限至关重要。
本研究聚焦于一个经典且重要的计算问题：局部搜索（Local search）。在给定的图G=(V, E)上，每个顶点v都被赋予一个整数值f(v)。局部搜索的目标是找到一个局部最小值顶点v，即满足对于所有邻居w，有f(v) ≤ f(w)。问题的复杂性在于函数f是未知的，算法只能通过查询“f(u)=?”来获取顶点u的值。我们分别用DLS(G)、RLS(G)、QLS(G)来表示确定性、随机化（允许双边错误ε）和量子（允许双边错误ε）算法解决该问题所需的最差情况查询复杂度。
对于特定的图结构——d维网格图[n]^d（即边长为n的d维网格），局部搜索的查询复杂度研究取得了丰富但未完成的成果。在本文工作之前，已知的渐近结果（忽略对数因子）可总结如下： * 随机化复杂度：对于d>2，RLS([n]^d) = Θ(n^{d/2})是紧的。 * 量子复杂度：对于d>4，QLS([n]^d) = Θ(n^{d/3})是紧的。 * 低维情况存在显著空白： * 二维网格：ω(n^{2⁄5}) ≤ QLS([n]^2) ≤ O(√n log log n)，上下界差距巨大。 * 三维网格：ω(n^{3⁄4}) ≤ QLS([n]^3) ≤ O(n)，上下界差距巨大。 * 四维网格：ω(n^{6⁄5}) ≤ QLS([n]^4) ≤ O(n^{4⁄3})，也存在差距。
低维情况之所以困难，是因为在构建证明所需的下界时（特别是基于Aaronson提出的随机行走方法），低维空间缺乏足够的“自由度”，导致碰撞概率较高，难以获得紧的下界。
因此，本研究的核心目标是显著缩小二维和三维网格图上局部搜索量子查询复杂度的已知上下界之间的差距，特别是提供接近已知上界的、更强的下界结果。
本文的核心方法论是将局部搜索问题归约到一个等价的金字塔图路径查找问题，并针对后者利用量子对手方法（Quantum adversary method）结合精心构造的非均匀步长随机游走来证明下界。整个工作流程可以概括为以下几个关键步骤：
步骤一：问题归约（Proposition 1） 首先，作者构建了一个从金字塔图（Pyramid graph）P{d,n}上的路径查找问题到d维网格[n]^d上局部搜索问题的归约。金字塔图P{d,n}的顶点集由所有坐标和为0到n的非负整数d维点构成，边从每个点指向增加一个单位坐标的点。路径查找问题是：给定一条从源点(0,…,0)出发、止于底层（坐标和为n的平面）的未知路径p，目标是通过查询“点x是否在路径p上？”来确定路径的终点。作者证明，任何解决网格局部搜索的算法都可以用来解决对应的金字塔路径问题，且查询次数不变。因此，要证明QLS([n]^d)的下界，只需证明Q(P_{d,n})的下界。
步骤二：构建下界证明框架（Propositions 2 和 4） 这是本文的技术核心。作者设计了一种基于特定序列的随机游走，并利用它来定义量子对手方法中的权重函数。 1. 对于二维情况（Proposition 2）：给定一个正整数序列a = (a_1, …, a_n)，构造一个在二维格子上的n步随机游走：从原点开始，第k步以1/2概率向右移动a_k距离，或以1/2概率向上移动ak距离。所有这样的游走路径自然对应了金字塔图P{2,n}中的一条路径。基于此随机游走，作者为对手方法定义了一组对称的权重函数w(p, p’)和w’(p, p’, x)，其中p和p’是两条不同的路径，x是一个顶点。权重的设计使得当两条路径早期分叉时，它们的权重较小；晚期分叉时，权重较大。 2. 关键参数ρ：为了分析权重的性质，作者引入了一个关键参数µ_{i,j}，它表示从序列a的第i到第j个元素构成的带符号和（随机取±1）等于某个特定值y的最大概率。然后定义ρj = Σ{i=1}^{j} µ_{i,j}，以及ρ = max_j ρj。这个ρ量化了随机游走中不同路径“碰撞”（即到达同一点）的可能性。ρ越小，意味着随机游走的“扩散性”越好，路径之间越容易区分。 3. 下界结论：通过复杂的组合概率分析（利用Lemma 8等），作者最终证明，对于由序列a导出的随机游走模型，对应的路径查找问题的复杂度满足：R(P{2, N}) = Ω(N/ρ) 且 Q(P_{2, N}) = Ω(√N/ρ)，其中N = Σ a_i是路径的总长度（即金字塔的“尺寸”）。这意味着，如果我们能找到一个序列a，使得总长度N不太大（相对于n），但参数ρ非常小，那么就能得到一个很强的下界。 4. 对于三维情况（Proposition 4）：思路类似，但更为复杂。给定一个二维正整数向量序列v = (v_1, …, v_n)，构造三维随机游走：第k步以1/2概率在xy平面移动v_k，或以1/2概率在z轴方向移动||v_k||1（1-范数）。权重函数w’(p, p’, x)的构造不再是简单的对称形式，而是引入了µ{i,j}的平方根项进行非对称调整，这是为了在三维情况下获得更优的下界。最终证明的下界形式为Q(P_{3, N}) = Ω(N/λ)，其中λj = Σ{i=1}^{j} √µ_{i,j}， λ = max_j λ_j， N = Σ ||v_i||_1。
步骤三：构造最优序列以极小化ρ和λ（Propositions 3 和 5） 这是本文最具创新性和技术难点的部分。为了得到接近最优的下界，需要构造特定的序列a（对于二维）和v（对于三维），使得在总长度N = O(n^{1+δ})（对于任意小常数δ>0）的条件下，参数ρ（或λ）尽可能小。 1. 二维序列构造（Proposition 3）：作者采用了递归构造法。从一个简单的等差序列开始（此时ρ = O(1)但N = O(n^2)）。然后，通过引入B_h序列（B_h-sequence，即所有h元子和两两不同的正整数序列，由Bose和Chowla的引理保证存在性）作为“间隔”或“放大器”，迭代地构造新序列。在每一步迭代中，将当前序列与一个B_h序列的缩放版本重复多次拼接。通过巧妙的设计和利用Sárközy和Szemerédi的组合数论结果（Lemma 3，关于子集和分布的上界），作者证明了经过常数步迭代后，可以构造出一个长度为n的序列a，使得总长度N = Σ a_i = O(n^{1+δ})，同时保证ρ = O(1)。这意味着ρ被控制为一个常数，而N几乎线性增长。 2. 三维向量序列构造（Proposition 5）：构造更为复杂。作者从一个特定的二维向量集开始（如(1,m), (2,m-1), …, (m,1)），利用其几何性质（任意两个向量距离至少为1，且在任意方向上都有足够多的向量具有显著投影）和Halász的解析数论结果（Lemma 5 & 6，关于向量和集中性的上界），来保证初始序列的λ = O(log n)。然后，类似二维的递归构造，但这里使用B_h序列来生成大量的二维向量对（如(3b_i, 3b_j)），并将它们按特定顺序排列后与当前序列拼接、重复。通过Halász引理分析新构造的向量序列的和分布，最终可以构造出一个长度为n的向量序列v，使得总长度N = Σ ||v_i||_1 = O(n^{1+δ})，同时λ = O(log n)。
步骤四：综合得出结论 将步骤二的框架性下界与步骤三构造出的“好”序列相结合，并利用步骤一的归约，即可得到关于原始网格局部搜索问题的最终下界。
通过上述方法，本文证明了以下两个主要定理： * 定理 1：对于任意常数δ > 0，有RLS([n]^2) = ω(n^{1-δ}) 且 QLS([n]^2) = ω(n^{1⁄2-δ})。 * 定理 2：对于任意常数δ > 0，有QLS([n]^3) = ω(n^{1-δ})。
这里ω记号表示下界，忽略常数因子和可能的对数因子。具体来说： * 对于二维网格，随机化查询复杂度的下界被提升到了接近线性（n^{1-δ}），量子查询复杂度的下界被提升到了接近平方根（n^{1⁄2-δ}）。这与已知的上界O(n)和O(√n log log n)相比，差距被极大地缩小了（仅剩下一个任意小的指数δ以及可能的多对数因子）。特别是量子下界，几乎匹配了已知上界。 * 对于三维网格，量子查询复杂度的下界被提升到了接近线性（n^{1-δ}），与已知上界O(n)相比，同样只剩下指数δ的差距。
本研究的核心结论是：对于二维和三维网格图上的局部搜索问题，其量子查询复杂度几乎（up to subpolynomial factors）是紧的，分别约为Θ(√n)和Θ(n)。这一结果填补了低维局部搜索量子复杂度认知上的重大空白。
科学价值： 1. 解决了关键难题：它解决了Aaronson等人开创的基于随机游走的下界方法在低维情形下遇到的固有困难。低维空间自由度不足导致传统均匀步长随机游走的碰撞概率过高，无法获得紧下界。本文通过非均匀步长随机游走的构造，巧妙地克服了这一障碍。 2. 引入了强大的数学工具：论文的创新之处在于将组合数论（如Sárközy和Szemerédi的定理、Bose和Chowla的B_h序列构造、Halász的向量和估计）和概率论工具（如Essen不等式）深度应用于量子下界证明中。这展示了跨学科方法在解决理论计算机科学难题中的威力。 3. 推进了对量子查询能力的理解：研究结果进一步刻画了量子计算在优化问题（如局部搜索）上的能力边界。它表明，对于低维结构上的局部搜索，量子加速虽然存在（从经典的约n^{d/2}加速到量子的约n^{d/3}），但这种加速在d=2,3时是有限的，并且其精确复杂度可以通过本文的方法近乎确定。 4. 提供了新的证明技术范式：论文所发展的通过构造特殊序列来控制随机游走碰撞概率，进而应用于对手方法的技术，为后续研究其他问题的量子下界提供了新的思路和工具。
论文明确指出，四维网格[ n]^4的量子查询复杂度在ω(n^{6⁄5})和O(n^{4⁄3})之间仍存在差距，这作为一个重要的开放问题被提出。此外，文中详细回顾了局部搜索查询复杂度研究的历史脉络，引用了从Aldous、Aaronson到Santha、Szegedy、Zhang等多位学者的工作，为读者提供了该领域的清晰发展图景。附录中提供了关键引理（Lemma 9）的完整证明，展示了如何结合Essen不等式和B_h序列的性质来严格估计非均匀随机游走和的集中概率，这部分论证本身也具有独立的技术价值。