基于量子多维系统的精确与定点 Grover 搜索

本文基于 Tanay Roy 2026 年论文《Exact and Fixed-Point Grover Search with Qudits》整理。该文发表于 arXiv:2607.24658，来自费米实验室 SQMS 中心。原稿系统地将 Grover 搜索推广到 qudit（多维量子系统）架构上，涵盖标准搜索、确定性精确搜索和定点搜索的完整框架。本文聚焦于核心数学结构与物理直觉，对电路实现细节做适当精简，力求以清晰的中文讲解呈现这一统一框架的完整逻辑。

1. 引言：从量子比特到量子多维系统

1.1 Grover 搜索算法的里程碑地位

在量子算法的版图中，Grover 搜索算法是一个里程碑式的成果：在一个大小为 (N) 的无序数据库中，仅需 (O(\sqrt{N})) 次预言机查询即可找到目标元素，而经典算法需要 (O(N)) 次查询。这种二次加速使其成为量子算法和量子硬件的核心基准。

1.2 为什么需要 qudit？

传统的 Grover 算法基于量子比特（qubit，二维系统），数据库大小必须是 2 的幂次。然而，许多新兴量子平台天然支持量子多维系统（qudit）——具有多于两个能级的量子系统，作为基本信息载体。

Qudit 相比 qubit 的优势包括：

更大的局部希尔伯特空间：一个 (d) 维 qudit 可存储 (\log_2 d) 比特信息
更高的信息密度：减少表示给定数据库所需的载体数量
更少的纠缠操作：某些算法中可减少门操作次数
更浅的线路深度：使某些操作更兼容硬件的原生控制能力

更重要的是，qudit 寄存器可以自然地编码非 2 的幂次的数据库大小，甚至可以使用异构寄存器——由不同维度的 qudit 组成的混合系统。

1.3 本文的贡献

本文建立了一个统一的 qudit Grover 搜索框架，核心贡献包括：

将任意 qudit 寄存器上的搜索约化为有效的二维问题
给出了 Oracle 和扩散算子的显式 qudit 线路构造（有/无辅助量子比特）
系统化了四种确定性精确搜索策略
推广了定点搜索协议（(\pi/3) 算法和 YLC 算法）
提供了 Bloch 球上不同协议轨迹的直观可视化比较

2. 标准 qudit Grover 搜索

2.1 二维约化：从多维到二维

考虑一个大小为 (N) 的无序数据库，其中有 (M \geq 1) 个满足搜索条件的标记项。

与传统的量子比特寄存器不同，qudit 寄存器可以自然地编码任意大小的数据库。更一般地，可以使用异构寄存器，其 qudit 维度为 ({d_1, d_2, \ldots})，只要总希尔伯特空间维度 (D = \prod_j d_j \geq N)。

对于搜索动力学，微观编码可以压缩到两个正交子空间中：

标记子空间：由目标态 (|t_j\rangle) 张成
未标记子空间：由其余态 (|r_j\rangle) 张成

定义归一化的集体态：

$$
|T\rangle = \frac{1}{\sqrt{M}} \sum_{j=1}^{M} |t_j\rangle, \qquad |R\rangle = \frac{1}{\sqrt{N-M}} \sum_{j=1}^{N-M} |r_j\rangle.
$$

这两个正交归一向量将原始的搜索问题约化为一个二维问题。

2.2 初始态与 Bloch 球表示

使用映射 (|R\rangle = \binom{1}{0}) 和 (|T\rangle = \binom{0}{1})，搜索从以下状态开始：

$$
|\psi_0\rangle = \sqrt{1-\lambda},|R\rangle + \sqrt{\lambda},|T\rangle = \begin{pmatrix} \sqrt{1-\lambda} \ \sqrt{\lambda} \end{pmatrix},
$$

其中 (\lambda) 为初始处于目标子空间的概率。对于通常的等幅叠加初始化，(\lambda = M/N)；更一般地，唯一的要求是 (\lambda > 0)。

