混合量子-经典算法的查询复杂度紧界是什么？

混合模型限制每个相干块的查询数

论文在查询模型中研究混合量子-经典算法。计算过程是经典的，但可以调用量子子程序，每个子程序最多允许q次oracle查询。每个子程序结束时，所有量子寄存器被测量并丢弃，测量结果传给经典算法，由它选择下一个子程序。

形式上，该算法是一棵有限有根树：每个内部顶点对应一个量子算法，它最多做q次查询并以一次测量结束；出边由测量结果标记；叶子携带经典输出。复杂度取所有在有效输入上可能出现的根到叶路径中，路径上各内部顶点查询数之和的最大值。

参数q是论文所调节的杠杆。取q = 1即回到经典复杂度，而让q达到Q(f)，即无限制的容错量子查询复杂度，则回到标准量子情形。两者之间正是论文刻画的混合区间。

相位与振幅估计按q与ε平方的倒数缩放

前两组结果涉及以精度ε、成功概率至少2/3估计一个相位或一个振幅。对于相位估计，给定对未知酉算子U的受控查询访问以及本征态U|ψ⟩ = e^{iφ}|ψ⟩，将φ估计到精度ε ∈ (0,1)的混合查询复杂度为Θ(1/ε + 1/(qε²))。

对于振幅估计，给定对酉算子U的受控访问，U|0̄⟩ = √s|1⟩|ψ₁⟩ + √(1−s)|0⟩|ψ₀⟩，且仅承诺对某个已知p ∈ (0,1)有s(1−s) ≤ p(1−p)，则将s估计到精度ε ≤ p(1−p)的复杂度为Θ(√(p(1−p))/ε + p(1−p)/(qε²))。

两个下界都来自同一个关于酉算子二分类的定理：若子程序对U和U†最多使用q次受控查询，且两类中存在U₀、U₁满足‖U₀ − U₁‖ = ε，则任何容错混合算法在最坏情况下需要Ω(1/ε + 1/(qε²))次查询。其中1/ε项是无限制量子界，1/(qε²)项是混合惩罚。

匹配的上界来自无偏估计量。对于相位估计，将子程序重复ℓ = Θ(1/(q²ε²))次可得到e^{iφ}的无偏估计量，方差为O(1/(q²ℓ))。对于振幅估计，分析分为几个区间：q = O(1)时直接测量U|0̄⟩；1 ≪ q ≤ (p(1−p))^{−1/2}时使用约q次振幅放大并输出第一个量子比特；q更大时运行m = 4的提升过程并取相位估计的实部。所有情形下估计量都是无偏的，唯振幅估计的中间区间例外；且算法是非自适应的，因此所有深度q的电路可以并行运行。

搜索与AND-OR在混合代价中增加平方根项

对于搜索，设定是标准的：x₁, …, x_N ∈ {0,1}并具有查询访问，任务是区分没有任何i满足x_i = 1的情形与恰好存在一个这样的i的情形。论文证明Θ(√N + N/q)次查询是必要且充分的。√N项是熟悉的Grover界，N/q是q较小时占主导的类经典项。

该界最初由Sun和Zheng证明；此处通过用于二分类的同一框架重新导出，这也是论文将其纳入的既定理由。

第三个问题是两级AND-OR树F(x) = ⋀_{i=1}^{m} ⋁_{j=1}^{n} x_{ij}，其中x ∈ {0,1}^{m×n}且m, n ≥ 2，它建模嵌套搜索。论文证明计算F需要Θ(√(mn) + mn/q)次查询，且该界是必要且充分的。上界来自MMO24；下界由本文首次给出。

这四个界都被表述为对从1到Q(f)（相应问题的无限制量子查询复杂度）的每个q，在常数因子内最优。这正是它们紧的含义：它们在经典端点与量子端点之间精确插值。

卡方型进度度量驱动下界证明

论文的方法论贡献是一套系统证明混合下界的方法，作者称此前这类证明一直非常零散。该框架追踪transcript：即相继量子块产生的经典测量结果序列。对每个输入，混合算法在transcript上诱导一个概率分布；若算法以容错方式区分两个输入，这些transcript分布必须具有常数统计距离。

这一差异由χ²型进度度量M(p, q) = Σ_z (p(z) − q(z))² / (2(p(z) + q(z)))刻画。柯西–施瓦茨界将其与全变差距离联系起来：TV(p, q) ≤ √M。若算法以误差至多1/3区分两种情形，则最终全变差距离至少为1/3，从而M_T ≥ 1/9。

