技术摘要：一种用于高斯消元法的量子电路

问题陈述

高斯消元法是求解线性方程组、计算矩阵秩、行列式及逆矩阵的基础算法。虽然抽象的量子算法由幺正操作定义，但其实际实现通常需要对位串映射进行可逆的经典构建。一个显著的挑战在于，高斯消元法本质上是非单射的（许多输入矩阵对应同一个行阶梯形式），因此需要至少 $x-y$ 个量子比特的辅助空间（垃圾空间）来维持可逆性，其中 $x$ 和 $y$ 分别是输入和输出的位长度。

以往的高斯消元量子实现被限制在二进制域 $GF(2)$ 内。这些现有工作面临两个主要局限：

1. 垃圾累积： 它们要么未能达到最小理论工作空间要求，要么产生了大量的“垃圾”（补充空间），且无法被解算（uncompute）。
2. 复杂度失配： 它们往往无法达到与经典实现相同的渐近复杂度，特别是在 Toffoli 深度和量子比特数量方面。

此外，目前尚不存在适用于任意有限域 $GF(p^l)$ 的广义量子高斯消元电路，这限制了量子线性代数在更广泛的密码学和代数背景下的应用。

方法论

作者提出了一种可在任何有限域 $GF(p^l)$ 上运行的可逆量子高斯消元电路。该方法的核心在于三项创新：

1. 伪行阶梯形式 (Pseudo Row Echelon Form)

为了解决标准高斯消元法的非单射问题，作者引入了伪行阶梯形式。

• 定义： 若矩阵 $A'$ 的上三角元素与 $A$ 的标准行阶梯形式的上三角元素一致，则称 $A'$ 为伪行阶梯形式。其下三角和对角部分并非由该形式严格定义，而是用于存储信息。
• 机制： 这种变换将本质上非单射的映射转换为双射变换。用于逆转操作所需的信息被保留在下三角和对角项中，从而允许将结果覆盖回输入量子比特，同时仅使用极少量的临时量子比特。

2. 算法结构

所提算法（算法 1）通过迭代列来变换矩阵。它依赖于四个可逆子程序：

• 标记 (Labeling)： 识别主元索引（当前列中第一个非零元素所在的行），并以一元制（unary format）对其进行编码。作者利用递归的、类似锦标赛（tournament-like）的结构来并行化这一过程，从而降低深度。
• 换行 (Pivoting)： 将第一行与主元行进行交换。这是通过锦标赛式的交换机制实现的，该机制可以通过“借用量子比特”（即处于未知状态但在操作结束时会被恢复到初始状态的辅助量子比特）来实现并行化。
• 行归约 (Row Reduction)： 将主元行元素除以主元元素，并将主元行从其他行中减去。这涉及域运算（乘法、求逆、加法），并通过借用量子比特进行并行化处理，以最小化深度。
• 删除主元索引 (Deleting the Pivot Index)： 逆转标记和部分换行步骤，以将工作量子比特恢复为零，确保电路在补充空间方面是无垃圾的。

3. 利用借用量子比特进行并行化

一个关键的技术贡献是系统地使用借用量子比特 (Borrowed Qubits) 来实现并行操作。

• 该电路不要求干净的辅助量子比特，而是利用可能持有未知值的量子比特。
• 作者改编了 Gidney 的方法，将共享控制值或操作数转移到这些借用量子比特中，执行并行操作，然后应用修正步骤以将借用量子比特恢复到其原始状态。
• 这种技术被应用于受控交换（在换行步骤中）和算术运算（在行归约步骤中），显著降低了电路深度。

核心贡献与结果

1. 向任意有限域的推广

不同于以往仅限于 $GF(2)$ 的工作，本设计已推广至任何有限域 $GF(p^l)$。这使得该电路能够处理与各种密码原语和编码理论问题相关的更复杂的代数结构。

2. 无垃圾构造

开发的电路实现了关于补充空间的无垃圾构造 (Garbage-Free Construction)。

• 高斯消元的结果直接覆盖在输入量子比特上。
• 电路在中间计算过程中仅需 $m-1$ 个临时工作量子比特，这些量子比特在操作结束时会被完全恢复为零。
• 至关重要的是，除了这些临时量子比特和输入量子比特外，该电路不占用任何补充（垃圾）空间。这与此前要求 $O(n^2)$ 或 $O(mn)$ 且无法返回零的补充空间（如文献 [20]）形成对比。本文将补充空间定义为初始为零但在操作结束时未返回零的工作量子比特；本设计确保该计数为零。

3. 复杂度改进

论文提供了针对大小为 $m \times n$（其中 $m \ge n$）且在 $GF(2)$ 上的矩阵的电路复杂度的定量比较，总结于论文表 1 中：

指标	前人工作 ([9], [20], [5])	本研究
Toffoli 计数	$O(n^2m)$ 到 $O(n^2m^2)$	$O(n^2m)$
Toffoli 深度	$O(nm)$到$O(n^2m \log^3 m)$| **$O(m \log^2 n + n \log^4 m)$**
临时空间	$0$到$m-2$| **$m-1$**
补充（垃圾）空间	$0$到$O(n^2)$| **$0$**

• 在 $GF(2)$ 中： 该电路实现了在对数因子范围内最优的已知渐近 Toffoli 深度，同时匹配了 $O(n^2m)$ 的经典算术复杂度。
• 在一般域中： 复杂度随域大小参数 $\alpha = l \lceil \log_2 p \rceil$ 缩放，保持了相同的结构效率。

重要性与主张

作者声称，这项工作代表了量子线性代数实现中的一次重大优化：

1. 优化权衡： 该设计成功优化了时间（深度）与空间（量子比特）之间的权衡。它在匹配经典算术复杂度的同时，严格限制了额外空间的使用，这对于量子比特数量受限的近期待机量子硬件至关重要。
2. 无垃圾的可逆性： 通过引入伪行阶梯形式，论文证明了可以在不累积补充垃圾量子比特的情况下实现可逆的高斯消元，这在之前的 $GF(2)$ 实现中尚未实现，且仅使用了 $m-1$ 个临时量子比特。
3. 广泛的适用性： 向任意有限域的推广扩展了涉及非二进制域线性问题的量子算法范围，例如某些后量子密码分析任务和编码理论应用。

论文总结道，尽管仍有进一步优化的空间（例如降低乘法深度），但当前的设计为可逆高斯消元树立了新的基准，在低量子比特开销与竞争性的时间复杂度之间取得了平衡。