在 Bloch 球上，将初始态与一般叠加态 (\cos(\theta/2)|R\rangle + e^{i\phi}\sin(\theta/2)|T\rangle) 比较，可得初始态与 (z) 轴的夹角为

$$
\theta = 2\sin^{-1}(\sqrt{\lambda}).
$$

2.3 Oracle 算子与扩散算子

Grover 搜索由两个基本操作组成：

广义 Oracle 算子：对目标子空间施加相位

$$
S_o(\alpha) = I - (1 - e^{i\alpha})|T\rangle\langle T| = \begin{pmatrix} 1 & 0 \ 0 & e^{i\alpha} \end{pmatrix}.
$$

其作用可可视化为状态向量绕 (|T\rangle) 轴顺时针旋转角度 (\alpha)。特殊情况 (S_o(\pi)) 可视为关于 (z) 轴的反射。

广义扩散算子（关于初始态的反射）：

$$
S_r(\beta) = I - (1 - e^{i\beta})|\psi_0\rangle\langle\psi_0|.
$$

展开为矩阵形式：

$$
S_r(\beta) = \begin{pmatrix} e^{i\beta}\lambda + (1-\lambda) & (e^{i\beta}-1)\sqrt{\lambda(1-\lambda)} \ (e^{i\beta}-1)\sqrt{\lambda(1-\lambda)} & e^{i\beta}(1-\lambda) + \lambda \end{pmatrix}.
$$

其作用可可视化为当前状态向量绕 (|\psi_0\rangle) 轴顺时针旋转角度 (\beta)。

2.4 Grover 迭代与成功概率

Oracle 和反射算子的乘积称为 Grover 迭代子：

$$
G(\alpha, \beta) = S_r(\beta) S_o(\alpha).
$$

标准 Grover 迭代（(\alpha = \beta = \pi)）将状态向量绕 (y) 轴旋转 (2\theta)，限制在 (ZX) 平面内。

第 (k) 次迭代后的成功概率：

$$
P_{\text{succ}}(k) = |\langle T|\psi_k\rangle|^2 = \sin^2!\left[\left(k + \frac{1}{2}\right)\theta\right].
$$

显然，成功概率关于迭代次数是周期性的。

2.5 最优迭代次数

由于 (|\psi_0\rangle) 到南极（(|T\rangle)）的角距离为 (\pi - \theta)，到达 (|T\rangle) 所需的步数为 ((\pi - \theta)/(2\theta))，这通常不是整数。因此，最终状态会"欠冲"或"过冲"目标态。

标准 Grover 搜索的最优迭代次数为最接近的整数：

$$
k_{\text{opt}} = \left\lfloor \frac{\pi}{2\theta} - \frac{1}{2} \right\rceil = \left\lfloor \frac{\pi}{4\sin^{-1}\sqrt{\lambda}} - \frac{1}{2} \right\rfloor.
$$

对于小 (\lambda)（对应大数据库），

$$
k_{\text{opt}} \approx \frac{\pi}{4}\sqrt{\frac{N}{M}},
$$

这就是相对于经典搜索的二次加速。

数值示例：若 (\lambda = 0.002)，则 (\theta \approx 0.0894) 弧度，(k_{\text{opt}} \approx 17)，此时 (P_{\text{succ}} > 0.99)。

3. 量子线路实现

3.1 qudit Hadamard 门

制备等幅叠加态的常用方法是施加 qudit Hadamard 门（离散傅里叶变换门）：

$$
H_d = \frac{1}{\sqrt{d}} \sum_{j=0}^{d-1} \sum_{k=0}^{d-1} \omega^{jk} |j\rangle\langle k|, \qquad \omega = e^{2\pi i/d}.
$$

对于由维度为 ({d_1, d_2, \ldots, d_n}) 的 qudit 组成的异构系统，可以构造幺正算子

$$
U_d = H_{d_1} \otimes H_{d_2} \otimes \cdots \otimes H_{d_n}.
$$

注意：与量子比特情形不同（(H_2^\dagger = H_2)），一般情况下 (U_d^\dagger \neq U_d)。

3.2 Oracle 的线路实现

