Quantumly controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms

技术摘要：矩阵操作算法中的量子控制测量、埃尔米特共轭与归一化

问题陈述
本文针对现有量子矩阵操作算法（特别是基于将矩阵元素编码进纯叠加态概率振幅的方法，如参考文献 [33–35] 所提出的方法）中的三个关键局限性进行了探讨：

1. 后选择效率低下（Post-Selection Inefficiency）： 当前的算法依赖于对单个量子比特辅助系统（ancilla）进行投影测量，以过滤掉“垃圾”态并选择期望结果。这一过程面临成功概率较低的问题，且该概率随矩阵维度的增加呈多项式或指数级下降。因此，算法需要多次运行才能获得所需结果，从而严重降低了效率。
2. 无法处理埃尔米特共轭（Inability to Handle Hermitian Conjugation）： 虽然这些算法通常可以处理复矩阵，但诸如埃尔米特共轭之类的特定操作无法在标准的编码框架内实现，这限制了代数运算的多样性。
3. 严格的归一化约束（Strict Normalization Constraints）： 将矩阵元素编码进纯量子态的过程施加了严格的归一化条件（$\sum |a_{jk}|^2 = 1$）。这限制了矩阵元素的模长，需要进行特定的缩放，而这种缩放在某些应用场景下可能并非最优。

方法论
作者提出了对矩阵操作框架的三种不同扩展：

1. 量子控制测量 (Quantumly Controlled Measurement, QCM)：

   • 与对单个辅助量子比特（$B_1$）进行标准投影测量不同，作者引入了一个双量子比特辅助系统（$B_1$ 和 $B_2$）。
   • 第一个量子比特（$B_1$）的状态作为作用于第二个量子比特（$B_2$）上的测量算符的控制端。
   • 具体而言，如果系统处于一种“有用”项与 $|1\rangle_{B_1}$ 纠缠，而“垃圾”项与 $|0\rangle_{B_1}$ 纠缠的叠加态中，则通过一个 C-NOT 门将 $B_1$ 与 $B_2$ 进行纠缠。随后应用受控测量算符 $W^{(3)}_{B_1B_2} = |1\rangle_{B_1}\langle 1| \otimes M_{B_2} + |0\rangle_{B_1}\langle 0| \otimes I_{B_2}$。
   • 该机制确保了如果存在有用分量（$\alpha \neq 0$），则会对 $B_2$ 触发测量，从而使系统坍缩到期望状态，避免了标准后选择法所带来的概率性失败问题。

2. 实部与虚部的分离编码：

   • 为了实现埃尔米特共轭，作者建议使用一个额外的单量子比特子系统（$M$）将复矩阵元素的实部和虚部分别编码进两个正交的子空间中。
   • 状态 $|0\rangle_M$ 标记实部，而 $|1\rangle_M$ 标记虚部。
   • 埃尔米特共轭随后通过在行/列寄存器上执行 SWAP 操作结合在 $M$ 寄存器上的 $\sigma_z$ 操作来实现，从而有效地完成转置和复共轭。

3. 弱化的归一化约束：

   • 作者在编码方案中引入了一个额外的辅助量子比特（$K$）。
   • 初始态被修改为包含一个与状态 $|0\rangle_K$ 相关联、振幅为 $b$ 的额外项，而矩阵元素则与 $|1\rangle_K$ 相关联。
   • 这将归一化条件从等式（$\sum |a_{jk}|^2 = 1$）转变为不等式（$\sum |a_{jk}|^2 \leq 1$），从而为矩阵元素的量级提供了更大的灵活性。

核心贡献与结果

• 在矩阵乘法中的实现： 作者将 QCM 以及两种编码扩展集成到了矩阵乘法算法中。他们证明了该算法不仅能执行标准乘法，还能执行涉及埃尔米特共轭的操作（例如 $A^\dagger B$, $A B^\dagger$）。
• 电路构建： 文中详细展示了以下内容的量子电路：
  • QCM 子程序。
  • 埃尔米特共轭算符。
  • 结合了所有三种扩展的改进型矩阵乘法算法。
• 复杂度分析：
  • 空间： 这些修改仅需常数个额外的量子比特（具体而言，对于编码扩展需要四个额外量子比特，而在乘法语境下的 QCM 需要一个辅助量子比特）。空间复杂度保持为 $O(n)$，其中 $N=2^n$ 是矩阵维度。
  • 深度： 电路深度保持为 $O(n)$。作者指出，虽然由于需要多次运行以克服低成功概率，先前算法的总运行时间实际上是 $O(2^n n)$，但基于 QCM 的算法通过单次运行即可实现结果，保持了电路本身的 $O(n)$ 深度特性。
• 归一化提取： 作者承认 QCM 移除了关于归一化常数 $G$ 的概率信息（此前 $G$ 是通过测量的成功概率推导出来的）。他们提出了一种通过多次运行算法来测量辅助态 $|0\rangle_K$ 的概率，从而概率性地测量 $G$ 的方法，尽管这需要与生成单次结果的过程分开进行。

意义与主张
本文声称，引入量子控制测量（QCM）从根本上解决了矩阵类量子算法中固有的“后选择问题”。通过用确定性的量子控制过程取代对垃圾态的概率性过滤，该算法消除了因重复运行而产生的指数级开销。

作者强调，QCM 不仅仅是一种振幅放大技术（如 Grover 算法），而是一种结合了量子控制与经典测量的独特算符，可能提供了一种新型的“量子-经典控制”。

此外，关于埃尔米特共轭和放宽归一化约束的扩展，扩大了矩阵操作算法在更广泛的复矩阵和数据编码场景中的适用性。作者指出，虽然 QCM 的实际物理实现尚未在标准量子/经典算符层面进行详细阐述，但其理论公式为量子叠加态的真实性提供了依据，并为更高效的量子线性代数提供了一条路径。

文章最后总结道，这些修改不仅可以应用于矩阵乘法，还可以应用于参考文献 [34, 35] 中讨论的其他算法，包括矩阵加法、行列式计算、求逆以及线性方程组求解，以及其他基于测量的量子算法。