1. 论文基本信息

1.1. 标题

A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search (基于 Grover 算法的通过适应度引导搜索解决完美迷宫问题的量子算法)

1.2. 作者

Michelle L. Wu

1.3. 发表期刊/会议

未明确指明发表期刊或会议。根据提供的链接 arxiv.org/abs/2507.21937v2，该论文作为预印本 (preprint) 发布在 arXiv 上。arXiv 是一个开放获取的预印本服务器，允许研究人员在正式同行评审和发表前分享他们的工作。

1.4. 发表年份

2025年。具体发布时间为世界协调时 (UTC) 2025年7月29日15:51:19。

1.5. 摘要

本文提出了一种量子算法，通过将寻路任务转化为结构化搜索问题来解决完美迷宫。该算法基于 Grover 算法的振幅放大 (amplitude amplification) 原理，将所有候选路径以叠加态 (superposition) 编码，并使用基于量子算术 (quantum arithmetic) 的可逆适应度算子 (reversible fitness operator) 评估它们接近目标点的程度。一个与 Grover 算法兼容的神谕 (oracle) 会标记高适应度的状态，并通过自适应截止 (adaptive cutoff) 策略迭代地细化搜索。论文提供了形式化定义、酉变换 (unitary construction) 构建和收敛性保证，以及资源分析，表明该算法在迷宫大小和路径长度方面具有高效的扩展性。该框架为量子混合寻路和规划奠定了基础。从编码到放大，包括神谕设计和适应度评估的完整算法流程都得到了详细说明。该方法易于扩展到其他搜索领域，包括树状或无环图上的导航。

1.6. 原文链接

官方 arXiv 链接: https://arxiv.org/abs/2507.21937v2 PDF 链接: https://arxiv.org/pdf/2507.21937v2.pdf 发布状态：预印本 (preprint)

2. 整体概括

2.1. 研究背景与动机

核心问题： 迷宫求解是一个基础的计算问题，广泛应用于机器人学、博弈论和人工智能领域。具体到二维完美迷宫（定义为无环、完全连通的网格），尽管其结构受限，但仍属于计算上难以处理的 NP 完全问题。

重要性与现有挑战： 经典的迷宫求解方法，如回溯 (backtracking) 和广度优先搜索 (breadth-first search, BFS)，其计算复杂度与迷宫大小和分支因子呈指数级关系，这限制了它们在大型迷宫实例中的实际应用。这意味着，随着迷宫规模的增大，经典方法所需的计算时间会迅速变得无法接受。

量子计算的切入点： 量子计算提供了一种新的范式，它利用叠加 (superposition) 和干涉 (interference) 原理来实现算法加速。特别是 Grover 搜索算法，为非结构化搜索问题提供了二次加速，并可以作为在量子领域构建结构化搜索任务的基础。

本文创新思路： 尽管之前的研究已经从概念层面探索了量子迷宫求解方法（例如，适应度评估和神谕设计的显式电路构建），但这些工作缺乏严格定义。本文旨在填补这一空白，提供一个完整的量子算法，通过将寻路问题框架化为结构化量子搜索，并给出形式化数学定义、电路级实现和完整的收敛性分析。

2.2. 核心贡献/主要发现

本文的主要贡献在于提出了一个完整的、基于 Grover 算法的量子迷宫求解框架，并提供了严谨的理论支撑和实现细节：

• 完整的量子算法框架： 提出了一个从路径编码、适应度评估到振幅放大的完整量子算法流程，用于解决完美迷宫问题。
• 可逆适应度算子 (Reversible Fitness Operator)： 设计并构建了一个可逆的量子算子，用于评估路径的质量（即路径终点与目标点之间的接近程度）。该算子基于量子算术，并严格遵守酉性 (unitarity) 要求，确保其可以集成到量子电路中。
• Grover 兼容神谕 (Grover-Compatible Oracle)： 构建了一个能够选择性地标记高适应度路径的神谕。该神谕通过应用条件相位翻转来实现，并支持经典或量子的截止值 (cutoff) 阈值，这对于迭代搜索至关重要。
• 自适应截止策略 (Adaptive Cutoff Strategy)： 引入了一种迭代的自适应截止策略，用于逐步细化搜索空间。该策略通过单调更新截止值来保证算法的收敛性，使其能够有效地找到最优解。
• 形式化理论与收敛性保证： 提供了算法的正式数学定义、酉变换构建、Grover 迭代的几何解释和振幅动力学分析，并对自适应截止策略的收敛性进行了严格证明。
• 资源分析： 对算法的量子电路深度和量子比特 (qubit) 数量进行了资源分析，表明其与迷宫大小和路径长度具有高效的扩展性。
• 可扩展性： 该框架不仅适用于迷宫问题，还可扩展到其他搜索领域，例如树状或无环图中的导航问题。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 量子计算 (Quantum Computing)

量子计算是一种利用量子力学原理（如叠加、纠缠、干涉）进行计算的新型计算范式。与经典计算机使用比特 (bit) 存储0或1的确定性状态不同，量子计算机使用量子比特 (qubit)。

3.1.2. 量子比特 (Qubit)

量子比特是量子计算的基本信息单位。一个量子比特可以处于0态、1态，或0态和1态的任意叠加态 (superposition)。数学上，一个量子比特的状态可以表示为 $| \psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$，其中 $\alpha$ 和 $\beta$ 是复数，且满足 $|\alpha|^2 + |\beta|^2 = 1$。$|\alpha|^2$ 表示测量结果为 $| 0 \rangle$ 的概率，$|\beta|^2$ 表示测量结果为 $| 1 \rangle$ 的概率。

3.1.3. 量子叠加 (Quantum Superposition)

量子叠加是指一个量子系统（如量子比特）可以同时处于多个量子态的线性组合中。例如，一个量子比特可以同时是0和1，直到被测量。这种特性使得量子计算机能够并行处理大量信息。

3.1.4. 量子纠缠 (Quantum Entanglement)

量子纠缠是指两个或多个量子比特之间存在一种特殊的关联，无论它们相距多远，一个量子比特的状态会瞬间影响另一个量子比特的状态。纠缠是量子计算中实现某些算法加速的关键资源。

3.1.5. 酉变换 (Unitary Transformation)

在量子力学中，量子系统的演化由酉变换 (unitary transformation) 描述。酉变换是一种保持内积不变的线性变换，对应于量子门 (quantum gate)。如果一个操作符 $U$ 是酉的，则其共轭转置 $U^\dagger$ 也是它的逆，即 $U^\dagger U = UU^\dagger = I$，其中 $I$ 是单位矩阵。量子计算中的所有操作都必须是酉的，以确保概率守恒。

3.1.6. 可逆计算 (Reversible Computing)

可逆计算是指计算过程在逻辑上是可逆的，即从输出可以唯一地确定输入。在量子计算中，所有基本量子门都是可逆的，因为它们是酉的。可逆计算的一个重要优点是，理论上它不产生热量损耗（不擦除信息），这在量子电路设计中至关重要，因为任何信息擦除操作都是不可逆的，会引入热量。在本文中，适应度算子和神谕的构建都强调了可逆性，以确保它们可以作为酉操作符集成到量子电路中。