标准 Oracle (S_o(\pm\pi)) 将目标态的相位翻转：(|T\rangle \mapsto -|T\rangle)。可通过施加一个或多个 qudit 条件相位门实现：

$$
\text{CPHASE}_{d,m} = I_d - 2|m\rangle\langle m|.
$$

该门将态 (|m\rangle) 的相位翻转而保持其余基态不变。

3.3 扩散算子的线路分解

标准扩散算子可以分解为 qudit 操作：

$$
S_r(\pi) = I_d - 2|\psi_0\rangle\langle\psi_0| = U_d \cdot (I_d - 2|0_d\rangle\langle 0_d|) \cdot U_d^\dagger = U_d \cdot \text{CPHASE}_{d,0} \cdot U_d^\dagger.
$$

这表明反射算子可以用制备初始叠加态的幺正算子和一个仅作用于基态 (|0_d\rangle) 的条件相位门来构造。

3.4 替代条件相位门

相位门不必作用于 (|0\rangle)，可以选择任意基态 (|m\rangle)。利用 qudit 相位门 (Z_d) 和循环移位门 (X_d)（广义 NOT 门）：

$$
Z_d = \sum_{k=0}^{d-1} \omega^k |k\rangle\langle k|, \qquad X_d = \sum_{k=0}^{d-1} |k+1 \bmod d\rangle\langle k|,
$$

可以证明

$$
S_r(\pi) = (Z_d^\dagger)^m \cdot H_d \cdot \text{CPHASE}_{d,m} \cdot H_d^\dagger \cdot (Z_d)^m.
$$

额外的单 qudit (Z) 门最多增加两层线路深度。在许多平台（如超导系统）上，(Z) 门是虚拟门（通过坐标系更新实现），不影响算法运行时间。

3.5 辅助量子比特实现

在某些实现中，使用辅助量子比特来实现条件相位门可能更方便。核心思想是通过将辅助量子比特制备在某个幺正算子的负本征态上来获得相位反冲（phase kickback）。

即使对于 qudit Grover 搜索，也仅需一个量子比特辅助，与数据库大小无关。将辅助量子比特初始化为 ((|0\rangle - |1\rangle)/\sqrt{2})，当控制 qudit 处于态 (|m\rangle) 时对辅助量子比特施加条件 NOT 门：

$$
CX_{d,m} = \sum_{k \neq m} |k\rangle\langle k| \otimes I_2 + |m\rangle\langle m| \otimes X_2.
$$

可以验证，这等效地在数据 qudit 上实现了 (\text{CPHASE}_{d,m})，而辅助量子比特保持不变。

4. 确定性精确搜索

4.1 问题：欠冲与过冲

标准 Grover 协议通常以接近但不等于 1 的成功概率停止。这种残余误差源于：将 Bloch 向量对准 (|T\rangle) 所需的理想旋转角度通常不是标准 Grover 旋转 (2\theta) 的整数倍。

定义确定性迭代次数：

$$
k_{\text{certain}} = \left\lceil \frac{\pi}{2\theta} - \frac{1}{2} \right\rceil.
$$

可以验证 (k_{\text{certain}} - k_{\text{opt}}) 为 0 或 1；后者对应欠冲情况。

4.2 方法一：单参数确定性协议（D1p）

由 Long 等人提出，同时修改 Oracle 和扩散相位，在每次 Grover 迭代中使用相同角度 (\theta_c)：

$$
\theta_c = 2\sin^{-1}!\left(\frac{1}{\sqrt{\lambda}} \sin\frac{\pi}{4k_{\text{certain}}+2}\right).
$$

这样，经过 (k_{\text{certain}}) 步后，系统精确到达目标态：

$$
|T\rangle = [G(\theta_c, \theta_c)]^{k_{\text{certain}}} |\psi_0\rangle.
$$

实验优势：每次迭代使用相同的相位参数 (\theta_c)，简化了实验控制。

4.3 方法二：双参数确定性协议（D2p）

当 Oracle 相位由问题或硬件固定而无法调整时，D2p 协议保持 Oracle (S_o(\alpha)) 不变，仅调整扩散算子。

