量子离散绝热线性求解器¶

算法描述¶

本算法的详细理论基础和实现细节源于论文：PRX Quantum 3, 040303 (2022) - Quantum Algorithm for Linear Systems of Equations with Augmented Matrices。

该算法旨在求解线性方程组 Ax=b，其核心思想是利用离散化的量子绝热演化 (Quantum Discrete Adiabatic Evolution) 过程，通过执行一种特殊的量子行走 (Quantum Walk) 来逼近最终的解。相较于其他量子线性求解算法（如HHL），它在某些方面具有不同的性能特点和实现路径。

算法流程¶

算法的完整流程可以分解为以下几个关键步骤：

数据预处理与编码 (classical2quantum 函数) 在将经典问题映射到量子计算机之前，必须进行两项关键的预处理：
- 厄米化 (Hermitization): 量子演化由厄米算符（哈密顿量）驱动。对于一个通用的、非厄米的方阵 A，算法会构建一个更大的增广矩阵，该矩阵是厄米的，并且其解与原问题相关。
- 维度补全 (Padding): 为了能在由 n 个量子比特构成的希尔伯特空间（其维度为 2^n）中进行操作，矩阵的维度需要被补全至最接近的2的整数次幂。
这两个步骤均在 classical2quantum 函数中完成。该函数不仅返回处理后的矩阵和向量，还会提供一个用于在算法结束时恢复 (recover) 原始解尺寸的函数。
量子态制备 (Quantum State Preparation) 算法的初始态需要编码向量 b 的信息，即制备与向量 b 对应的量子态 |b⟩。这一步通常通过量子随机访问存储器 (QRAM) 来高效实现，它能将经典数据加载到量子态的振幅中。
离散绝热演化 (Discrete Adiabatic Evolution) 这是算法的引擎。其核心是执行一个受控的量子行走，该行走模拟了从一个简单的初始哈密顿量 H_I 到一个编码了问题解的最终哈密顿量 H_F 的绝热演化过程。
- 这个演化过程由一个调度参数 s 控制，s 从 0 逐渐变化到 1。
- 当 s=0 时，系统处于容易制备的 H_I 的基态。
- 当 s 缓慢地增加到 1 时，根据量子绝热定理，系统将始终保持在其基态上。
- 当 s=1 时，系统演化到 H_F 的基态，而这个基态就精确地包含了我们想要的解向量 |x⟩。
- 与连续的绝热演化不同，“离散”意味着这个过程被分解为一系列有限的、独立的演化步骤（Quantum Walk Steps）。演化步数的多少直接影响算法的精度和成功率，并与矩阵的条件数 κ (kappa) 密切相关。
结果测量与恢复 (Measurement and Recovery) 演化结束后，我们得到一个包含了多个辅助量子比特的复杂量子态。通过对辅助比特进行投影测量（例如，确保它们都处于 |0⟩ 态），主寄存器中的态会坍缩到正比于解向量 |x⟩ 的状态。

由于量子态的物理性质，直接从线路中测量出的解向量 sol 是被归一化的（即其L2范数 ||sol||₂ = 1）。为了得到最终的经典解 x，我们需要计算其正确的模长 norm。我们的目标是找到一个 norm，使得残差 ||b - A * (norm * x_hat)||₂ 最小化。这个问题可以通过经典的最小二乘法来解决，其解析解为 norm = (b · y) / (y · y)，其中 y = A * x_hat：
```
```python
# 假设 x_hat 是从量子线路得到的归一化解
y = np.dot(A, x_hat)

# 通过最小化 ||b - norm * A * x_hat|| 来计算模长 norm
norm = np.dot(b, y) / np.dot(y, y)

# 将归一化的解向量乘以正确的模长，得到最终解
x = norm * x_hat
```
```
通过这个经典的后处理步骤，我们便能从量子算法得到的归一化向量中，恢复出具有正确模长的最终解（误差小于10%）。