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

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

## 1. 阈值 oracle 表述

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

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

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$ 直接矛盾。

## 参考文献

- Zoo 编号 39：Farhi、Goldstone、Gutmann 与 Sipser, [Invariant Quantum Algorithms for Insertion into an Ordered List](https://arxiv.org/abs/quant-ph/9901059).
- Zoo 编号 103：Andrew Childs、Andrew Landahl 与 Pablo Parrilo, [Improved Quantum Algorithms for the Ordered Search Problem via Semidefinite Programming](https://arxiv.org/abs/quant-ph/0608161).
- Zoo 编号 219、24：Høyer--Neerbek--Shi 与 [Childs--Lee](https://arxiv.org/abs/0708.3396) 的 adversary 下界。
- Zoo 编号 10：Michael Ben-Or 与 Avinatan Hassidim, [Quantum Search in an Ordered List via Adaptive Learning](https://arxiv.org/abs/quant-ph/0703231).