对于标准 Oracle 相位 (\alpha = \pm\pi)，D2p 在两个扩散相位 (\beta_1) 和 (\beta_2) 之间交替：

$$
|T\rangle = \cdots G(\pi, \beta_1) \cdot G(\pi, \beta_2) \cdot G(\pi, \beta_1) |\psi_0\rangle.
$$

这产生了在 (ZX) 平面测地线周围的锯齿形轨迹。

对偶版本：保持扩散相位固定为 (\pm\pi)，交替 Oracle 相位。交替结构可能通过部分噪声抵消提供实验优势。

4.4 方法三：三参数确定性协议（D3p）

进一步简化：大部分步骤使用标准 Grover 迭代，仅修改最后几步。

前 (k') 步使用标准扩散算子 (S_r(\pi))，剩余 (k_{\text{certain}} - k' \geq 2) 步在两个相位 (\beta_a) 和 (\beta_b) 之间交替：

$$
|T\rangle = G(\pi, \beta_a) \cdot G(\pi, \beta_b) \cdot G(\pi, \beta_a) \cdots [G(\pi, \pi)]^{k'} |\psi_0\rangle.
$$

示例：(\lambda = 0.005)，(k_{\text{certain}} = 11)，仅修改最后两步即可精确到达目标态。

4.5 方法四：辅助量子比特辅助方法

使用辅助量子比特来调节有效目标重叠。目标是选择有效重叠 (\lambda' \leq \lambda)，使得精确搜索条件恰好满足。

将辅助量子比特初始化为 (a|0\rangle + b|1\rangle)，选择 (|a|^2 \lambda = \lambda')。通过施加旋转 (R_y(\theta_a))，其中

$$
\theta_a = 2\cos^{-1}\sqrt{\frac{\lambda'}{\lambda}},
$$

联合初始态变为

$$
|\psi_0'\rangle = \left[\sqrt{1-\lambda}|R\rangle + \sqrt{\lambda}|T\rangle\right] \otimes \left[a|0\rangle_2 + \sqrt{1-|a|^2}|1\rangle_2\right].
$$

相应地修改 CPHASE 门和扩散算子，即可实现精确搜索。

4.6 四种方法的比较

方法	修改对象	参数数量	是否需要 Oracle 可调	辅助量子比特
D1p	Oracle + 扩散	1	是	否
D2p	仅扩散	2	否	否
D3p	仅最后几步扩散	3	否	否
方法四	有效重叠	1	否	是（1 个量子比特）

所有方法至多比标准协议多一次 Oracle 查询即可达到单位成功概率。

5. 定点搜索

5.1 动机

上述确定性协议假设初始目标比例 (\lambda) 是已知的。但在许多搜索问题中，(\lambda) 可能事先未知。此时，需要设计定点搜索算法——避免过冲或保证成功概率在迭代次数足够大时始终高于某个阈值 (P_{\min})。

5.2 (\pi/3) 算法

Grover 的定点协议将 Oracle 和扩散算子中的相位反转替换为较小的旋转 (\alpha = \beta = \pi/3)，递归构造为

$$
U_{k+1} = U_k S_r(\pi/3) U_k^\dagger S_o(\pi/3) U_k.
$$

由于每次递归都放大目标分量而不旋转过头，状态单调趋近 (|T\rangle)。对应的成功概率为

$$
P_{\text{succ}}(k) = 1 - (1-\lambda)^{3^k}.
$$

代价：递归构造在 (k) 次递归后需要 ((3^k - 1)/2) 次 Oracle 调用。因此，标度变为 (O(1/\lambda)) 而非 Grover 搜索的二次标度 (O(1/\sqrt{\lambda}))。

5.3 YLC 算法

Yoder–Low–Chuang（YLC）算法在保持定点搜索鲁棒性的同时保留了二次加速。

YLC 协议在每次 Grover 迭代中选择不同的相位对，使得一旦迭代次数超过阈值 (k_{\min})，成功概率对所有 (\lambda > \lambda_{\min}) 都有下界 (P_{\min})。阈值近似为

$$
k_{\min} \approx \frac{1}{2\sqrt{\delta}} \sqrt{\log\frac{2}{\lambda_{\min}}}, \qquad \delta = 1 - P_{\min}.
$$

这保持了特征性的二次标度。

对于固定迭代次数 (k)，YLC 相位按回文顺序选择：

$$
\alpha_j = \beta_{k-j+1} = 2\cot^{-1}!\left(\sqrt{1-\gamma^2}\tan\frac{2\pi j}{2k+1}\right),
$$

其中 (\gamma^{-1} = T_{1/(2k+1)}(1/\delta))，(T_n(x)) 为第一类 Chebyshev 多项式。

成功概率在 (P_{\min}) 和 1 之间振荡，而不会因为过冲而降至阈值以下。

5.4 三种搜索策略的比较

策略	查询复杂度	是否需要已知 (\lambda)	成功概率行为
标准 Grover	(O(1/\sqrt{\lambda}))	是（确定迭代次数）	周期性振荡
确定性协议	(O(1/\sqrt{\lambda}))	是（确定相位参数）	精确为 1
(\pi/3) 定点	(O(1/\lambda))	否	单调趋近 1
YLC 定点	(O(1/\sqrt{\lambda}))	否（仅需阈值）	在 (P_{\min}) 和 1 之间振荡

YLC 算法是最优的定点搜索：既保持了二次加速，又不需要精确知道 (\lambda)。

6. Bloch 球上的几何可视化

不同协议在 Bloch 球上的轨迹提供了直观的几何图像：

标准 Grover：在 (ZX) 平面上以固定步长 (2\theta) 旋转，通常停在 (|T\rangle) 附近但不精确到达
D1p：轨迹偏离 (ZX) 平面形成弧线，经过整数步后精确到达南极
D2p/D3p：在 (ZX) 平面测地线周围形成锯齿形路径
(\pi/3) 定点：单调螺旋趋近 (|T\rangle)
YLC 定点：在 (|T\rangle) 附近振荡但不远离

这些几何图像清晰地展示了不同相位选择如何引导状态趋向目标态。

7. 讨论与展望

7.1 实用工具箱

本文的结果为 qudit 处理器上的搜索算法设计提供了一个紧凑的工具箱。在标准、确定性、辅助辅助和定点协议之间的选择应基于以下因素：

广义相位门的可用性
受控门的保真度
目标比例的先验知识
可接受的线路深度

7.2 硬件平台的适配性

不同硬件平台的高保真纠缠操作可能不同。本文提供的多种替代构造（无辅助/有辅助、不同条件相位门选择）使得算法可以灵活适配各种平台：

超导系统：(Z) 门为虚拟门，SNAP 门可原生实现 CPHASE
离子阱系统：已展示通用 qudit 门集
光学系统：可利用轨道角动量实现 qudit

7.3 超越计算的应用

除了量子计算，qudit 振幅放大还可以改善量子传感——达到 Grover-Heisenberg 极限，这是最小传感时间的根本下界。

8. 参考文献

[1] Roy T. Exact and Fixed-Point Grover Search with Qudits[J]. arXiv:2607.24658 [quant-ph], 2026.

[2] Grover L K. Quantum mechanics helps in searching for a needle in a haystack[J]. Physical Review Letters, 1997, 79(2): 325–328.

[3] Long G L. Grover algorithm with zero theoretical failure rate[J]. Physical Review A, 2001, 64: 022307.

[4] Roy T, Jiang L, Schuster D I. Deterministic Grover search with a restricted oracle[J]. Physical Review Research, 2022, 4: L022013.

[5] Yoder T J, Low G H, Chuang I L. Fixed-point quantum search with an optimal number of queries[J]. Physical Review Letters, 2014, 113: 210501.

[6] Grover L K. Fixed-point quantum search[J]. Physical Review Letters, 2005, 95: 150501.

[7] Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation[J]. Contemporary Mathematics, 2002, 305: 53–74.