关键的单块不等式（引理1）将一次子程序后进度的增量上界为(1 − M_t(h))·‖|ψ₀⟩ − |ψ₁⟩‖²，其中|ψ₀⟩和|ψ₁⟩是子程序在两种oracle下最终测量前的状态。结合r次查询子程序至多将状态改变r·‖U₀ − U₁‖这一事实，可得M_T ≤ qε²L，其中L是最坏情况总查询数，因此L = Ω(1/(qε²))。对整个计算单独应用标准混合论证给出L = Ω(1/ε)，两者结合即得所述界。

对于搜索，证明使用补量M′ = 1 − M，并以Σ_i M′^{(i)}_t（对唯一1的N个可能位置求和）作为进度度量。对于AND-OR，论证更为精细：它将基于transcript的度量与混合压缩oracle框架的思想结合，包括归约到一种替代的混合计算模型，以及分别追踪算法积累的经典信息与量子信息的两个进度度量。与那项早期工作不同，这些要素被纳入一个对抗式论证，而非用于追踪压缩oracle。

分布区分在至多对数因子内是紧的

作为进一步应用，论文刻画了在纯化访问下区分两个离散分布r, s ∈ Δ_k的混合查询复杂度：未知酉算子U_p对应均匀随机的p ∈ {r, s}，满足U_p|0̄⟩ = Σ_{i∈[k]} √(p_i)|i⟩|ψ_i⟩。在受控访问U_p下，以成功概率至少2/3区分U_r与U_s的代价为Θ̃(1/d_H + 1/(q d_H²))，其中d_H是Hellinger距离d_H(r, s) = √(Σ_{i∈[k]} (√r_i − √s_i)² / 2)。

该界在至多对数因子内是紧的，而非在常数因子内。下界在k = 2情形下已本质上等价于振幅估计推论。上界归约到该二元情形：总存在子集B ⊂ [k]，使诱导的二元分布满足1 ≤ d_H(r, s)/d_H(r_B, s_B) ≤ O(min(k, log(1/d_H)))，因此对r_B, s_B应用振幅估计算法在常数k下渐近紧，一般情况下在d_H上至多有一个对数松弛。

论文指出，该访问模型相当通用，包含通过量子蒙特卡洛方法获得分布的情形，且该结果在不相干样本复杂度与完全相干查询复杂度之间平滑插值。

开放问题标出框架的边界

论文明确指出混合下界的研究才刚刚起步，并列出四个开放问题。第一，引理4——它通过查询两个输入中不同变量的概率来上界transcript分布的可区分性——目前还缺少与前面章节类似的更直接证明。第二，该方法可扩展到更大常数深度的AND-OR树的紧下界，但大O常数随深度增长；任意深度是否允许紧界仍是开放的。

第三，近似计数，例如区分等于1的变量比例是1/2还是1/2 + ε，是一个自然目标，因为其最优量子下界由带简单输入分布的正权对抗法证明，这暗示该框架可能可以扩展。第四，元素区分性尚未解决：自然的分解给出O(max(N^{2/3}, N²/q²))次查询，只有当q > √N时才优于经典算法，而这是否最优尚不清楚。作者指出两个困难——正权对抗法不再给出最优量子界，且混合模型与噪声查询模型可能不同，因此噪声模型可能无法给出最优下界。

这些被表述为开放问题，而非结果。它们界定了论文的四个紧界及其分布区分界实际确立了什么的边界。

把界读作关于q的权衡曲线

阅读这篇论文最有用的方式，是把它看作一条权衡曲线而非单个数字。每个结果都具有（无限制量子项）+（类经典项）/q的形式，而两个区间之间的交叉点决定了混合实现是否保留优势。对于搜索，混合代价是√N + N/q，因此量子优势只在N/q不比√N大太多时保留，大致是q超过√N时。对于两级AND-OR树，类似的比较发生在√(mn)与mn/q之间。

对于相位与振幅估计，比较发生在1/ε与1/(qε²)之间，以及√(p(1−p))/ε与p(1−p)/(qε²)之间。振幅估计结果带有一个值得注意的额外条件：承诺是对某个已知p有s(1−s) ≤ p(1−p)，且所述复杂度在ε ≤ p(1−p)时成立。论文还指出，估计量是无偏的，唯1 ≪ q ≪ (p(1−p))^{−1/2}区间例外，此时算法通过T_q(p)/q给出p的潜在有偏估计量。

分布区分结果是唯一一处紧性只到对数因子的地方，其松弛通过二元归约被限制在O(min(k, log(1/d_H)))。这是值得记住的论文特有阈值：对常数k该界渐近紧，而对数松弛随结果数k增大以及Hellinger距离变小而增长。

本文引用的文献