资料快照：2026-10-07 · 中文研究导读

284｜经典随机与量子查询的最优幂次：总布尔函数可有近四次优势

官方问题族 284；本版含 1 篇稿件。以下为稿件结论的解释，未完成独立证明认证。来源版本：adc7f1241b42，核对日期：2026-10-07。

A. 问题与历史背景

查询复杂性把访问输入位看作主要成本，查询之间的计算不计费。令 $R(f)$ 为经典随机算法、 $Q(f)$ 为量子算法计算布尔函数 $f$ 所需的最坏查询次数，均要求每个输入上错误率至多 $1/3$ 。

对于仅在承诺集合上定义的问题，量子查询可有很大优势；但如果 $f:\{0,1\}^n\to\{0,1\}$ 对所有输入都有定义，即总布尔函数，量子与经典复杂性受到普遍的多项式关系约束。Grover 搜索展示平方级优势，而它并不是所有总函数分离的唯一可能结构。

关于 Huang 敏感性定理的量子推论给出 $D(f)=O(Q(f)^4)$ ，其中 $D$ 为确定性查询复杂性，因而也有 $R(f)\le D(f)=O(Q(f)^4)$ 。剩余问题是随机算法更强，会不会普遍把四次幂降为三次幂或其他更低指数？

原文声称四次幂就是最优普遍指数。对每个固定整数 $k\ge2$ ，构造一族总函数 $F_{k,m}$ ，其中 $m$ 取足够大的四的幂，使

Q(F_{k,m})\le C_k\sqrt m\,(\log m)^{b_k}, \qquad R(F_{k,m})\ge c_k\frac{m^{2-1/k}}{(\log m)^2}.

$c_k,C_k,b_k>0$ 是依赖 $k$ 的常数。忽略对数并以量子查询数衡量，分离幂次接近 $4-2/k$ ；先选择足够大的固定 $k$ ，再使 $m$ 变大，就能排除任何固定 $\alpha<4$ 的普遍界

R(f)=O\bigl((1+Q(f))^\alpha\bigr).

“近四次”准确表达了这一量词结构，不应改写为稿件已构造无任何对数损失的精确 $R=Q^4$ 等式。

**潜在积极影响：**刻画在最弱输入承诺条件下，量子访问还能比经典随机访问强多少，完善量子算法上限和下限的地图。构造方法也可能给其他查询或通信问题提供新的分离工具。

它使“经典能用随机性降低多少查询成本”这个问题更清楚，并提醒研究者不能把 Grover 的平方关系当作所有量子优势的普遍天花板。

**边界：**它不是任意实际计算的四次加速，更不是所有物理模拟、数据库查询或机器学习都能获得该增益。函数族可能非常人工，查询之间不计费的工作在硬件上仍然消耗时间；相干访问输入的代价也需计入应用分析。其直接贡献在量子计算理论，若要用于物理问题，还需构造既自然又保持这种分离的任务。

O284-01 A Nearly Quartic Separation Between Randomized and Quantum Query Complexity。形式化目录：未列入。BibTeX 键：OAI:A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026。