量子顺序搜索：半定规划模块与常数因子优势

未排序搜索中 Grover 把 \(N\) 降到 \(\sqrt N\)；已排序列表本来就能二分到 \(\log_2N\)，量子算法只能改善前面的常数。顺序搜索因此是研究精确量子查询常数的试验场：小规模算法可表示为半定规划（SDP），再递归拼接成任意规模算法；对抗法则证明仍需 \(\Omega(\log N)\) 查询。

1. 阈值 oracle 表述

把“\(x\) 应插到排序表哪里”改写为未知阈值 \(t\in\{0,\ldots,N}\)。定义位串

\[\begin{split} z_i^{(t)}= \begin{cases} 0,&i<t,\\ 1,&i\ge t. \end{cases} \end{split}\]

oracle 可用相位形式

\[ O_t|i\rangle=(-1)^{z_i^{(t)}}|i\rangle. \]

任务是确定 \(t\)。经典每次比较最多把候选区间二分，因此最坏至少 \(\lceil\log_2(N+1)\rceil\) 次，binary search 达到该界。

量子查询可在多个 \(i\) 的叠加上施加相位，但不同阈值 oracle 的相位模式高度相关，所以不会像无结构搜索那样获得平方根加速。

2. 用 Gram 矩阵描述整个量子算法

对每个可能阈值 \(t\)，令 \(|\psi_t^{(q)}\rangle\) 是第 \(q\) 次查询前的算法状态。把两两内积组成 Gram 矩阵

\[ G^{(q)}_{st} =\langle\psi_s^{(q)}|\psi_t^{(q)}\rangle. \]

输入无关酉操作保持所有内积，所以只需追踪查询如何改变 \(G\)。在查询索引 \(i\) 上分解状态，设对应 PSD Gram 分量为 \(G_i^{(q)}\succeq0\)，则

\[ G^{(q)}=\sum_iG_i^{(q)}. \]

相位 oracle 对阈值 \(s,t\) 的相对符号为

\[ (D_i)_{st}=(-1)^{z_i^{(s)}\oplus z_i^{(t)}}. \]

一次查询后 Gram 矩阵变成

\[ \widetilde G^{(q)} =\sum_iG_i^{(q)}\circ D_i, \]

其中 \(\circ\) 是 Hadamard 积。下一段输入无关酉只要求新状态具有同一 \(\widetilde G^{(q)}\)，因此“是否存在 \(Q\) 查询算法”可写成一组 PSD 变量与线性等式的 SDP。

精确识别要求最终状态两两正交：

\[ G^{(Q)}=I. \]

有界错误则允许非对角内积足够小，并加入 measurement feasibility 约束。

3. 对称性如何缩小 SDP

直接 SDP 有 \(N+1\) 个输入标签。把有序问题嵌入一个带周期/反射对称的扩展问题后，最优算法可平均成 translation-invariant 形式，Gram 矩阵近似只依赖 \(s-t\)。循环矩阵由 Fourier 基对角化，PSD 条件化成若干非负 Laurent 多项式系数约束。

因此可数值搜索“小块问题”：给定块长 \(M\) 与查询数 \(q\)，寻找一个精确区分块内阈值的可行 SDP，并从 Gram 分解显式恢复各步酉矩阵。数值解必须再高精度化或解析验证，不能只把浮点 SDP 状态当作精确算法证明。

4. 小块递归给出任意 \(N\)

若一个 \(q\) 查询子程序能确定阈值落在 \(M\) 个有序子区间中的哪一个，就把长度 \(N\) 的列表按比例分成 \(M\) 块：

  1. 用该子程序找出正确块；

  2. 在块内递归使用同一程序；

  3. 直到候选只剩一个位置。

递归深度约为 \(\log_MN\)，查询总数

\[ Q(N)\le q\log_MN+O(1) =\frac q{\log_2M}\log_2N+O(1). \]

SDP 找到 \(q=4,M=605\) 的精确模块，于是

\[ Q(N)\le4\log_{605}N+O(1) \approx0.433\log_2N+O(1). \]

它比早期约 \(0.53\log_2N\) 的 invariant algorithm 更好，但仍只改变常数。

5. 对抗下界为何仍是对数级

令 adversary 矩阵 \(\Gamma\) 以阈值 \(s,t\) 为索引，并让相近阈值具有精心选择的权重。一次查询位置 \(i\) 只能区分那些阈值分别位于 \(i\) 两侧的输入对，即用

\[ (\Delta_i)_{st}=1[z_i^{(s)}\ne z_i^{(t)}] \]

过滤 \(\Gamma\)。对抗比值

\[ \frac{\|\Gamma\|} {\max_i\|\Gamma\circ\Delta_i\|} \]

给出查询下界。Høyer--Neerbek--Shi 及 Childs--Lee 的优化得到

\[ Q(N)\ge \frac{\ln2}{\pi}\log_2N-O(1) \approx0.221\log_2N-O(1). \]

上界 0.433 与下界 0.221 之间仍有常数空隙，精确渐近常数未知。随机化量子算法可通过 adaptive learning 把期望查询常数降到 \(1/3\) 以下，但期望、有界错误与最坏精确三种口径不能直接比较。

6. 一个两查询干涉直觉

经典查询索引 \(i\) 只告诉阈值在左还是右。量子查询态

\[ \sum_i\alpha_i|i\rangle \]

会按整条阶跃函数同时翻转一段后缀的相位。后续酉变换可以让多个候选阈值的相位边界产生不同干涉模式。SDP 的 Gram 矩阵正是在全局优化：每一步应该把哪些候选状态拉开，同时不违反“一次查询只能施加一个阶跃相位”的限制。

7. 小结与习题

  • 顺序搜索的量子优势只能是常数因子，复杂度仍为 \(\Theta(\log N)\)。

  • 查询前状态的 Gram 矩阵把量子算法存在性化成 SDP。

  • 小规模精确模块可递归，常数为 \(q/\log_2M\)。

  • 对抗矩阵证明下界，当前上下界常数尚未闭合。

  1. 写出 \(N=3\) 时四个阈值 oracle 的相位向量。

  2. 证明输入无关酉操作保持 Gram 矩阵。

  3. 从 \(q=4,M=605\) 计算 \(q/\log_2M\)。

  4. 解释“期望少于 \(\frac13\log_2N\)”为何不与精确最坏 \(0.433\log_2N\) 直接矛盾。

参考文献