3.1.7. Grover 搜索算法 (Grover's Search Algorithm)

Grover 搜索算法是一种量子算法，用于在非结构化数据库中寻找特定项，与经典算法相比，它提供了平方级加速。 原理： 假设我们有一个包含 $N$ 个元素的数据库，其中有 $k$ 个“标记”元素。经典搜索平均需要 $O(N)$ 次操作才能找到一个标记元素。Grover 算法只需要 $O(\sqrt{N/k})$ 次操作。 Grover 算法的核心在于两个酉操作符的迭代应用：

1. 神谕 (Oracle) $O$： 标记 (mark) 解决方案。它通过对标记态应用相位翻转 (phase flip) 来区分它们。 $$O|x\rangle = (-1)^{f(x)}|x\rangle$$ 其中 $f(x)=1$ 如果 $x$ 是标记态，否则 $f(x)=0$。
2. 扩散算子 (Diffuser) $D$： 放大标记态的振幅，减小未标记态的振幅。它是一个关于均匀叠加态 $|s\rangle$ 的反射。 $D = 2|s\rangle\langle s| - I$ 其中 $|s\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$ 是所有态的均匀叠加。

Grover 迭代算子定义为 $G = DO$。每一次迭代 $G$ 都会将当前状态向量在由标记态子空间和未标记态子空间组成的二维平面内旋转一个角度，从而逐渐增大标记态的振幅，直到其概率接近1。

3.1.8. 汉明距离 (Manhattan distance) / 欧几里得距离 (Euclidean distance)

• 汉明距离 (Manhattan distance)： 也称为 $L_1$ 距离或城市街区距离。在二维平面上，对于两点 $(x_1, y_1)$ 和 $(x_2, y_2)$，其汉明距离为 $|x_1 - x_2| + |y_1 - y_2|$。
• 欧几里得距离 (Euclidean distance)： 也称为 $L_2$ 距离。在二维平面上，对于两点 $(x_1, y_1)$ 和 $(x_2, y_2)$，其欧几里得距离为 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$。
• 平方欧几里得距离 (Squared Euclidean distance)： 本文使用了平方欧几里得距离，即 $(x_1 - x_2)^2 + (y_1 - y_2)^2$。这样做的好处是避免了在量子电路中计算平方根，这会显著增加电路复杂性。

3.2. 前人工作

论文指出，尽管之前有一些概念性的研究探索了量子迷宫求解方法，例如显式电路构建来评估适应度或设计神谕，但这些工作通常“没有被严格定义”。这意味着这些研究可能缺乏形式化的数学定义、详细的电路级实现细节或完整的收敛性分析。本文正是为了填补这些空白，为量子迷宫求解提供一个更严谨、更完整的框架。因此，本文没有引用具体的“前人工作”来作为对比基线，而是将自身定位为在概念性工作基础上的一个实质性推进。

3.3. 技术演进

迷宫求解问题作为人工智能和计算科学中的一个经典问题，其技术演进大致可以分为以下几个阶段：

1. 经典图搜索算法： 早期主要依赖于深度优先搜索 (Depth-First Search, DFS)、广度优先搜索 (Breadth-First Search, BFS)、A* 搜索等算法。这些算法在小规模迷宫中表现良好，但在迷宫规模增大时，其计算复杂度（通常是指数级）会迅速增加，成为瓶颈。
2. 启发式搜索与优化： 为了应对大规模问题，研究者引入了启发式方法，如 A* 算法，通过启发函数来引导搜索方向，减少搜索空间。
3. 量子计算的引入： 随着量子计算理论的发展，研究者开始探索如何利用量子特性来加速计算。对于搜索问题，Grover 算法的出现为在非结构化数据库中寻找目标提供了二次加速的潜力。
4. 量子化寻路与规划： 在量子计算背景下，迷宫求解或寻路问题被视为一种结构化搜索问题。早期的量子方法可能侧重于概念验证，或者对特定组件（如适应度函数或神谕）进行初步的量子化设计。 本文的地位： 本文的工作正处于量子化寻路与规划的演进阶段。它不是提出一个全新的量子算法范式，而是在 Grover 搜索算法的基础上，针对完美迷宫求解这一具体问题，提供了一个“完整且严格定义”的解决方案。它将之前可能分散或不完善的量子化组件（如适应度算子和神谕）整合进一个统一的框架，并辅以形式化证明和资源分析，从而推动该领域从概念探索走向更具体的算法实现。

3.4. 差异化分析

本文的方法与相关工作（此处指之前概念性的量子迷宫求解探索）的核心区别和创新点体现在以下几个方面：

• 形式化严谨性： 本文提供了迷宫结构、路径表示、适应度评估、神谕设计以及 Grover 迭代的“形式化数学定义”。这与之前可能停留在“概念层面”的探索形成对比，为算法的正确性、可实现性和可分析性奠定了坚实基础。

• 电路级实现细节： 论文明确地给出了适应度算子和神谕的“电路级实现”方案。这包括如何使用可逆量子算术（如加法器、减法器、乘法器）构建适应度函数，以及如何使用比较器和受控相位门构建神谕。这种细节层次的描述对于实际在量子硬件上实现算法至关重要。

• 完整收敛性分析： 本文不仅描述了算法，还提供了“完整的收敛性分析”。这包括 Grover 振幅放大过程的几何解释、成功概率的推导，以及特别是“自适应截止策略”的收敛性证明。这保证了算法能够有效地找到最优解，并提供了概率保障。

• 自适应截止策略的引入： 这是一个重要的创新点。通过动态调整神谕的截止值，算法可以逐步缩小搜索范围，优先放大更高质量的路径。这种机制比固定截止值的 Grover 搜索更具鲁棒性，尤其是在最优解的数量未知或有多个近似最优解的情况下。

• 资源分析： 论文对量子电路的资源需求（如量子比特数量和门深度）进行了详细分析。这对于评估算法在近中期量子硬件上的可行性至关重要，并提供了优化的方向。

  总而言之，本文的创新点在于将零散的概念性量子迷宫求解想法，提升到了一个具有完整理论框架、详细电路实现指导和严格性能分析的成熟量子算法。

4. 方法论

4.1. 方法原理

本文的核心思想是将完美迷宫 (perfect mazes) 求解问题转换为一个结构化的量子搜索问题，并利用 Grover 算法的振幅放大 (amplitude amplification) 机制来加速寻找最优路径。其基本原理是：

1. 路径编码与叠加 (Path Encoding and Superposition)： 首先，将迷宫中的所有可能的路径（一定长度的移动序列）编码为量子态。然后，通过 Hadamard 门操作，将这些路径以均匀叠加态的形式表示在一个量子寄存器中。这意味着量子系统同时“探索”了所有可能的路径。

2. 适应度评估 (Fitness Evaluation)： 设计一个可逆的量子算子，称为适应度算子 (fitness operator)。这个算子会模拟每一条叠加路径在迷宫中的移动，计算其终点与目标点之间的距离（或接近程度），并将这个“适应度”值存储在一个辅助量子寄存器中。适应度值越高，表示路径越接近目标。

3. 神谕标记 (Oracle Marking)： 构建一个 Grover 兼容的神谕 (oracle)。这个神谕根据一个预设的截止值 (cutoff)，识别并标记那些适应度高于该截止值的路径。标记的方式是给这些“高适应度”的量子态施加一个负相位。

4. 振幅放大 (Amplitude Amplification)： 利用 Grover 算法的迭代过程（包括神谕操作和扩散算子）来反复地放大那些被标记的（高适应度）路径的振幅，同时减小未标记路径的振幅。经过足够多次迭代后，高适应度路径被测量的概率会大大提高。

5. 自适应截止策略 (Adaptive Cutoff Strategy)： 为了处理初始时最佳路径适应度未知，以及可能存在多个接近最优解的情况，算法引入了一个自适应截止策略。它在每次 Grover 搜索迭代后，根据测量到的路径的适应度，动态地更新截止值，使其单调递增。这样，算法会逐渐聚焦于越来越优秀的路径，最终收敛到具有最高适应度的最优路径。

   通过这种方式，量子算法能够并行探索所有路径，并有效地“筛选”出最优路径，从而有望比经典算法更快地找到解决方案。

4.2. 迷宫形式化 (Problem Formalization)

4.2.1. 迷宫模型 (Maze Model)

迷宫被建模为一个 $m \times m$ 的完美网格。完美迷宫意味着：

• 可解性： 存在至少一条从唯一的起始单元格 $(i_s, j_s)$ 到目标单元格 $(i_f, j_f)$ 的路径。

• 无环： 迷宫是一个在 $\mathcal{M}$ 上的树 (tree)，即在任意两个可达的单元格之间只有一条简单的路径。

  数学表示： $$\mathcal { M } : = \{ 0 , 1 , \ldots , m - 1 \} \times \{ 0 , 1 , \ldots , m - 1 \}$$ 其中 $m$ 是迷宫的边长。每个单元格 $(i, j) \in \mathcal{M}$ 可能在四个基本方向 $\{N, E, S, W\}$ 中的一个或多个方向上有开放的墙壁。

4.2.2. 路径表示 (Path Representation)

一条长度为 $n$ 的路径被定义为 $n$ 个方向性移动的序列。 $$P = ( d _ { 1 } , d _ { 2 } , \ldots , d _ { n } ) , \quad { \mathrm { w h e r e } } \quad d _ { k } \in \{ N , E , S , W \}$$ 每个方向被编码为2比特二进制字符串：

• $N$ (北) = 00
• $E$ (东) = 01
• $S$ (南) = 10
• $W$ (西) = 11 因此，一条长度为 $n$ 的路径对应一个 2n 比特的字符串，或者等价地，一个 2n 量子比特的量子态： $$| P \rangle = | d _ { 1 } \rangle \otimes | d _ { 2 } \rangle \otimes \dots \otimes | d _ { n } \rangle \in \left( \mathbb { C } ^ { 2 } \right) ^ { \otimes 2 n }$$ 其中，$\mathbb{C}^2$ 是单个量子比特的希尔伯特空间。

4.2.3. 搜索空间 (Search Space)

所有长度为 $n$ 的候选路径的集合 $\mathcal{P}_n$ 为： $$\mathcal { P } _ { n } : = \{ N , E , S , W \} ^ { n } , \quad \mathrm { s o ~ t h a t } \quad | \mathcal { P } _ { n } | = 4 ^ { n }$$ 每个路径 $P \in \mathcal{P}_n$ 都可能在迷宫中从起始单元格进行有效遍历，也可能因为撞墙或超出边界而无效。 为此，定义一个部分过渡函数 (partial transition function) $\delta$，它模拟每次移动： $$\delta \bigl ( ( i , j ) , d \bigr ) = \left\{ \begin{array} { l l } { ( i ^ { \prime } , j ^ { \prime } ) } & { \mathrm { i f ~ m o v e ~ i n ~ } d \mathrm { ~ f r o m ~ } ( i , j ) \mathrm { ~ i s ~ l e g a l } } \\ { \perp } & { \mathrm { i f ~ m o v e ~ h i t s ~ a ~ w a l l ~ o r ~ e x i t s ~ t h e ~ g r i d } } \end{array} \right.$$ 其中 (i, j) 是当前单元格，$d$ 是方向。如果移动合法，则返回新的单元格 (i', j')；否则，返回 $\perp$ (表示无效)。 通过顺序应用 $\delta$，路径 $P = (d_1, \ldots, d_n)$ 会产生一系列位置： $$( i _ { 0 } , j _ { 0 } ) : = ( i _ { s } , j _ { s } ) , \quad ( i _ { k } , j _ { k } ) : = \delta \big ( ( i _ { k - 1 } , j _ { k - 1 } ) , d _ { k } \big )$$ 如果路径在任何一步 $k$ 导致 $(i_k, j_k) = \perp$，则该路径在该点之后被视为无效。

4.2.4. 目标定义 (Goal Definition)

路径 $P$ 的最终位置定义为： $$\mathrm { e n d } ( P ) : = ( i _ { n } , j _ { n } )$$ 如果 $\delta$ 在第 $k < n$ 步失败，则 $\operatorname{end}(P)$ 是 $\perp$ 之前的最后一个有效单元格。 优化目标是找到一个路径 $P^\star \in \mathcal{P}_n$ 使得：

1. 精确到达目标：$\operatorname{end}(P^\star) = (i_f, j_f)$，或者
2. 最小化与目标的已知度量（例如，曼哈顿距离）： $$P ^ { \star } : = \arg \operatorname* { m i n } _ { P \in \mathcal { P } _ { n } } \operatorname { d i s t } ( \operatorname { e n d } ( P ) , ( i _ { f } , j _ { f } ) )$$ 这个度量在适应度函数中被形式化，本文使用的是平方欧几里得距离。

4.2.5. 路径长度参数 (Path Length Parameter)

路径长度 $n$ 的选择至关重要：

• 如果 $n < \operatorname{length}(P^\star)$ (真实最短路径长度)，则解空间中不包含真正的最短路径。
• 如果 $n > \operatorname{length}(P^\star)$，则解空间包含冗余或无效的路径。 本文假设 $n \ge \ell_{\mathrm{min}}$，其中 $\ell_{\mathrm{min}}$ 是从 $(i_s, j_s)$ 到 $(i_f, j_f)$ 的唯一路径长度。这个值可以通过启发式方法设置，或者在迭代过程中进行调整。由于迷宫是无环的，它为基于树的迷宫表示引入了一个生成树 (spanning tree)，因此所有有效路径对应于此树中的根到叶路径，这有利于在经典或量子搜索中进行剪枝 (pruning)。

4.3. 量子编码与叠加 (Quantum Encoding and Superposition)

4.3.1. 二进制编码映射 (Binary Encoding Map)

路径 $P = (d_1, d_2, \ldots, d_n)$ 是 $n$ 个移动序列，其中每个 $d_k \in \{N, E, S, W\}$。定义一个二进制编码映射： $$\begin{array}{c} \chi : \{ N , E , S , W \} \to \{ 0 , 1 \} ^ { 2 } \quad \mathrm { s u c h ~ t h a t } \quad \chi ( N ) = 00 , \quad \chi ( E ) = 0 1 , \\ \chi ( S ) = 10 , \quad \chi ( W ) = 11 \end{array}$$ 然后，路径 $P \in \mathcal{P}_n$ 被映射到一个 2n 比特的二进制字符串： $$\chi ( P ) = \chi ( d _ { 1 } ) \parallel \chi ( d _ { 2 } ) \parallel \cdots \parallel \chi ( d _ { n } ) \in \{ 0 , 1 \} ^ { 2 n }$$ 其中 $\parallel$ 表示字符串拼接。

4.3.2. 量子寄存器表示 (Quantum Register Representation)

每个比特与一个量子比特相关联，完整的量子寄存器存在于希尔伯特空间 (Hilbert space)： $$\mathcal { H } : = \left( \mathbb { C } ^ { 2 } \right) ^ { \otimes 2 n } , \quad \mathrm { d i m } \mathcal { H } = 2 ^ { 2 n }$$ 对于每个路径 $P \in \mathcal{P}_n$，定义： $$| P \rangle : = | \chi ( P ) \rangle \in \mathcal { H }$$ 例如，如果 $P = (N, E, S)$，则： $$\left| P \right. = \left| 0 0 0 1 1 0 \right. = \left| 0 \right. \otimes \left| 0 \right. \otimes \left| 0 \right. \otimes \left| 1 \right. \otimes \left| 1 \right. \otimes \left| 0 \right.$$

4.3.3. 路径的均匀叠加 (Uniform Superposition Over Paths)

目标是构建一个均匀叠加态，其中包含所有可能的路径： $$| \Omega \rangle : = \frac { 1 } { \sqrt { | \mathcal { P } _ { n } | } } \sum _ { P \in \mathcal { P } _ { n } } | P \rangle = \frac { 1 } { 2 ^ { n } } \sum _ { P \in \mathcal { P } _ { n } } | \chi ( P ) \rangle$$ 这是对所有长度为 $n$ 的编码方向序列的均匀叠加。

4.3.4. Hadamard 制备与编码有效性 (Hadamard Preparation and Encoding Validity)

如果直接对 2n 个初始为 $|0\rangle$ 的量子比特应用 Hadamard 门 $H^{\otimes 2n}$： $$H ^ { \otimes 2 n } \left| 0 \right. ^ { \otimes 2 n } = { \frac { 1 } { \sqrt { 2 ^ { 2 n } } } } \sum _ { z \in \{ 0 , 1 \} ^ { 2 n } } \left| z \right.$$ 这将产生一个对所有长度为 2n 的二进制字符串的均匀叠加。然而，并非所有这样的字符串都对应于有效的方向序列（例如，01 后面跟着 10 是有效的，但 0011 对应 N, W）。实际上，有效的编码子集 $S = \chi(\mathcal{P}_n) \subset \{0, 1\}^{2n}$ 的大小恰好是 $|S| = 4^n$，对应于每对相邻比特编码一个方向的字符串。

为了将均匀叠加限制在有效的编码上，需要将量子比特分组为 $n$ 对： $${ \mathcal { H } } = \bigotimes _ { k = 1 } ^ { n } { \mathcal { H } } _ { k } , \quad { \mathrm { w h e r e ~ } } { \mathcal { H } } _ { k } : = \mathbb { C } ^ { 2 } \otimes \mathbb { C } ^ { 2 }$$ 对每个初始为 $|00\rangle$ 的2量子比特块应用 $H^{\otimes 2}$： $$H ^ { \otimes 2 } \left| 0 0 \right. = \frac { 1 } { 2 } \sum _ { b \in \{ 0 , 1 \} ^ { 2 } } \left| b \right.$$ 这将产生对四个有效方向编码的均匀叠加：$|00\rangle, |01\rangle, |10\rangle, |11\rangle$。 然后，整个状态变为： $$| \Omega \rangle = \bigotimes _ { k = 1 } ^ { n } \left( { \frac { 1 } { 2 } } \sum _ { b _ { k } \in \{ 0 , 1 \} ^ { 2 } } | b _ { k } \rangle \right) = { \frac { 1 } { 2 ^ { n } } } \sum _ { P \in { \mathcal { P } } _ { n } } | \chi ( P ) \rangle$$

4.3.5. 定理1 (Theorem 1: Superposition Correctness)

定理： 令 $n \in \mathbb{N}$。令 $\mathcal{P}_n = \{N, E, S, W\}^n$ 为所有长度为 $n$ 的方向序列的集合，并如上定义编码映射 $\chi : \mathcal{P}_n \to \{0, 1\}^{2n}$。令 $| \Omega \rangle \in (\mathbb{C}^2)^{\otimes 2n}$ 为由 $\vert \Omega \rangle : = \bigotimes _ { k = 1 } ^ { n } \left( H ^ { \otimes 2 } \left. 0 0 \right. \right)$ 定义的量子态。 则： $$| \Omega \rangle = \frac { 1 } { 2 ^ { n } } \sum _ { P \in \mathcal { P } _ { n } } | \chi ( P ) \rangle$$ 也就是说，$\vert \Omega \rangle$ 是对所有长度为 $n$ 的有效方向序列的均匀叠加。 证明： 令 $\mathcal{H} := (\mathbb{C}^2)^{\otimes 2n}$。希尔伯特空间可以分解为 $n$ 个2量子比特子系统的张量积： $${ \mathcal { H } } = \bigotimes _ { k = 1 } ^ { n } { \mathcal { H } } _ { k } , \quad { \mathrm { w h e r e ~ } } { \mathcal { H } } _ { k } = \mathbb { C } ^ { 2 } \otimes \mathbb { C } ^ { 2 }$$ 每个2量子比特子系统 $\mathcal{H}_k$ 将通过单射映射 $\chi$ 编码一个方向 $d_k \in \{N, E, S, W\}$。 现在，对每个初始为 $|00\rangle$ 的量子比特对应用 $H^{\otimes 2}$： $$H ^ { \otimes 2 } | 0 0 \rangle = \frac { 1 } { 2 } \sum _ { b \in \{ 0 , 1 \} ^ { 2 } } | b \rangle = \frac { 1 } { 2 } ( | 0 0 \rangle + | 0 1 \rangle + | 1 0 \rangle + | 1 1 \rangle )$$ 这形成了对四个有效方向编码的均匀叠加。由于所有 $n$ 个方向编码是独立的，我们取它们的张量积： $${ \begin{array} { r l } & { | \Omega \rangle = \bigotimes _ { k = 1 } ^ { n } \left( { \frac { 1 } { 2 } } \sum _ { b _ { k } \in \{ 0 , 1 \} ^ { 2 } } | b _ { k } \rangle \right) } \\ & { \qquad = { \frac { 1 } { 2 ^ { n } } } \displaystyle \sum _ { ( b _ { 1 } , \ldots , b _ { n } ) \in ( \{ 0 , 1 \} ^ { 2 } ) ^ { n } } | b _ { 1 } \rangle | b _ { 2 } \rangle \cdots | b _ { n } \rangle } \end{array} }$$ 根据 $\chi$ 的定义，每个串联字符串 $b_1 \parallel \dots \parallel b_n \in \{0, 1\}^{2n}$ 都等于某个 $P \in \mathcal{P}_n$ 的 $\chi(P)$。因此，求和遍历了所有这样的编码： $$| \Omega \rangle = \frac { 1 } { 2 ^ { n } } \sum _ { P \in \mathcal { P } _ { n } } | \chi ( P ) \rangle$$ 证毕。

4.4. 适应度算子构建 (Fitness Operator Construction)

适应度函数评估给定路径 $P \in \mathcal{P}_n$ 从起始单元格 $(i_s, j_s)$ 到目标单元格 $(i_f, j_f)$ 的终点与目标点的接近程度。 适应度函数使用平方欧几里得距离 (squared Euclidean distance)： $$\operatorname { f u n e s s } ( P ) = C - \left[ ( i _ { \mathrm { e n d } } - i _ { f } ) ^ { 2 } + ( j _ { \mathrm { e n d } } - j _ { f } ) ^ { 2 } \right]$$ 其中：

• $C = 2^r$ 是一个常数，且 $C \ge 2(m-1)^2$。这个常数确保适应度值始终为非负数，并在路径到达目标时达到最大值。
• $(i_{\mathrm{end}}, j_{\mathrm{end}})$ 是路径 $P$ 的最终单元格。
• $r \in \mathbb{N}$ 是存储适应度值所需的量子比特数量。$r = \lceil \log_2 C \rceil$。

4.4.1. 定义1 (Definition 1: Fitness Operator)

令 $|x\rangle$ 为编码路径 $P \in \mathcal{P}_n$ 的量子寄存器，令 $|0\rangle_f$ 为一个包含 $r$ 个量子比特的辅助适应度寄存器，其初始值为 $|0\rangle$。适应度算子是一个酉变换： $$F : | x \rangle | 0 \rangle _ { f } \mapsto | x \rangle | { \hbar t n e s s ( x ) } \rangle$$ 其中，fitness(x) 是通过可逆模拟由 $|x\rangle$ 定义的路径计算出的适应度值，并存储在 $|f\rangle$ 中。

4.4.2. 量子电路实现 (Quantum Circuit Implementation)

适应度算子 $F$ 的电路实现涉及以下寄存器配置：

• $|x\rangle$: 2n 量子比特的路径寄存器。

• $|i\rangle, |j\rangle$: 位置寄存器，每个包含 $\lceil \log_2 m \rceil$ 个量子比特，用于存储当前单元格的坐标。

• $|d\rangle$: 距离寄存器，用于存储平方欧几里得距离。

• $|f\rangle$: 适应度寄存器，包含 $r = \lceil \log_2 C \rceil$ 个量子比特。

• Ancillae (辅助量子比特)：用于中间计算（如减法、平方、清理）的临时寄存器。

  $F$ 的电路由以下阶段组成：

1. 路径模拟 (Path Simulation)： 对于 $k = 1$ 到 $n$ 的每个步骤，提取 $|x\rangle$ 中的 2 量子比特切片 $|d_k\rangle$（代表第 $k$ 次移动的方向），并应用方向控制的更新操作： $$\delta ( i , j ; d _ { k } ) : = \left\{ \begin{array} { l l } { i \mapsto i - 1 } & { \mathrm { i f ~ } d _ { k } = 0 0 \quad (N) } \\ { j \mapsto j + 1 } & { \mathrm { i f ~ } d _ { k } = 0 1 \quad (E) } \\ { i \mapsto i + 1 } & { \mathrm { i f ~ } d _ { k } = 1 0 \quad (S) } \\ { j \mapsto j - 1 } & { \mathrm { i f ~ } d _ { k } = 1 1 \quad (W) } \end{array} \right.$$ 每次更新都通过多控加/减电路 (multi-controlled add/subtract circuits) 实现，使用 Toffoli 门和 CNOT 门。这些操作是完全可逆的。

2. 距离计算 (Distance Computation)： 设最终位置为 (i, j)。平方欧几里得距离为 $d = (i - i_f)^2 + (j - j_f)^2$。 首先使用量子减法器计算： $$| d _ { i } \rangle : = | i - i _ { f } \rangle , \quad | d _ { j } \rangle : = | j - j _ { f } \rangle$$ 然后应用可逆平方电路（例如，基于 Toffoli 门的乘法器）： $$| d _ { i } ^ { 2 } \rangle , | d _ { j } ^ { 2 } \rangle \Rightarrow | d \rangle = | d _ { i } ^ { 2 } + d _ { j } ^ { 2 } \rangle$$

3. 适应度计算 (Fitness Calculation)： 使用可逆减法器计算： $| f \rangle = | C - d \rangle$ 常数 $C = 2^r$ 作为固定二进制输入嵌入到算术电路中。结果写入 $|f\rangle$ 寄存器。

4. 反计算 (Uncomputation)： 所有用于中间减法和平方的辅助寄存器通过反转先前的操作进行反计算 (uncomputation)。这使得最终状态为 $\left| x \right. \left| f \right.$，确保了操作符的可逆性，并为集成到更大的 Grover 型量子电路做好准备。

4.4.3. 定理2 (Theorem 2: Fitness Operator is Unitary)

定理： 上述定义的适应度算子 $F$ 在路径寄存器和适应度寄存器的联合空间上是酉的 (unitary)。 $F ^ { \dagger } F = I$ 证明： 算子 $F$ 由以下可逆组件组成：

• 路径模拟： 由路径数据控制的坐标更新。
• 距离计算： 对位置差值进行可逆算术运算。
• 适应度评估： 从一个固定的2的幂常数中减去距离。
• 反计算： 反转辅助量子比特内部操作。 每个组件都只使用由 Toffoli、CNOT 和其他 Clifford+T 门组成的酉子电路。由于整体变换是酉操作的组合，因此我们得出 $F$ 是酉的。

4.4.4. 工作示例 (Worked Example)

假设迷宫大小 $m=2$，路径长度 $n=2$。

• 起始单元格：$(i_s, j_s) = (0, 0)$
• 目标单元格：$(i_f, j_f) = (1, 1)$
• 给定路径量子态：$|x\rangle = |1001\rangle$ 解码：10 对应 $S$ (南)，01 对应 $E$ (东)。 路径为 (S, E)。 最终单元格： $$(0, 0) \stackrel{S}{\longrightarrow} (1, 0) \stackrel{E}{\longrightarrow} (1, 1) \Rightarrow \text{distance} = 0$$ 设常数 $C = 2^2 = 4$。 则适应度为： $$\text{fitness} = C - 0 = 4 - 0 = 4 \quad \Rightarrow \quad |f\rangle = |100\rangle$$ 电路会将这个输出与 $|x\rangle$ 纠缠，并且所有辅助量子比特通过反计算重置为零。

4.5. 神谕设计 (Oracle Design)

神谕算子 (oracle operator) $O$ 通过对那些适应度超过某个经典或量子阈值（称为截止值 cutoff）的量子态应用相位翻转，来选择性地标记高适应度路径。它通过将搜索谓词 (search predicate) 编码到量子相位中，从而实现 Grover 式的振幅放大。 令 cutoff $\in \mathbb{N}$ 表示阈值。神谕作用于适应度寄存器 $|f_x\rangle$（大小为 $m_f$ 量子比特）如下： $$O : \left| x \right. \left| f _ { x } \right. \mapsto ( - 1 ) ^ { g ( f _ { x } ) } \left| x \right. \left| f _ { x } \right. ,$$ 其中，函数 $g(f_x)$ 定义为： $$g ( f _ { x } ) = { \left\{ \begin{array} { l l } { 1 } & { { \mathrm { i f ~ } } f _ { x } > \mathrm { c u t o f f } } \\ { 0 } & { { \mathrm { o t h e r w i s e . } } } \end{array} \right. }$$ 这意味着只有当路径的适应度 $f_x$ 大于 cutoff 时，对应的量子态才会获得一个负相位。

4.5.1. 截止值编码 (Encoding the Cutoff)

神谕支持两种场景：

1. 经典截止值 (Classical cutoff)： cutoff 是一个固定的经典常数，硬编码到比较器电路中。
2. 量子截止值寄存器 (Quantum cutoff register)： $|c\rangle$ 存储动态阈值，允许自适应或迭代方案。 两种版本都可以通过可逆比较器 (reversible comparator) 处理，它比较 $|f_x\rangle$ 与经典常数或量子寄存器 $|c\rangle$。

4.5.2. 神谕电路构建 (Oracle Circuit Construction)

神谕通过三个可逆阶段进行：

1. 比较器阶段 (Comparator Stage)： $$\left| f _ { x } \right. \left| 0 \right. _ { b } \mapsto \left| f _ { x } \right. \left| b \right. ,$$ 其中 $|b\rangle = 1$ 当且仅当 $f_x > \text{cutoff}$。这使用了一个可逆的“大于”比较器电路 (reversible greater-than comparator circuit)，通过带有进位逻辑的比特减法构建。

2. 相位翻转阶段 (Phase Flip Stage)： 应用一个受控-Z (Controlled-Z, CZ) 门： $$\left| x \right. \left| f _ { x } \right. \left| 1 \right. _ { b } \mapsto - \left| x \right. \left| f _ { x } \right. \left| 1 \right. _ { b } .$$ 这只对“标记”态（即 $|b\rangle = 1$ 的态）施加相位翻转。实际上，$\text{CZ}$ 门除了在 $|1\rangle_b$ 子空间外，对所有其他子空间都表现为恒等操作。

3. 反计算阶段 (Uncomputation Stage)： 反转比较器逻辑以清理辅助量子比特： $$\left| f _ { x } \right. \left| b \right. \mapsto \left| f _ { x } \right. \left| 0 \right. ,$$ 这保持了可逆性并恢复了辅助量子比特的工作空间。

4.5.3. 大于比较器电路 (Greater-Than Comparator Circuit)

令 $|f_x\rangle = f_0 f_1 \ldots f_{m-1}$ (表示适应度值) 和 $\text{cutoff} = c_0 c_1 \ldots c_{m-1}$ (表示截止值)。 要检查 $f > c$，我们实际上是检查 $f - c > 0$，这意味着 $f - c$ 的最高有效位 (MSB) 为 0 (如果使用补码表示负数) 或特定位模式。 本文通过可逆减法器电路实现，例如 Cuccaro 的波纹进位减法器 (ripple-carry subtractor)。 $$\left| f \right. \left| c \right. \left| 0 \right. _ { b } \mapsto \left| f \right. \left| c \right. \left| f - c \right. { \xrightarrow { { \mathrm { M S B - c h e c k } } } } \left| f \right. \left| c \right. \left| b \right. .$$ 这个电路由以下部分组成：

• $m$ 个受控非门 (controlled-NOT, CNOT) 和 Toffoli 门用于位差计算。
• 一个进位超前 (carry-lookahead) 或波纹进位网络用于减法。
• 一个使用1个辅助量子比特的 MSB 提取逻辑。 所有门都是可逆的，并且只使用 Clifford+Toffoli 操作。

4.5.4. 酉性证明 (Unitarity Proof)

神谕的每个阶段都是酉的：

• 比较器是一个可逆函数 $C$，所以 $C^\dagger = C^{-1}$ 存在。
• 相位翻转是一个对角酉算子，$Z = \text{diag}(1, -1)$。
• 整个神谕 ${ \cal O } = { \cal C } ^ { \dagger } \cdot { \cal Z } \cdot { \cal C }$ 是酉操作的组合，因此 $O$ 是酉的。

4.5.5. 量子资源成本 (Quantum Resource Cost)

令 $m$ 为 $|f_x\rangle$ 中的量子比特数。

• 比较器成本：$O(m)$ 个 Toffoli 门，$O(m)$ 个辅助量子比特用于进位（可以重用）。
• 相位翻转：1个 CZ 门。
• 总深度：$O(m)$ (减法) + $O(m)$ (反计算)。
• 总宽度：$m$ (用于 $|f_x\rangle$)，1 (用于标志位)，$\sim m$ (辅助量子比特)。 可以通过 Bennett 式的垃圾清理 (garbage cleanup) 或辅助量子比特重用来进一步降低成本。

4.5.6. 布尔逻辑定义 (Boolean Logic Definition)

令适应度寄存器 $|f_x\rangle$ 包含 $m$ 个量子比特，表示一个无符号整数 $a = a_{m-1} a_{m-2} \dots a_0$。 令截止值 $c = c_{m-1} c_{m-2} \ldots c_0$ 可以是经典值或存储在量子寄存器中。 输出比特 $b$ 被定义为： $$\operatorname { G T } ( a , c ) = \bigcup _ { i = 0 } ^ { m - 1 } [ a _ { i } \wedge \neg c _ { i } \wedge \bigwedge _ { j = i + 1 } ^ { m - 1 } ( a _ { j } \oplus c _ { j } ) ]$$ 其中：

• $\bigcup$ 表示逻辑或 (OR)。
• $\wedge$ 表示逻辑与 (AND)。
• $\neg$ 表示逻辑非 (NOT)。
• $\oplus$ 表示逻辑异或 (XOR)。 这个逻辑返回 $b=1$ 当且仅当无符号整数 $a$ 大于 $c$。

4.5.7. 电路实现 (Circuit Realization)

上述布尔逻辑可以转换为可逆电路，使用：

• CNOT 门计算异或 $a_j \oplus c_j$。
• Toffoli 门计算受控合取 (controlled conjunctions)。
• 一个输出辅助量子比特 $|b\rangle$ 存储最终结果。 总体深度为 $O(m)$，宽度为 $O(m)$ 个辅助量子比特（可重用）。 证明： 令 $a, c \in \{0, 1\}^m$ 被解释为无符号二进制整数。目标是证明 $\operatorname{GT}(a, c) = 1$ 当且仅当 $a > c$。 从最高有效位 (MSB) 到最低有效位 (LSB) 逐位比较 $a$ 和 $c$。结果由第一个 $a_i \neq c_i$ 的位置 $i$ 决定：
• 如果 $a_i = 1$ 且 $c_i = 0$，则 $a > c$。
• 如果 $a_i = 0$ 且 $c_i = 1$，则 $a < c$。
• 如果 $a_i = c_i$，则继续检查下一个低位。 布尔公式 $\operatorname{GT}(a, c) = \bigcup _ { i = 0 } ^ { m - 1 } [ a _ { i } \wedge \neg c _ { i } \wedge \bigwedge _ { j = i + 1 } ^ { m - 1 } ( a _ { j } \oplus c _ { j } ) ]$ 明确编码了这个逻辑。对于特定的 $i$，如果满足以下条件，它将对 OR 表达式做出贡献：
• 所有更重要的位 ($j > i$) 都匹配：$a_j = c_j$。
• 在位 $i$ 处，$a_i = 1, c_i = 0$。 因此，OR 表达式当且仅当 $a$ 和 $c$ 之间最高有效差异是 $a_i=1, c_i=0$ 时才为真，这意味着 $a>c$。 由于该布尔公式中的每个操作在使用标准量子逻辑门（CNOT 和 Toffoli）实现时都是可逆的，因此比较器电路保持酉性并可以被干净地反计算。

4.6. Grover 迭代与振幅放大 (Grover Iteration and Amplitude Amplification)

4.6.1. Grover 几何与振幅动力学 (Grover Geometry and Amplitude Dynamics)

令 $N = 4^n$ 为长度为 $n$ 的编码迷宫路径的总数。 令 $\mathcal{H} = \operatorname{span}\{|x\rangle : x \in \mathcal{P}_n\}$ 表示路径态的希尔伯特空间。 令 $M \subseteq \mathcal{P}_n$ 为标记态集合（适应度 $f(x) > \text{cutoff}$ 的路径），且 $k = |M|$。 定义： $$| \Omega \rangle : = { \frac { 1 } { \sqrt { N } } } \sum _ { x \in \mathcal { P } _ { n } } | x \rangle \quad { \mathrm { ( u n i f o r m ~ s u p e r p o s i t i o n ) } }$$ 这是所有路径的均匀叠加态。 定义标记态子空间和未标记态子空间的归一化投影： $$| \psi _ { T } \rangle : = \frac { 1 } { \sqrt { k } } \sum _ { x \in \cal { M } } | x \rangle , \quad | \psi _ { \bot } \rangle : = \frac { 1 } { \sqrt { N - k } } \sum _ { x \notin \cal { M } } | x \rangle$$

4.6.2. 引理1 (Lemma 1: 2D Subspace Orthonormal Basis)

引理： 态 $\{|\psi_T\rangle, |\psi_\bot\rangle\}$ 构成了包含所有 Grover 动力学的二维子空间 $\mathcal{H}_G \subset \mathcal{H}$ 的正交基。 证明： 通过构造，可见 $|\psi_T\rangle$ 和 $|\psi_\bot\rangle$ 都是归一化的。它们的内积为： $$\langle \psi _ { T } | \psi _ { \bot } \rangle = \frac { 1 } { \sqrt { k ( N - k ) } } \sum _ { x \in M } \sum _ { y \notin M } \langle x | y \rangle = 0$$ 因为对于 $x \neq y$，$\langle x|y \rangle = 0$，并且 $M \cap (\mathcal{P}_n \setminus M) = \emptyset$。因此，正交性成立。

4.6.3. 引理2 (Lemma 2: Initial State Decomposition)

引理： 初始态 $|\Omega\rangle$ 可以分解为： $$\left| \Omega \right. = \sin ( \theta ) \left| \psi _ { T } \right. + \cos ( \theta ) \left| \psi _ { \perp } \right. , \quad \theta : = \arcsin \left( \sqrt { \frac { k } { N } } \right)$$ 证明： 我们计算 $|\Omega\rangle$ 在 $|\psi_T\rangle$ 上的投影： $$\langle \psi _ { T } | \Omega \rangle = { \frac { 1 } { \sqrt { N } } } \cdot { \frac { 1 } { \sqrt { k } } } \sum _ { x \in M } 1 = { \frac { \sqrt { k } } { \sqrt { N } } } = \sin ( \theta )$$ 根据正交性，在 $|\psi_\bot\rangle$ 上的投影为： $$\langle \psi _ { \bot } | \Omega \rangle = \sqrt { 1 - \sin ^ { 2 } ( \theta ) } = \cos ( \theta )$$ 因此： $$\left| \Omega \right. = \sin ( \theta ) \left| \psi _ { T } \right. + \cos ( \theta ) \left| \psi _ { \perp } \right.$$ 证毕。

4.6.4. 神谕操作符 (Oracle Operator)

神谕算子 $O$ 将标记态的相位翻转： $$O : = I - 2 \Pi _ { T } \quad { \mathrm { w h e r e } } \quad \Pi _ { T } = \sum _ { x \in M } \left| x \right. \left. x \right|$$ 其中 $\Pi_T$ 是投影到标记子空间的投影算子。 它的作用是： $$O \left| x \right. = { \left\{ \begin{array} { l l } { - \left| x \right. } & { { \mathrm { i f ~ } } x \in { \mathcal { M } } } \\ { \left| x \right. } & { { \mathrm { o t h e r w i s e } } } \end{array} \right. }$$

4.6.5. 扩散算子 (Diffuser Operator)

扩散算子 $D$ 是关于均匀叠加态 $|\Omega\rangle$ 的反射： $$D : = 2 \left| \Omega \right. \left. \Omega \right| - I .$$

4.6.6. 定理 (Theorem: Grover Operator as Rotation)

定理： 复合的 Grover 算子 $G := D \cdot O$ 在由 $\{|\psi_T\rangle, |\psi_\bot\rangle\}$ 张成的平面内执行一个角度为 $2\theta$ 的旋转。 证明： 令初始状态为 $|\psi_0\rangle = |\Omega\rangle = \sin(\theta)|\psi_T\rangle + \cos(\theta)|\psi_\bot\rangle$。 首先应用神谕 $O$： $$O \left| \psi _ { 0 } \right. = O \left( \sin \theta \left| \psi _ { T } \right. + \cos \theta \left| \psi _ { \perp } \right. \right) = - \sin \theta \left| \psi _ { T } \right. + \cos \theta \left| \psi _ { \perp } \right. .$$ 然后应用扩散算子 $D = 2|\psi_0\rangle\langle\psi_0| - I$： $$\begin{array} { r l r } { G | \psi _ { 0 } = D O | \psi _ { 0 } } & { { } } & { { } } \\ { } & { { } } & { = ( 2 | \psi _ { 0 } \psi _ { 0 } | - I ) ( - \sin \theta | \psi _ { T } + \cos \theta | \psi _ { \perp } ) . } \end{array}$$ 代入 $|\psi_0\rangle = \sin(\theta)|\psi_T\rangle + \cos(\theta)|\psi_\bot\rangle$： $$\begin{array} { c } { { G \left. \psi _ { 0 } \right. = - \sin \theta \left. \psi _ { T } \right. + \cos \theta \left. \psi _ { \perp } \right. } } \\ { { { } } } \\ { { + 2 \left( \sin \theta \left. \psi _ { T } \right. + \cos \theta \left. \psi _ { \perp } \right. \right) \cdot \left( - \sin ^ { 2 } \theta + \cos ^ { 2 } \theta \right) . } } \end{array}$$ (此处原文中间简化步骤有误，直接跳到了结果。根据 Grover 算法的标准推导，结果应是) $$G \left| \psi _ { 0 } \right. = \sin ( 3 \theta ) \left| \psi _ { T } \right. + \cos ( 3 \theta ) \left| \psi _ { \perp } \right. .$$ (这里是论文原文的最终结果，但需要注意的是，通常 Grover 迭代一次是将角度从 $\theta$ 变为 $3\theta$。所以 $G^r$ 会是 $(2r+1)\theta$。如果将初始状态看作与 $\left| \psi _ { \perp } \right.$ 夹角为 $\theta$，那么 $G$ 的作用是反射两次，总旋转 $2\theta$。因此，经过 $r$ 次迭代后，总旋转角度是 $2r\theta$，所以与 $\left| \psi _ { \perp } \right.$ 的夹角变为 $(2r+1)\theta$) 因此，每次应用 $G$ 都会将状态在二维子空间中旋转 $2\theta$ 角。所以，经过 $r$ 次 Grover 迭代后： $$G ^ { r } \left| \psi _ { 0 } \right. = \sin ( ( 2 r + 1 ) \theta ) \left| \psi _ { T } \right. + \cos ( ( 2 r + 1 ) \theta ) \left| \psi _ { \perp } \right. .$$ 测量到标记态的概率为： $$P _ { \mathrm { s u c c e s s } } = \sin ^ { 2 } \left( ( 2 r + 1 ) \theta \right) .$$

4.6.7. 推论1 (Corollary 1: Optimal Iteration Count)

推论： 当 $(2r+1)\theta \approx \frac{\pi}{2}$ 时，成功概率达到最大值。因此，最佳迭代次数为： $$r ^ { \star } = \left\lfloor { \frac { \pi } { 4 \theta } } - { \frac { 1 } { 2 } } \right\rfloor$$ 其中 $\theta = \arcsin \left( { \sqrt { \frac { k } { N } } } \right)$。这使得 $P_{\mathrm{success}} \approx 1$。

4.6.8. 子空间分解 (Subspace Decomposition)

令 $\mathcal{M} \subset \mathcal{P}_n$ 表示标记解的集合，其大小为 $|\mathcal{M}| = k$。 定义两个正交向量： $$\begin{array} { l } { \displaystyle | \Psi _ { T } \rangle = \displaystyle \frac { 1 } { \sqrt { k } } \sum _ { x \in \mathcal { M } } | x \rangle \quad \mathrm { ( t a r g e t ~ s u b s p a c e ) } } \\ { \displaystyle | \Psi _ { \perp } \rangle = \displaystyle \frac { 1 } { \sqrt { N - k } } \sum _ { x \notin \mathcal { M } } | x \rangle \quad \mathrm { ( u n m a r k e d ~ s u b s p a c e ) } } \end{array}$$ 则初始状态 $| \Psi \rangle$（即 $| \Omega \rangle$）分解为： $$\begin{array} { r } { | \Psi \rangle = \sqrt { \frac { k } { N } } \left| \Psi _ { T } \right. + \sqrt { 1 - \frac { k } { N } } \left| \Psi _ { \bot } \right. = \sin ( \theta ) \left| \Psi _ { T } \right. } \\ { + \cos ( \theta ) \left| \Psi _ { \bot } \right. } \end{array}$$ 其中 $\theta = \arcsin \left( { \sqrt { \frac { k } { N } } } \right)$ 是 $| \Psi \rangle$ 与未标记子空间之间的初始角度。

4.6.9. Grover 旋转作为反射组合 (Grover Rotation as Reflection Composition)

神谕 $O$ 对 $|\Psi_T\rangle$ 进行反射： $O = I - 2 \Pi _ { T }$ 其中 $\Pi_T = |\Psi_T\rangle\langle\Psi_T|$。 扩散算子 $D$ 对 $|\Psi\rangle$ 进行反射： $$D = 2 \left| \Psi \right. \left. \Psi \right| - I$$ 因此，$G = D \cdot O$ 在由 $(|\Psi_T\rangle, |\Psi_\perp\rangle)$ 张成的平面内执行一个角度为 $2\theta$ 的旋转。 证明： 考虑 $G$ 对初始态 $|\Psi\rangle$ 的作用。写作： $$\left| \Psi \right. = \cos ( \theta ) \left| \Psi _ { \perp } \right. + \sin ( \theta ) \left| \Psi _ { T } \right.$$ 应用 $O$： $$O \left| \Psi \right. = \cos ( \theta ) \left| \Psi _ { \perp } \right. - \sin ( \theta ) \left| \Psi _ { T } \right.$$ 应用 $D$： $$G \left| \Psi \right. = D ( O \left| \Psi \right. ) = ( 2 \left| \Psi \right. \left. \Psi \right| - I ) ( \cos \theta \left| \Psi _ { \bot } \right. - \sin \theta \left| \Psi _ { T } \right. )$$ 由于 $|\Psi\rangle$ 位于由 $|\Psi_T\rangle, |\Psi_\perp\rangle$ 张成的平面中，算子 $G$ 作用为一个平面内逆时针旋转 $2\theta$ 角。 即： $$G \left| \Psi \right. = \cos ( 3 \theta ) \left| \Psi _ { \perp } \right. + \sin ( 3 \theta ) \left| \Psi _ { T } \right.$$ 通过归纳法，经过 $r$ 次应用： $$G ^ { r } \left| \Psi \right. = \cos ( ( 2 r + 1 ) \theta ) \left| \Psi _ { \perp } \right. + \sin ( ( 2 r + 1 ) \theta ) \left| \Psi _ { T } \right.$$

4.6.10. 成功概率 (Success Probability)

令 $\mathcal{M}$ 为标记态的集合。经过 $r$ 次 Grover 迭代后测量到标记态的概率为： $$P _ { \mathrm { s u c c e s s } } ( r ) = | \langle \Psi _ { T } | G ^ { r } | \Psi \rangle | ^ { 2 } = \sin ^ { 2 } ( ( 2 r + 1 ) \theta )$$ 为了最大化 $P_{\mathrm{success}}$，我们选择 $r$ 为最接近以下整数的值： $$r ^ { \star } = \left\lfloor { \frac { \pi } { 4 \theta } } - { \frac { 1 } { 2 } } \right\rfloor \quad { \mathrm { w h e r e } } \quad \theta = \arcsin \left( { \sqrt { \frac { k } { N } } } \right)$$ 这在 $(2r+1)\theta \approx \frac{\pi}{2}$ 时实现 $P_{\mathrm{success}} \approx 1$。

4.6.11. $G$ 的谱分解 (Spectral Decomposition of G)

令 $G$ 作用在二维不变子空间 $\mathcal{H}_2 = \operatorname{span}(|\Psi_T\rangle, |\Psi_\perp\rangle)$ 上。它的作用可以完全描述为： $$G | _ { \mathcal { H } _ { 2 } } = \left[ \begin{array} { c c } { \cos ( 2 \theta ) } & { - \sin ( 2 \theta ) } \\ { \sin ( 2 \theta ) } & { \cos ( 2 \theta ) } \end{array} \right]$$ 其特征值为 $e^{\pm i 2\theta}$，并有相应的特征向量。重复应用 $G$ 会使状态向量平滑地向 $|\Psi_T\rangle$ 旋转，增加与标记解的重叠。

4.7. 单调截止值更新保证收敛 (Monotonic Cutoff Update Guarantees Convergence)

算法运行 $T$ 次迭代。在每次迭代 $t \in \{1, \ldots, T\}$ 中，算法观察到一个适应度值 $f_t^*$ 并更新一个经典的阈值或截止值 $C_t$。 定义截止值更新规则为：

4.7.1. 定义2 (Definition 2: Monotonic Cutoff Policy)

令 $C_1 \in \mathbb{N}$ 为初始截止值。则定义： $$C _ { t + 1 } : = \operatorname* { m a x } ( C _ { t } , f _ { t } ^ { * } ) , \quad \mathrm { for } \quad t = 1 , \ldots , T - 1$$ 其中 $f_t^*$ 是在第 $t$ 次迭代中观察到的适应度值。 令 $f_{\mathrm{max}} := \max_{x \in \mathcal{P}_n} f(x)$ 为可能的最大适应度（由最优路径实现）。

4.7.2. 引理1 (Lemma 1: Cutoff Sequence Properties)

引理： 序列 $\{C_t\}$ 是非递减的，并被 $f_{\mathrm{max}}$ 有界。 证明：

1. 单调性 (Monotonicity)： $$C _ { t + 1 } = \operatorname* { m a x } ( C _ { t } , f _ { t } ^ { * } ) \geq C _ { t } \Rightarrow C _ { 1 } \leq C _ { 2 } \leq \cdots \leq C _ { T }$$
2. 有界性 (Boundedness)： 由于观察到的适应度 $f_t^* \le f_{\mathrm{max}}$ 对所有 $t$ 都成立， $$\begin{array} { r l } & { C _ { t + 1 } = \operatorname* { m a x } ( C _ { t } , f _ { t } ^ { * } ) \leq \operatorname* { m a x } ( C _ { t } , f _ { \operatorname* { m a x } } ) \leq f _ { \operatorname* { m a x } } } \\ & { \qquad \Rightarrow C _ { t } \leq f _ { \operatorname* { m a x } } \quad \forall t } \end{array}$$ 因此，$\{C_t\}$ 是一个单调非递减序列，并被 $f_{\mathrm{max}}$ 有界。由于其取整数值，它必然收敛。证毕。

4.7.3. 定理3 (Theorem 3: Finite-Time Convergence)

定理： 截止值序列 $\{C_t\}$ 在最多 $f_{\mathrm{max}} - C_1$ 步内收敛到 $f_{\mathrm{max}}$。 证明： 每次当观察到 $f_t^* > C_t$ 时，截止值会严格增加： $$C _ { t + 1 } = f _ { t } ^ { * } > C _ { t } \Rightarrow C _ { t + 1 } > C _ { t }$$ 由于 $f_t^*$ 被 $f_{\mathrm{max}}$ 有界，并且截止值是整数，所以可能的增量次数最多为 $f_{\mathrm{max}} - C_1$。因此，序列在最多 $f_{\mathrm{max}} - C_1$ 次迭代后稳定在 $f_{\mathrm{max}}$。

4.7.4. 推论2 (Corollary 2: Persistence of Maximum Amplification)

推论： 一旦 $C_t = f_{\mathrm{max}}$，所有具有 $f(x^\star) = f_{\mathrm{max}}$ 的最优态 $x^\star$ 将在所有后续迭代中被神谕标记。 $$f ( x ^ { \star } ) > C _ { t } = f _ { \operatorname* { m a x } } \Rightarrow \text{False}$$ 但是，根据神谕的定义，当 $f(x) > \text{cutoff}$ 时才翻转相位。如果将神谕修改为 $f(x) \ge \text{cutoff}$ (原文此处表述有些模糊，但通常自适应 Grover 会标记 $\ge$ 阈值的状态，以确保最优解被标记)，那么： $$f ( x ^ { \star } ) = C _ { t } = f _ { \operatorname* { m a x } } \Rightarrow \text{phase flip occurs if } f ( x ) \geq C _ { t }$$ 因此，一旦截止值达到 $f_{\mathrm{max}}$，神谕将永久标记所有全局最优解，从而使 Grover 放大能够无限期地放大它们。证毕。

4.8. 自适应截止策略的收敛性 (Convergence of Adaptive Cutoff Strategy)

本文证明了自适应截止策略能够以高概率收敛到最大适应度状态。该更新方案只需要适应度观测和经典的最大值追踪，这比需要已知 $k$ 的完整 Grover 迭代更简单，并允许算法动态减少神谕的接受集，直到只剩下全局最优解。

量子搜索在每一步 $t$ 都以一个由截止值 $C_t$ 定义的神谕 $G_t$ 运行。每轮结束后，截止值更新为： $$C _ { t + 1 } : = \operatorname* { m a x } ( C _ { t } , f _ { t } ^ { * } ) ,$$ 其中 $f_t^*$ 是第 $t$ 次迭代中观察到的适应度。 假设适应度值是整数，并被 $f_{\mathrm{max}} \le 2m$ 有界。

4.8.1. 定理4 (Theorem 4: Cutoff Convergence)

定理： 令适应度值有界，且截止值更新规则是单调的。那么，算法以高概率在最多 $T \le 2m$ 步后终止，并得到一个解 $x^\star$，使得 f(x^\star) = f_{\mathrm{max}，成功概率至少为： $$P _ { s u c c e s s } \geq 1 - \varepsilon .$$ 证明： 本证明结合了 $C_t$ 的单调收敛性与 Grover 振幅放大的概率保证。 如前所述，截止值序列满足： $$C _ { t + 1 } = \operatorname* { m a x } ( C _ { t } , f _ { t } ^ { * } ) , \quad f _ { t } ^ { * } \leq f _ { \operatorname* { m a x } } .$$ 如果 $C_1 = 0$，那么由于每次更新（当发现新最大值时）至少将 $C_t$ 增加1，所以它将在最多 2m 步后收敛到 $C_T = f_{\mathrm{max}}$ (因为 $f_{\mathrm{max}} \le 2m$)。 在每一步 $t$，Grover 搜索将运行 $r_t$ 次迭代，使用截止阈值 $C_t$ 定义的神谕。 令 $\theta_t$ 为由下式定义的角度： $$\sin ^ { 2 } \theta _ { t } = { \frac { k _ { t } } { N } } , \quad { \mathrm { w h e r e } } \quad k _ { t } = | \{ x : f ( x ) > C _ { t } \} | , \quad N = 4 ^ { n } .$$ 根据 Grover 几何学，经过 $r_t$ 轮后的成功概率为： $$P _ { t } = \sin ^ { 2 } ( ( 2 r _ { t } + 1 ) \theta _ { t } ) .$$ 如果我们选择 $r_t$ 使得 $(2r_t+1)\theta_t \approx \frac{\pi}{2}$，那么 $P_t \ge 1-\delta$，其中 $\delta$ 很小。 令 $\varepsilon$ 为总失败预算。那么我们要求： $$\sum _ { t = 1 } ^ { T } \delta _ { t } \leq \varepsilon$$ 在每轮中设置 $\delta_t = \varepsilon / T$。那么以高概率 $1-\varepsilon$，至少有一轮将成功返回一个 $x^\star$ 使得 $f(x^\star) \ge C_t$。 一旦 $C_t = f_{\mathrm{max}}$，神谕将只标记最优解。再次运行 Grover 算法，将 $k=1$ (指只有一个标记态，即全局最优解) 的标记态进行放大，最终的放大步骤将以 $\ge 1-\delta$ 的概率返回真正的最优解。 因此，自适应过程在 $T \le 2m$ 轮内收敛到 $f_{\mathrm{max}}$，最终成功概率至少为 $1-\varepsilon$。证毕。

4.9. 有效性检查操作符与正确性 (Validity Check Operator and Correctness)

令路径 $x \in \mathcal{P}_n$ 被编码为 $n$ 条指令，其中每条指令 $x_k \in \{0, 1, 2, 3\}$ 对应方向 $\{N, E, S, W\}$。 令迷宫网格大小为 $m \times m$，坐标寄存器为 (i, j)。 定义模拟操作符 $S$ 如下： $$S : | x \rangle \mapsto | x \rangle | { \mathrm { v a l i d } } ( x ) \rangle$$ 其中，valid(x) 函数定义为： $${ \mathrm { v a l i d } } ( x ) = { \left\{ \begin{array} { l l } { 1 } & { { \mathrm { i f ~ n o ~ i n v a l i d ~ m o v e ~ i s ~ m a d e ~ ( o u t –o f –b o u n d s ) } } } \\ { 0 } & { { \mathrm { o t h e r w i s e } } } \end{array} \right. }$$ 目标： 证明 $S$ 是可逆的，并且正确计算 valid(x)。

4.9.1. 构建 (Construction)

每次移动的模拟步骤如下：

1. 初始化寄存器： $$| i \rangle = | i _ { s } \rangle , \quad | j \rangle = | j _ { s } \rangle , \quad | v \rangle = | 1 \rangle$$ 其中 $|v\rangle$ 是一个辅助量子比特，初始化为 $|1\rangle$，表示当前路径是有效的。
2. 对于 $k = 1$ 到 $n$ (路径中的每一步)，重复以下操作：
   • 将 $x_k$ (方向编码) 解码为变化量 $\delta_i, \delta_j \in \{\pm 1, 0\}$。
   • 更新 (i, j) 坐标： $$i \leftarrow i + \delta _ { i } , \quad j \leftarrow j + \delta _ { j }$$
   • 通过可逆比较器 (reversible comparators) 比较 i, j 与边界 $[0, m-1]$。
   • 如果超出边界，使用一个受控于溢出 (overflow) 的 Toffoli 门将 $|v\rangle \mapsto |0\rangle$。 我们需要证明： $$| v \rangle = 1 \iff \operatorname { e a c h } \ ( i _ { k } , j _ { k } ) \in [ 0 , m - 1 ] ^ { 2 }$$ 证明： 在每一步中，我们：

• 从步骤代码计算 $\delta_i, \delta_j$ (例如，N = ( -1, 0), E = (0, 1))。
• 通过比较器使用模算术 (modular arithmetic)： $$C _ { i } : | i _ { k } \rangle \mapsto | i _ { k } \rangle | \phi _ { k } ^ { ( i ) } \rangle , \quad \phi _ { k } ^ { ( i ) } = 1 \iff 0 \leq i _ { k } < m$$ 对 $j$ 也进行同样的操作。
• 定义总的有效性标志 $\phi_k = \phi_k^{(i)} \wedge \phi_k^{(j)}$。
• 更新 $|v\rangle$：$v \leftarrow v \land \phi_k$。 由于 AND 逻辑可以使用 Toffoli 门实现，它是可逆的，因此累积的有效性标志是准确的。一旦任何步骤变得无效（即 $\phi_k = 0$），$v$ 将永久变为 0。 $$\Rightarrow \mathrm { v a l i d } ( x ) = 1 \iff \mathrm { A l l ~ s t e p s ~ i n ~ b o u n d s } \quad \square$$

4.9.2. $S$ 的可逆性 (Reversibility of S)

• 每个算术更新都使用可逆加法/减法。
• 每个比较都使用可逆逻辑（例如，通过 cuGT 实现 $|a > b\rangle$）。
• 用于有效性的 AND 逻辑是基于 Toffoli 门的。 因此，$S$ 是可逆的，并且可以嵌入到酉变换中。

4.10. 量子电路素描 (Quantum Circuit Sketch)

4.10.1. 适应度算子 $F$ 的量子电路素描 (Quantum Circuit Sketch for Fitness Operator $F$)

输入：

• 2n 量子比特路径寄存器。
• $\lceil \log_2 C \rceil$ 量子比特的适应度输出寄存器（初始化为零）。
• $\lceil \log_2 m \rceil$ 量子比特的位置寄存器 (i, j)，初始化为起始位置。
• 用于中间逻辑的辅助寄存器。

高级电路阶段：

1. 路径解码器 (Path Decoder)： 对于每个方向块（2个量子比特），应用逻辑：
   • 00 (北): 从 $i$ 减去 1。
   • 01 (东): 从 $j$ 加上 1。
   • 10 (南): 从 $i$ 加上 1。
   • 11 (西): 从 $j$ 减去 1。 这通过 (i, j) 寄存器上的受控加/减门实现。
2. 距离计算器 (Distance Calculator)： 应用可逆减法：$(i_f - i)^2 + (j_f - j)^2$。使用量子算术中的平方和加法电路。
3. 适应度减法 (Fitness Subtraction)： 通过受控减法电路计算 $C - \text{distance}$。结果存储在适应度寄存器中。
4. 反计算临时寄存器 (Uncompute Temporary Registers)： 清理辅助量子比特以恢复可逆性。 所有步骤都使用已知的量子算术原语（例如，Draper 加法器、Cuccaro 加法器用于二进制减法、基于 Toffoli 门的乘法器）。

4.10.2. 神谕比较器电路 (Oracle Comparator Circuit)

描述了一个相位神谕，它翻转 $ft(x) > cutoff$ 的状态的相位。 寄存器：

• 适应度寄存器：$|f_x\rangle$
• 经典阈值：cutoff (硬编码或编码在量子寄存器中)
• 辅助量子比特：1个量子比特的标志位 $|b\rangle$

构建： 比较器可以通过比特减法电路、符号位分析和带有辅助进位比特的多控非门构建。

1. 应用一个大于比较器电路： $$\mathsf { C o m p a r e } ( | f _ { x } \rangle , \mathsf { c u t o f f } ) \to | b \rangle$$ 这会设置 $|b\rangle = 1$ 当且仅当 $f_x > \text{cutoff}$。
2. 应用受控-Z 到完整状态，条件是 $|b\rangle$： $$CZ ( \left| b \right. ) \to ( - 1 ) ^ { b } \left| x \right. \left| f _ { x } \right.$$
3. 反计算比较器： 反向运行电路以重置 $|b\rangle$。

4.10.3. 神谕的酉性和可逆性 (Oracle Unitarity and Reversibility)

令 $f_x \in \mathbb{N}$ 是编码在 $|f_x\rangle$ 寄存器中的适应度值，cutoff $\in \mathbb{N}$ 是一个固定的经典阈值。神谕操作符 $O$ 定义为： $$\begin{array} { r l } & { O \left| x \right. \left| f _ { x } \right. = ( - 1 ) ^ { g ( f _ { x } ) } \left| x \right. \left| f _ { x } \right. , } \\ & { ~ g ( f _ { x } ) = \left\{ \begin{array} { l l } { 1 } & { \mathrm { i f ~ } f _ { x } > \mathrm { c u t o f f } } \\ { 0 } & { \mathrm { o t h e r w i s e } } \end{array} \right. } \end{array}$$ 目标： 证明 $O$ 是酉的 ($O^\dagger O = I$)。 构建： 定义 $g : \{0, \ldots, 2m\} \to \{0, 1\}$ 为一个布尔函数，令 $Z$ 为单量子比特 Pauli-Z 门。$O$ 分三步构建：

1. 比较子电路 $C$： 可逆电路，计算： $$C : | f _ { x } \rangle | 0 \rangle \mapsto | f _ { x } \rangle | g ( f _ { x } ) \rangle$$ 使用可逆比较器（例如 cuGT）。
2. 受控相位翻转 (Controlled Phase Flip)： 在辅助量子比特 $|g(f_x)\rangle = 1$ 的条件下应用 $Z$： $$Z _ { b } \left| g ( f _ { x } ) \right. = ( - 1 ) ^ { g ( f _ { x } ) } \left| g ( f _ { x } ) \right.$$
3. 反计算 (Uncompute)： 应用 $C^{-1}$ 移除辅助量子比特： $$C ^ { - 1 } : | f _ { x } \rangle | g ( f _ { x } ) \rangle \mapsto | f _ { x } \rangle | 0 \rangle$$ 完整的酉操作符 $O$ 作用在 $|x\rangle|f_x\rangle$ 和一个辅助量子比特 $|0\rangle_b$ 上，并执行： $$O = C ^ { - 1 } \cdot \left( I \otimes Z _ { b } \right) \cdot C$$ 酉性证明： 我们证明 $O^\dagger = O^{-1} = O$： $$\begin{array} { r l } & { O ^ { \dagger } = \left( C ^ { - 1 } \cdot Z _ { b } \cdot C \right) ^ { \dagger } } \\ & { \quad = C ^ { \dagger } \cdot Z _ { b } ^ { \dagger } \cdot ( C ^ { - 1 } ) ^ { \dagger } } \\ & { \quad = C \cdot Z _ { b } \cdot C ^ { - 1 } \quad ( \mathrm { s i n c e ~ } C ^ { \dagger } = C ^ { - 1 } , Z ^ { \dagger } = Z ) } \\ & { \quad = O ^ { - 1 } } \end{array}$$ 因此，$O^\dagger O = I \Rightarrow O$ 是酉的。 可逆性： 每个组件都是可逆的：

• 比较器 $C$ 由可逆门（Toffoli、Fredkin）构建。
• $Z$ 是酉的且自逆。
• 反计算操作撤销了 $C$。 因此，$O$ 可以编译成使用 Toffoli、CNOT 和单量子比特门的量子电路。

5. 实验设置

5.1. 数据集

本文没有使用传统意义上的“数据集”，而是定义了“完美迷宫”的抽象模型作为其研究对象。迷宫被形式化为 $m \times m$ 的网格 $\mathcal{M}$，具有无环和可解的特性。 具体迷宫实例： 论文在“工作示例”和“示例执行”部分展示了一个具体的 $2 \times 2$ 迷宫实例：

• 迷宫大小：$m=2$
• 起始点：$(i_s, j_s) = (0, 0)$
• 目标点：$(i_f, j_f) = (1, 1)$
• 路径长度：$n=2$ 该迷宫的结构是一个简单的网格，其墙壁配置未显式给出，但假设存在一条从 $(0,0)$ 到 $(1,1)$ 的有效路径，例如南(S)然后东(E)。 选择理由： 这种形式化的迷宫模型允许作者在理论层面进行算法设计和分析，而不依赖于特定迷宫实例的复杂性。在理论推导和资源分析中，使用参数 $m$ (迷宫大小) 和 $n$ (路径长度) 使得结果具有普适性。所提供的 $2 \times 2$ 迷宫示例用于演示算法在小型、可理解的实例上的具体运作流程。

5.2. 评估指标

本文主要通过理论分析和推导来评估所提出算法的性能，其评估指标主要围绕算法的收敛性、成功概率以及资源消耗。

5.2.1. 成功概率 (Success Probability, $P_{\mathrm{success}}$)

• 概念定义： 成功概率是指在 Grover 搜索算法结束时，通过测量量子寄存器，获得一个标记态（即满足搜索条件、具有高适应度的路径）的概率。在本文中，这表示测量到一条能够到达目标点或距离目标点最近的路径的概率。
• 数学公式： 经过 $r$ 次 Grover 迭代后，成功概率为： $$P _ { \mathrm { s u c c e s s } } ( r ) = \sin ^ { 2 } ( ( 2 r + 1 ) \theta )$$ 其中，$\theta$ 是由标记态数量 $k$ 和总态数量 $N$ 决定的角度： $$\theta = \arcsin \left( { \sqrt { \frac { k } { N } } } \right)$$
• 符号解释：
  • $P_{\mathrm{success}}(r)$: 经过 $r$ 次 Grover 迭代后的成功概率。
  • $r$: Grover 迭代的次数。
  • $\theta$: 初始态与未标记态子空间之间的角度。
  • $k$: 满足神谕标记条件（适应度高于截止值）的路径数量。
  • $N$: 长度为 $n$ 的所有可能路径的总数，$N = 4^n$。

5.2.2. 适应度 (Fitness)

• 概念定义： 适应度函数用于量化一条候选路径的“质量”，即其终点与迷宫目标点之间的接近程度。适应度值越高，表示路径越接近目标，甚至已经到达目标。
• 数学公式： 本文使用的适应度函数基于平方欧几里得距离： $$\operatorname { f u n e s s } ( P ) = C - \left[ ( i _ { \mathrm { e n d } } - i _ { f } ) ^ { 2 } + ( j _ { \mathrm { e n d } } - j _ { f } ) ^ { 2 } \right]$$
• 符号解释：
  • $\operatorname{fitness}(P)$: 路径 $P$ 的适应度值。
  • $C$: 一个常数，其值设置为 $2^r$，其中 $r$ 是存储适应度值所需的量子比特数，且 $C \ge 2(m-1)^2$。它的作用是确保适应度值非负，并且当路径到达目标时（距离为0），适应度达到最大值。
  • $(i_{\mathrm{end}}, j_{\mathrm{end}})$: 路径 $P$ 模拟结束后所到达的最终单元格坐标。
  • $(i_f, j_f)$: 迷宫的目标单元格坐标。
  • $m$: 迷宫的边长。

5.2.3. 量子资源成本 (Quantum Resource Cost)

• 概念定义： 量子资源成本用于衡量执行算法所需的量子比特数量（宽度）和量子门操作的序列长度（深度），以及特定门（如 Toffoli 门）的数量。这对于评估算法在实际量子硬件上的可行性和效率至关重要。
• 度量单位：
  • 量子比特数 (Qubit Count)： 算法所需的总量子比特数量，包括路径寄存器、位置寄存器、适应度寄存器和辅助量子比特。
  • Toffoli 门数 (Toffoli Gates)： Toffoli 门是量子计算中的一个通用门，可用于构建任何可逆经典电路，其数量常用于衡量电路复杂性。
  • 深度 (Depth)： 算法中量子门操作的最长序列长度，与计算时间相关。
• 本文分析： 论文在“Resource Summary”中提供了详细的渐近成本分析，如 Table I 所示。

5.3. 对比基线

本文的重点是提出并严格定义一个全新的 Grover-based 量子迷宫求解算法，而不是与现有的特定量子算法进行性能比较。因此，论文中没有明确列出“对比基线”模型并进行量化实验。

然而，在引言部分，作者定性地指出了经典迷宫求解算法（如回溯 (backtracking) 和广度优先搜索 (breadth-first search)）的局限性：它们在迷宫大小和分支因子方面表现出指数级扩展行为 (exponential scaling behavior)，限制了它们在大型实例中的实际应用。这间接表明，本文提出的量子算法旨在克服经典算法在扩展性上的挑战，通过量子加速提供潜在的性能优势。

因此，如果需要进行“对比基线”分析，它将主要集中在与经典算法的理论复杂性比较上，而非与其他量子算法的实验性能比较。

6. 实验结果与分析

6.1. 核心结果分析

本文没有提供大规模的实验结果，而是通过理论分析、形式化证明和一个小规模的“示例执行”来展示算法的正确性和效率。核心结果分析主要集中在：

1. 理论正确性与收敛性：

   • 均匀叠加的正确性： 定理1证明了算法能够正确地制备所有长度为 $n$ 的有效路径的均匀叠加态，这是 Grover 搜索的基础。
   • 适应度算子的酉性： 定理2证明了适应度算子是酉的，确保了其在量子电路中的合法性。
   • Grover 迭代的几何： 详细分析了 Grover 迭代作为二维子空间中的旋转操作，以及成功概率的推导，这与 Grover 算法的标准理论相符。
   • 自适应截止策略的收敛性： 引理1和定理3证明了截止值序列是单调非递减且有界的，最终在有限步内收敛到最大适应度 $f_{\mathrm{max}}$。定理4进一步证明了通过该策略，算法能够以高概率收敛到最大适应度状态。这些理论结果为算法的可靠性提供了强有力的保证。

2. 资源效率分析 (Resource Efficiency Analysis)： 论文在 Table I 中总结了算法的量子资源成本，显示了其与迷宫尺寸和路径长度的扩展关系。

   以下是原文 Table I 的结果：

   Parameter	Asymptotic Cost
   Path register size (|x)	2n qubits
   Position registers (|i , |j)	2 · [log2 m] qubits
   Distance register (|d)	[log2 m] qubits
   Fitness register ( f)	[log2(2m)] qubits
   Comparator ancilla (|b) , carry bits)	O(log m) qubits
   Total ancilla(adder, comparator, cleanup)	O(n log m) qubits
   Toffoli gates(path simulation)	O(n log m)
   Toffoligates(distance + fitness)	O(log2 m)
   Toffoligates (oracle comparator)	O(log m)
   Grover iteration depth (1 round)	O(n log m)

   分析：

   • 量子比特数量： 路径寄存器大小 2n 与路径长度 $n$ 线性相关。位置寄存器、距离寄存器、适应度寄存器和比较器辅助量子比特的尺寸都与 $\log m$ (迷宫边长的对数) 相关，这是非常高效的。总辅助量子比特为 $O(n \log m)$，这意味着随着迷宫尺寸的增大，量子比特需求增加相对缓慢。
   • Toffoli 门数量和深度： 路径模拟的 Toffoli 门数量和单轮 Grover 迭代的深度与 $n \log m$ 相关，这表明算法的计算复杂性与路径长度和迷宫尺寸的对数呈准线性关系。距离和适应度计算的 Toffoli 门数量与 $\log^2 m$ 或 $\log m$ 相关。
   • 效率优势： 这种对数或准线性的扩展性与经典算法的指数级扩展性形成了鲜明对比，突出了量子算法在处理大规模迷宫问题上的潜在效率优势。

3. 示例执行 (Example Execution)： 论文通过一个 $2 \times 2$ 迷宫的例子（从 $(0,0)$ 到 $(1,1)$，路径长度 $n=2$）演示了算法的具体工作流程。

   • 路径编码： 路径 $|1001\rangle$ 对应于 S, E 移动序列。
   • 路径模拟： $(0,0) \stackrel{S}{\to} (1,0) \stackrel{E}{\to} (1,1)$，最终到达目标。
   • 距离计算： 终点 $(1,1)$ 与目标 $(1,1)$ 的平方欧几里得距离为 0。
   • 适应度计算： 设定 $C=4$，则适应度 $f = 4 - 0 = 4$。
   • 神谕标记： 如果截止值 $C=2$，由于 $f=4 > 2$，神谕将翻转该路径的相位。
   • 扩散与反计算： 接着应用扩散算子，并通过反计算恢复辅助量子比特。 这个例子清晰地展示了适应度算子和神谕如何具体地作用于一个量子态，以及如何计算和标记一个最优路径。

总结： 尽管缺乏大规模的实证结果，但本文通过严谨的数学形式化、详细的电路设计和渐近资源分析，成功地构建了一个理论上可行且高效的量子迷宫求解算法。核心发现是，该算法在量子比特和门操作方面具有良好的扩展性，并且自适应截止策略确保了其能够可靠地收敛到最优解。

6.2. 数据呈现 (表格)

以下是原文 Table I 的结果：

7. 总结与思考

7.1. 结论总结

本文成功提出了一个完整且严谨的基于 Grover 算法的量子迷宫求解框架。其核心贡献在于：

• 全面的算法流程： 从路径的量子编码到适应度评估、神谕标记，再到 Grover 振幅放大，构建了一个端到端的量子算法管道。
• 可逆操作的严格设计： 成功设计了可逆的适应度算子和神谕，确保了算法的酉性，使其能在量子硬件上实现。
• 自适应收敛机制： 引入了自适应截止策略，通过迭代调整阈值，保证了算法能够以高概率收敛到最优或高适应度的路径。
• 高效的资源扩展性： 理论分析表明，算法所需的量子比特和门操作数量与迷宫尺寸呈对数关系，与路径长度呈线性或准线性关系，展现出优于经典算法的潜在扩展性。 该工作不仅为解决完美迷宫问题提供了一个量子加速的理论模型，也为量子混合寻路和规划提供了坚实的基础，并展示了其在其他树状或无环图搜索领域的潜力。

7.2. 局限性与未来工作

论文作者指出了当前的局限性，并提出了以下未来研究方向：

局限性：

• 理想化假设： 算法目前是在理想化的假设下运作的，例如无噪声量子门和完美的测量。在实际的量子硬件上，噪声和错误是不可避免的。

未来工作：

• 适应噪声环境： 将算法扩展到噪声中等规模量子 (NISQ) 设备，可能需要通过错误缓解 (error mitigation) 或容错技术 (fault-tolerant techniques)，例如表面码 (surface codes)。
• 处理复杂环境： 泛化该框架以解决更复杂的环境问题，例如：
  • 带环的迷宫 (mazes with cycles)： 完美迷宫是无环的，而实际环境可能包含环路。
  • 动态演化拓扑 (dynamically evolving topologies)： 迷宫结构可能随时间变化。
  • 带权遍历成本 (weighted traversal costs)： 不同的移动可能具有不同的成本。
• 结合其他量子模型： 探索与量子行走 (quantum walk) 模型或变分神谕 (variational oracle) 构建的集成，以可能进一步提高性能。
• 量子混合方法： 结合经典-量子混合预处理 (classical-quantum preprocessing) 方法，在量子执行之前减少有效的搜索空间，以提高在近期硬件上的实用性。

7.3. 个人启发与批判

7.3.1. 个人启发

1. Grover 算法的通用性： 本文再次展示了 Grover 算法作为一种通用搜索原语的强大潜力，可以被巧妙地应用于各种结构化问题，而不仅仅是简单的数据库查找。通过精心设计的编码和适应度函数，可以将复杂问题映射到 Grover 框架中。
2. 可逆计算的重要性： 论文对可逆性（酉性）的严格强调和电路级实现细节非常具有启发性。在量子算法设计中，不仅仅要考虑逻辑功能，更要关注如何将经典计算步骤转换为可逆的量子操作，这对于保持量子态的完整性和避免信息损失至关重要。
3. 自适应策略的引入： 自适应截止策略是一个非常实用的设计。它解决了在实际问题中“不知道最优解在哪里”的挑战，允许算法通过迭代和反馈机制逐步收敛。这种将经典迭代与量子加速相结合的混合思想，对于 NISQ 时代甚至未来的容错量子计算都具有重要意义。
4. 模块化设计： 适应度算子和神谕作为独立的模块被严格定义和实现，这为其他类似的量子搜索问题提供了设计范式。这种模块化使得算法更易于理解、验证和扩展。

7.3.2. 批判与潜在改进

1. 缺乏实证模拟结果： 尽管提供了详尽的理论分析和资源成本，但论文中没有包含任何模拟结果（即使是小规模的），无法直观地展示算法的实际性能，例如振幅随迭代次数的演变、收敛速度的实际表现等。这使得初学者难以感知理论成果的实际效果。
2. 完美迷宫的限制： 完美迷宫的“无环”特性极大地简化了问题，因为它确保了任意两点间只有一条简单路径。这在很大程度上避免了经典算法中处理环路和重复访问的复杂性。但实际的寻路问题往往涉及有环图和动态障碍物，算法的泛化能力仍需更深入的验证。
3. 路径长度 $n$ 的预设： 论文假设 $n \ge \ell_{\mathrm{min}}$，其中 $\ell_{\mathrm{min}}$ 是最短路径长度。然而，确定最短路径长度本身就是一个计算问题。如果 $n$ 设得过大，会增加不必要的量子比特和计算资源；如果设得过小，则可能找不到最优解。虽然提到可以“启发式设置或迭代调整”，但缺乏具体策略。
4. $f_{\mathrm{max}}$ 的获取和常数 $C$ 的设置： 定理4的收敛性证明依赖于适应度值被 $f_{\mathrm{max}} \le 2m$ 有界。虽然 $f_{\mathrm{max}}$ 理论上可以计算（当距离为 0 时），但常数 $C$ 的选择需要保证适应度非负且能区分所有有效距离。这些参数的实际确定和优化在大型迷宫中可能仍是一个挑战。
5. 实际资源消耗与 NISQ 挑战： 尽管渐近资源分析显示出高效性，但 $O(n \log m)$ 的 Toffoli 门数量和深度在 NISQ 时代仍然可能非常高。一个 $m=1000$ 的迷宫，路径长度 $n=100$ 的话，$\log_2 m \approx 10$。这意味着 Toffoli 门数量可能在 $100 \times 10 = 1000$ 级别，这对于当前大多数超导或离子阱量子计算机来说仍然是巨大的挑战，尤其是在考虑门保真度时。论文虽然提到了未来工作可能涉及错误缓解，但对于当前实现的可行性仍有较大差距。