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

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

## A. 问题与历史背景

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

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

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

## B. 稿件结论

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

```math
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$ 的普遍界

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

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

## C. 为何有价值

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

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

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

## 原稿及配套材料

- **O284-01** [A Nearly Quartic Separation Between Randomized and Quantum Query Complexity](https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026/quartic-query-separation.pdf)。形式化目录：未列入。BibTeX 键：`OAI:A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026`。

[返回总览](../README.md) · [来源与核验记录](../sources.md)