结果族 284：The optimal quartic separation between randomized and quantum queries · 学科：Mathematical physics · 验证状态：暂无形式化证明，请以社区核验为准
量子计算机查资料能少翻很多页，问题是”最坏能省多少次”。已知对任何任务，随机算法所需的查询次数不超过量子算法的四次方，有人猜三次方就够。本文造出一族”规规矩矩”的函数（对每个输入都要答对），其随机查询数几乎顶到四次方——四次方这个指数被证明最优，三次方猜想被推翻。
关键词卡片
@@M@@\mathbb{R}(f)=O(\mathbb{Q}(f)^4)@@看个具体例子
公式卡（数字版定理）：@@M@@\mathbb{Q}(F_{k,m})\le C_k\sqrt m\,(\log m)^{b_k}@@，而 @@M@@\mathbb{R}(F_{k,m})\ge c_k\,m^{2-1/k}/(\log m)^2@@；两者之比约为 @@M@@m^{3/2-1/k}@@，取 @@M@@k@@ 足够大，便任意接近四次幂。
为什么值得关心
它终结了随机与量子查询复杂度之间”指数究竟几次”的最后悬念：答案是 4，不是 3。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读说”量子计算机查资料能少翻很多页，问题是省多少次”。翻译成半数学语言：对象是一个由输入比特决定的布尔函数，以及两类翻页方式——随机地按位提问，或以量子叠加方式查询；操作是统计最坏情形下答对（错误率有界）所需的最少提问次数，并比较两类方式之间的差距最多能拉到多大。
第二级台阶
用本科术语精确化。随机查询复杂度 @@M@@\mathrm R(f)@@ 指任何随机算法在所有输入上错误至多 @@M@@1/3@@ 时所需的最坏情形比特查询数；量子查询复杂度 @@M@@\mathrm Q(f)@@ 同理，允许查询处于叠加态的输入位，两次查询之间的计算不受限制。全函数与部分函数的区别在于是否所有输入都必须答对。已知普适上界 @@M@@\mathrm R(f)=O((1+\mathrm Q(f))^4)@@——它由敏感度定理推出，挡住了指数级分离的可能。
第三级台阶
定理在此语境陈述：对每个固定整数 @@M@@k\ge2@@，构造全函数族 @@M@@F_{k,m}@@，其量子复杂度 @@M@@\mathrm Q(F_{k,m})\le C_k\sqrt m\,(\log m)^{b_k}@@，而随机复杂度 @@M@@\mathrm R(F_{k,m})\ge c_k\,m^{2-1/k}/(\log m)^2@@。”全函数、无承诺输入”这一假设挡住了部分函数里靠破坏承诺获得指数分离的捷径——所有获胜条件都必须是输入位的能行谓词。结论换用导读的话说：二者之比随 @@M@@k@@ 增大任意逼近四次幂，故任何指数 @@M@@\alpha<4@@ 的普适关系 @@M@@\mathrm R(f)=O((1+\mathrm Q(f))^\alpha)@@ 被否定，猜想的三次界证伪——四次，正是答案。
构造出一族全布尔函数 @@M@@F_{k,m}@@：量子算法只需 @@M@@\sqrt m\,(\log m)^{O_k(1)}@@ 次查询，而任何随机算法都需约 @@M@@m^{2-1/k}/(\log m)^2@@ 次，两者之比可任意逼近四次幂。这证明已知的四次普适上界指数最优，并推翻了此前猜想的三次关系。
查询复杂度 (query complexity) 统计算法读取输入比特的次数：@@M@@\mathbb{R}(f)@@ 与 @@M@@\mathbb{Q}(f)@@ 分别是随机与量子算法在最坏输入上错误至多 @@M@@1/3@@ 时所需的最少查询数，两次查询之间的计算不受限制。Grover 搜索对 OR 函数给出最优的二次加速；对只须在部分输入上正确的部分函数 (partial function)，量子甚至有指数加速，但 Beals 等人 2001 年证明对全函数 (total function) 有 @@M@@\D(f)=O(\mathbb{Q}(f)^6)@@，指数加速不复可能。2021 年 Aaronson、Ben-David、Kothari、Rao、Tal 借黄皓的敏感度定理 (sensitivity theorem) 把上界压缩到 @@M@@\D(f)=O(\mathbb{Q}(f)^4)@@，并猜想随机复杂度满足更强的三次关系 @@M@@\mathbb{R}(f)=O(\mathbb{Q}(f)^3)@@。构造方面，借助作弊表 (cheat sheet) 与指针技术，已知的随机–量子分离从 @@M@@5/2@@ 次幂逐步推进到 @@M@@3-o(1)@@。三次与四次之间孰是孰非，成为该领域最后悬而未决的指数问题，本文给出终局答案。
主定理断言最优指数 @@M@@\alpha_{\mathrm{tot}}=4@@：一方面所有全函数满足 @@M@@\mathbb{R}(f)=O((1+\mathbb{Q}(f))^4)@@（已知结果，附录给出自足证明）；另一方面，对每个固定整数 @@M@@k\ge2@@，存在全函数 @@M@@F_{k,m}@@（@@M@@m@@ 取充分大的 4 的幂）使
@@M@@D\mathbb{Q}(F_{k,m})\le C_k\sqrt m\,(\log m)^{b_k},\qquad \mathbb{R}(F_{k,m})\ge c_k\,\frac{m^{2-1/k}}{(\log m)^2}.@@
二者之比为 @@M@@m^{3/2-1/k}@@ 除以多项式对数因子，令 @@M@@k@@ 增大便任意接近四次幂。于是任何 @@M@@\alpha<4@@ 的普适关系 @@M@@\mathbb{R}(f)=O((1+\mathbb{Q}(f))^\alpha)@@ 都被否定，文献中猜想的三次界随之证伪。
构造是”带外向指针 (outward pointer) 的编址证书”。输入分 @@M@@m@@ 列，每列含 @@M@@m@@ 位串 @@M@@X_i@@、@@M@@r=O(\log m)@@ 个无承诺的 @@M@@k@@ 重 Forrelation 实例，以及按这 @@M@@r@@ 个实例的答案（即真实地址）索引的证书单元 @@M@@B_{i,s}@@，内存放指向其余各列的指针与电路求值记录 (transcript)。列 @@M@@i@@ 获胜，指 @@M@@X_i=1^m@@、真实地址单元的记录正确、且其指针在其余各列中都指到一个 0。@@M@@F_{k,m}=1@@ 当且仅当存在获胜列；获胜者至多一个，且所有条件皆是输入位的能行谓词，故无任何承诺。Forrelation 量子 @@M@@O_k(1)@@ 次查询可解，经典需 @@M@@\Omega_k(m^{1-1/k}/(\log m)^2)@@ 次（Bansal–Sinha 定理，唯一外部下界），此差距即分离引擎。
先证量子上界，核心是”概率比较锦标赛 (tournament)”引理。非获胜列的地址实例可违反承诺，两列比较的胜负概率任意，固定图上的算法不再适用。引理条件仅是：比较电路相干可逆、胜负概率互补 @@M@@a_{ij}+a_{ji}=1@@，且某个 @@M@@i_*@@ 以概率 @@M@@\ge1-\epsilon@@ 击败所有对手；结论为 @@M@@O(c\sqrt m\,T^2\log T)@@ 次查询可得含 @@M@@i_*@@ 的短列表。证明把”按乘法权重选 pivot、权重再乘 @@M@@a_{ip}@@“的理想过程精确量子化：叠加态与已有 pivot 逐一相干比较，成功分支的条件分布恰为权重分布，振幅放大 (amplitude amplification) 不改变它；互补性使总权重期望每步减半，保证 @@M@@i_*@@ 入选。外向指针恰提供支配性：获胜者的全 1 串令对手无处指零，自己却指认每个对手的零，故对手承诺被破坏也无妨。最后将候选的获胜条件拆成 @@M@@K@@ 个精确局部测试，Grover 搜索找失败者即完成验证。
再证随机下界，耦合两个输入：哑输入每列独立藏一个零、单元空白，函数值为 0；均匀选列 @@M@@I@@，抹去其零并填好其实地址单元，指针恰指向各列隐藏的零，得值为 1 的种植输入 (planted input)。区分二者须找到被抹的零，或碰到新填的单元。前者因零位在适应式查询下保持条件均匀，概率至多 @@M@@4G/m^2@@；后者或该列是”重列”——对其 Forrelation 串查询超过 @@M@@L@@ 次，概率至多 @@M@@G/(mL)@@——或须在 @@M@@L@@ 次查询内猜中 @@M@@r@@ 维地址向量。对最后情形，逐实例封顶的适应直接积 (direct product) 论证被写成超鞅：以各分量剩余最优猜中率之积为位势，期望在适应查询下不增，故猜中概率 @@M@@\le(2/3)^r@@，取并集后仍可忽略。三项合计小于 @@M@@1/3@@，故 @@M@@\mathbb{R}(F_{k,m})>\lfloor mL/100\rfloor@@（@@M@@L=\lfloor m^{1-1/k}/(\log m)^2\rfloor@@）。取 @@M@@k@@ 使 @@M@@2-1/k>\alpha/2@@，比值随 @@M@@m@@ 发散，排除一切 @@M@@\alpha<4@@。
本文暂无形式化证明，按 OpenAI 官方声明，未经形式化的结果可能有问题，请以社区核验为准。除 Bansal–Sinha 的 Forrelation 随机下界作为黑盒引用外，构造、锦标赛引理、耦合下界与附录中的四次上界重证均给出完整证明；本结果族 284 即以此篇为支柱，其”候选者比较”视角与近期证书复杂度 (certificate complexity) 分离工作一脉相承，而上界侧依赖的敏感度定理已是广为接受的结果。
问 1：构造里最关键、最难的一步是什么？
（答：锦标赛引理。非获胜列之间的比较胜负概率完全任意（地址实例可违反承诺），固定比较图的既有量子算法不再适用；引理只要求比较电路相干可逆、胜负概率互补 @@M@@a_{ij}+a_{ji}=1@@、某 @@M@@i_*@@ 以 @@M@@\ge1-\epsilon@@ 击败所有对手，就能用 @@M@@O(\sqrt m\,T^2\log T)@@ 次查询得到含 @@M@@i_*@@ 的短列表。把”乘法权重选 pivot”理想过程精确量子化——成功分支条件分布恰为权重分布——是全文技术心脏，振幅放大的保分布性质若有偏差，引理即失效。）
问 2：指针方向为什么是构造的灵魂、不能反着来？
（答：外向指针造成不对称支配：真实获胜者的全 1 串让对手的任何单元都无处指零，而获胜者的证书恰指认每个对手的零。于是即使对手的地址实例跑出承诺区、比较概率失控，廉价量子比较仍以高概率偏向获胜者——反过来指就两头都失控，函数也不再全。）
问 3：与既有谱系相比真正的新意在哪里？
（答：随机–量子分离此前止步 @@M@@3-o(1)@@（Bansal–Sinha、Sherstov–Storozhenko–Wu），本文推到任意接近四次幂，证明 @@M@@\alpha_{\mathrm{tot}}=4@@ 并证伪 ABKRT 的三次猜想；方法上把 Ben-David–Kothari、Ambainis–Iraids–Kokainis 的”候选者比较”视角从证书复杂度移植到随机复杂度，并用锦标赛引理驯服非承诺输入的任意行为。）
问 4：证明对外部结果的依赖有多深？
（答：下界侧唯一外部输入是 Bansal–Sinha 的 Forrelation 经典下界 @@M@@\Omega_k(m^{1-1/k}/(\log m)^2)@@，作黑盒引用；上界侧依赖黄皓敏感度定理（论文在附录自足重证四次上界）。Forrelation 定理本身经同行评议且被广泛使用，风险不大，但整个分离的定量形状完全由它塑形。）
问 5：最可能出错的环节是什么？
（答：随机下界的自适应直接积论证。论文把”逐实例封顶的猜中率”写成超鞅——以各分量剩余最优猜中率之积为位势，期望在适应式查询下不增——以避免对算法选列行为做条件化。种植输入与哑输入的耦合、@@M@@4G/m^2@@ 与 @@M@@G/(mL)@@ 两项概率控制里，任何一处条件化疏漏都会让 @@M@@(2/3)^r@@ 的直觉论证失效。这类”适应式直接积”是 AI 生成证明的高危地带。）
问 6：这个结果封顶了什么、谁来用？
（答：它终结全函数上随机–量子查询指数的悬案：答案恰为 4。查询复杂度社区由此拿到精确的相图，锦标赛引理可作为独立工具用于其他候选者比较型构造；对量子算法设计者，它划清了全函数场景量子加速的极限——想超过四次幂必须离开全函数世界。）
总评
这是一项干净的终局性构造：问题明确、答案彻底、上界自足重证；最大风险集中在锦标赛引理的相干采样细节与自适应直接积位势论证两处，且无形式化核验，社区复核前宜保持谨慎乐观。