算法移植指南¶
备注
本页镜像仓库级指南 docs/algorithm-implementation_zh-cn.md。 该文件为权威版本;更新后请在文档站重建时刷新本副本。
基于 PySparQ 的量子算法实现¶
本节详细记录 PySparQ 如何将 SparQ 的量子算法实验代码(C++)逐一转译为 Python 实现,涵盖代码与量子算法步骤的精确对应关系、寄存器长度管理策略,以及各子模块的实现流程。
一、覆盖率总览:C++ 实验 vs PySparQ 实现¶
算法 |
C++ 实验代码 |
PySparQ 实现文件 |
对应状态 |
|---|---|---|---|
Grover |
|
|
✅ 完整复刻 |
Shor |
|
|
✅ 完整复刻 |
QDA |
|
|
✅ primitive 级转译,解读出后处理待补 |
CKS |
|
|
✅ primitive 级转译,LCU 解读出后处理待补 |
QFT |
|
❌ 无独立模块 |
❌ 尚未实现 |
GHZ |
|
❌ 无 |
❌ 尚未实现 |
QCNN |
|
❌ 无 |
❌ 尚未实现 |
关键发现:
Grover 和 Shor 实现了完整的一一对应,是目前 PySparQ 算法库中最完整的两个实现
QDA 和 CKS 的 Python 实现不直接调用 C++ solver,而是组合 PySparQ 底层 primitive 来复刻 C++ 的寄存器级流程;当前未完成的是测量、post-selection 和线性系统解向量读出
QFT、GHZ 的 C++ 实现较简单,可作为接下来补全的优先目标
QCNN 在 C++ 侧已被禁用,需要先在 C++ 侧恢复再转译到 Python
二、Register Level Programming 在量子算法中的通用模式¶
在深入各算法之前,先总结 PySparQ 实现量子算法时的通用寄存器管理模式。
2.1 寄存器角色分工¶
每个量子算法均需定义以下几类寄存器,理解它们的角色是理解实现细节的关键:
寄存器类型 |
命名模式 |
长度(比特) |
作用 |
|---|---|---|---|
主数据寄存器 |
|
|
存储算法主输入,如搜索空间地址 |
数据寄存器 |
|
视数据范围而定,通常 64 |
临时存放 QRAM 读取的数据 |
搜索值寄存器 |
|
与 data 相同 |
存放要搜索/匹配的目标值 |
辅助 Ancilla 寄存器 |
|
1 或与主寄存器相同 |
控制流、标记位、条件反射 |
精度寄存器 |
|
2×n(n 为主寄存器宽度) |
相位估计、迭代计数 |
2.2 寄存器长度的选取原则¶
主寄存器宽度 = ceil(log2(问题规模 N))
数据寄存器宽度 = 64(默认值,足够容纳浮点数量化后的整数)
精度寄存器宽度 = 2 × ceil(log2(N)) ← 主要用于 Shor 算法的相位估计
在 grover.py 中(第 256–283 行):
n_bits = int(math.log2(n)) + 1 if n > 0 else 1 # 地址寄存器宽度
data_reg = ps.AddRegister("data", ps.UnsignedInteger, data_size)(state) # 数据寄存器固定64位
2.3 通用量子操作模式¶
几乎所有算法都遵循以下操作模式:
# ① 清理系统
ps.System.clear()
# ② 创建量子态
state = ps.SparseState()
# ③ 添加寄存器(链式调用,返回寄存器 ID)
addr_reg = ps.AddRegister("addr", ps.UnsignedInteger, n_bits)(state)
# ④ 初始化(叠加态 / 指定值)
ps.Hadamard_Int_Full("addr")(state) # 全叠加
ps.Init_Unsafe("target", target)(state) # 指定值
# ⑤ 算法主体(Oracle / Walk / 量子门序列)
grover_op(state) # 或 walk_op(state)
# ⑥ 测量(偏迹)
measured_results, prob = ps.PartialTrace([...Registers...])(state)
三 Grover 量子搜索算法¶
3.1 算法概述与数学原理¶
Grover 算法用于在 N 个无序条目中搜索 M 个标记项,复杂度为 O(√(N/M)),相比经典 O(N) 有平方加速。
核心迭代:
G = D · O
其中 Oracle O 标记目标态(加负相位),扩散算子 D 放大振幅。
3.2 C++ 实现 → Python 的精确对应¶
C++ 测试(GroverTest.cpp,第 272–355 行)的核心逻辑与 grover.py 的对应关系:
C++ 代码(GroverTest.cpp) |
PySparQ 实现(grover.py) |
说明 |
|---|---|---|
|
|
量子随机存取存储器建立 |
|
|
地址寄存器添加 |
|
|
搜索目标初始化 |
|
|
创建等幅叠加态 |
|
|
完整 Grover 迭代 |
|
|
偏迹获取测量结果 |
3.3 Oracle 的实现细节(代码行级对应)¶
C++ GroverTest.cpp 中无显式 Oracle 注释,但 grover.h(SparQ_Algorithm)定义了 GroverOracle 结构,对应 Python 实现如下:
第 82–113 行(Oracle 工作流程):
def __call__(self, state: ps.SparseState) -> None:
# Step 1: QRAMLoad → |addr⟩|0⟩ → |addr⟩|memory[addr]⟩
ps.QRAMLoad(self.qram, self.addr_reg, self.data_reg)(state)
# Step 2: 创建比较标志寄存器(less / equal)
compare_less = ps.AddRegister("compare_less", ps.Boolean, 1)(state)
compare_equal = ps.AddRegister("compare_equal", ps.Boolean, 1)(state)
# Step 3: 比较 data 与 target,产生 less/equal 标志
ps.Compare_UInt_UInt(
self.data_reg, self.search_reg, compare_less, compare_equal
)(state)
# Step 4: 匹配时加负相位(标记)
phase_flip = ps.ZeroConditionalPhaseFlip([compare_equal])
phase_flip(state)
# Step 5: 反比较(反操作,清理辅助寄存器)
ps.Compare_UInt_UInt(
self.data_reg, self.search_reg, compare_less, compare_equal
)(state)
# Step 6: 删除临时寄存器
ps.RemoveRegister(compare_equal)(state)
ps.RemoveRegister(compare_less)(state)
# Step 7: QRAMLoad 自反操作(QRAMLoad² = I)
ps.QRAMLoad(self.qram, self.addr_reg, self.data_reg)(state)
关键设计决策:
三步式相位标记:QRAMLoad → Compare → PhaseFlip → Uncompute → QRAMLoad,实现了无 ancilla 污染的相位 oracle
Compare_UInt_UInt:PySparQ 直接对两个寄存器值做比较,生成布尔标志位,无需编译成量子门序列——这是 Register Level Programming 的核心优势
临时寄存器管理:每次 Oracle 调用都会临时创建
compare_less/equal,使用后立即 RemoveRegister,避免状态空间膨胀
3.4 扩散算子的实现细节(第 116–171 行)¶
def __call__(self, state: ps.SparseState) -> None:
ps.Hadamard_Int_Full(self.addr_reg)(state) # H
phase_flip = ps.ZeroConditionalPhaseFlip([self.addr_reg]) # P_0
phase_flip(state) # 对 |0⟩ 加相位
ps.Hadamard_Int_Full(self.addr_reg)(state) # H
数学上:D = H · P_0 · H = 2|s⟩⟨s| - I(关于均匀叠加态的反射)
3.5 GroverIterator 的完整流程(第 173–222 行)¶
def __call__(self, state: ps.SparseState) -> None:
# 每次迭代:Oracle → Diffusion
self.oracle(state) # 标记
self.diffusion(state) # 振幅放大
对应 C++ 测试中的循环(第 319–324 行):
for (size_t i = 0; i < n_repeats * 4; ++i) {
auto qram_data_reg = AddRegister("data", UnsignedInteger, data_size)(state);
GroverOperator(&qram, qram_addr_reg, qram_data_reg, search_data_reg)(state);
(RemoveRegister(qram_data_reg))(state); // 每次迭代后清理临时 data 寄存器
}
3.6 量子计数 GroverCount 的实现(第 314–384 行)¶
对应 C++ grover_count_success_test(第 449–503 行):
C++ 代码 |
Python 实现 |
|---|---|
|
|
|
|
|
|
逆向 QFT |
|
四、Shor 量子因数分解算法¶
4.1 算法概述¶
Shor 算法通过量子相位估计找到模幂运算的周期 r,从而将大数分解转化为求 gcd,在 RSA 加密等领域有重要应用。复杂度 O((log N)³),相对经典的亚指数分解有指数加速。
核心流程:
1. 选择随机数 a (与 N 互素)
2. 量子相位估计:找最小 r 使得 a^r ≡ 1 (mod N)
3. 计算 gcd(a^(r/2)±1, N) 得到因子
4.2 C++ 实现 → Python 的精确对应¶
C++ ShorTest.cpp(第 7–26 行):
semi_classical_shor(N); // 核心调用,迭代 100 次
对应 Python shor.py 中的 SemiClassicalShor 类(第 241–331 行):
C++ 步骤 |
Python 实现(shor.py) |
代码位置 |
|---|---|---|
半经典迭代测量 |
|
第 282–330 行 |
创建工作量子比特 |
|
第 300–302 行 |
受控模幂运算 |
|
第 306–307 行 |
相位校正 |
|
第 311–313 行 |
Hadamard + 测量 |
|
第 316–320 行 |
逆向 QFT(隐式在迭代测量中) |
|
第 329 行 |
经典后处理 |
|
第 166–196 行 |
4.3 模幂运算的实现(第 39–65 行、198–239 行)¶
C++ Shor 实现使用自定义量子算术模块。Python 对应实现:
# 模幂函数(纯数学,第 39–65 行)
def general_expmod(a: int, x: int, N: int) -> int:
"""经典平方-乘算法:a^x mod N"""
if x == 0: return 1
if x & 1: # 奇数
return (general_expmod(a, x-1, N) * a) % N
else: # 偶数
half = general_expmod(a, x // 2, N)
return (half * half) % N
# 受控模乘算子(第 198–239 行)
class ModMul:
def __call__(self, state: ps.SparseState) -> None:
def modmul_func(val: int) -> int:
return (val * self.opnum) % self.N
op = ps.CustomArithmetic([self.reg], 64, 64, modmul_func)
op.conditioned_by_all_ones(cond_reg)(state)
关键设计:
CustomArithmetic是 Register Level Programming 的极致体现——直接写 Python 函数描述整数到整数的映射,由 SparQ 自动编译为量子算术电路无需手动构造受控-NOT 和单比特门组合
4.4 半经典 Shor 的量子电路流程(第 282–330 行)¶
for x in range(size): # size = 2 * n_bits(N)
① work_reg = |0⟩ + |1⟩ (通过 Hadamard)
② 受控模乘 a^(2^(size-1-x)) mod N (conditioned_by_all_ones on work_reg)
③ 相位校正 from prior results
④ Hadamard on work_reg
⑤ 测量 work_reg → result_bit
⑥ 移除 work_reg
↓
合并 bits → meas_result (整数)
↓
shor_postprocess → period r → factors p, q
4.5 经典后处理(第 166–196 行)¶
def shor_postprocess(meas: int, size: int, a: int, N: int) -> Tuple[int, int]:
# ① 找最佳分数近似 y/Q
r, c = find_best_fraction(y, Q, N)
# ② 验证 r 的有效性(偶数、≠ -1 mod N)
check_period(r, a, N)
# ③ 提取因子
a_exp_r_half = general_expmod(a, r // 2, N)
p = math.gcd(a_exp_r_half + 1, N)
q = math.gcd(a_exp_r_half - 1, N)
五、QDA 量子离散绝热线性系统求解器¶
5.1 算法概述¶
QDA(Quantum Discrete Adiabatic)利用离散绝热定理求解线性系统 Ax = b,达到 O(κ log(κ/ε)) 的最优规模(κ 为条件数)。
PySparQ 版本按 C++ Walk_s_Tridiagonal 和 Walk_s_via_QRAM 的寄存器级结构实现:矩阵块编码、StatePrepViaQRAM、Hadamard_Int_Full、反射、受控旋转和全局相位都由 Python 侧调用底层 primitive 组合完成。它不会把整个 QDA solver 作为一个 C++ 绑定来绕过 Python 实现。当前 qda_solve() 会执行量子 walk 序列;由于测量和 post-selection 读出尚未接上,运行完成后会显式抛出 RuntimeError,避免用经典 np.linalg.solve 掩盖算法路径中的错误。
核心思路:
H(s) = (1-f(s))·H₀ + f(s)·H₁ (插值哈密顿量)
W_s = R · H_s (量子游走算子)
通过对 s 离散化执行 W_s 序列,使系统从 |b⟩ 演化到 |x⟩
5.2 插值函数 f(s) 的实现(qda_solver.py 第 41–72 行)¶
def compute_fs(s: float, kappa: float, p: float) -> float:
"""
来自 PRX Quantum 论文 Eq.(69):
f(s) = κ/(κ-1) * (1 - (1 + s(κ^(p-1) - 1))^(1/(1-p)))
"""
if kappa == 1:
return s
kappa_p_minus_1 = kappa ** (p - 1)
inner = 1 + s * (kappa_p_minus_1 - 1)
exponent = 1 / (1 - p)
result = kappa / (kappa - 1) * (1 - inner ** exponent)
return max(0.0, min(1.0, result))
对应 C++ QDATest.cpp 第 410–413 行中的调用:
WalkSequence_via_QRAM_Debug(&qram_A, &qram_b, mat, b, ...,
steps, kappa, p, data_size, rational_size, ...)(state);
5.3 块编码 H(s) 的实现(qda_solver.py 第 196–314 行)¶
BlockEncodingHs 类实现插值哈密顿量的块编码,对应 C++ 中的 Walk_s_via_QRAM 操作。核心操作序列(第 248–308 行):
def __call__(self, state: ps.SparseState) -> None:
ps.Hadamard_Bool(self.anc_3)(state) # H
self.enc_b.dag(state) # 状态准备逆操作
ps.X_Bool(self.anc_1, 0)(state) # X
ps.Reflection_Bool(self.main_reg, True) # 反射算子(关于 |0⟩)
.conditioned_by_all_ones([self.anc_1, self.anc_3, self.anc_4])(state)
ps.X_Bool(self.anc_1, 0)(state)
self.enc_b(state) # 状态准备
# 旋转序列:R_s(f(s))
ps.X_Bool(self.anc_4, 0)(state)
ps.Rot_Bool(self.anc_2, self.R_s).conditioned_by_all_ones(self.anc_4)(state)
...
self.enc_A.conditioned_by_all_ones([self.anc_1, self.anc_2])(state) # 块编码 A
5.4 QRAM 数据准备的完整流程(对应 QDATest.cpp 第 356–391 行)¶
# Step 1: 将浮点矩阵/向量量化为整数
conv_A = scaleAndConvertVector(mat, exponent=15, data_size=50)
conv_b = scaleAndConvertVector(b, exponent=15, data_size=50)
# Step 2: 构建 QRAM 树结构
data_tree_A = make_vector_tree(conv_A, data_size)
data_tree_b = make_vector_tree(conv_b, data_size)
# Step 3: 建立 QRAM 电路
addr_size = log_column_size * 2 + 1 # 比 data 多 1 bit(用于归一化)
qram_A = ps.QRAMCircuit_qutrit(addr_size, data_size)
qram_A.set_memory(data_tree_A)
qram_b = ps.QRAMCircuit_qutrit(log_column_size + 1, data_size)
qram_b.set_memory(data_tree_b)
# Step 4: 添加寄存器
main_reg = ps.AddRegister("main_reg", ps.UnsignedInteger, log_column_size)(state)
anc_UA = ps.AddRegister("anc_UA", ps.UnsignedInteger, log_column_size)(state)
anc_4 = ps.AddRegister("anc_4", ps.Boolean, 1)(state)
anc_3 = ps.AddRegister("anc_3", ps.Boolean, 1)(state)
anc_2 = ps.AddRegister("anc_2", ps.Boolean, 1)(state)
anc_1 = ps.AddRegister("anc_1", ps.Boolean, 1)(state)
5.5 旋转矩阵的构造(qda_solver.py 第 74–95 行)¶
def compute_rotation_matrix(fs: float) -> List[complex]:
"""
旋转矩阵 R_s:
R_s = 1/√((1-f_s)² + f_s²) * [[1-f_s, f_s], [f_s, f_s-1]]
"""
sqrt_N = 1.0 / math.sqrt((1 - fs) ** 2 + fs**2)
return [
complex(sqrt_N * (1 - fs), 0),
complex(sqrt_N * fs, 0),
complex(sqrt_N * fs, 0),
complex(sqrt_N * (fs - 1), 0),
]
5.6 Dolph-Chebyshev 过滤(qda_solver.py 第 102–189 行)¶
用于提高 QDA 解的精度:
def dolph_chebyshev(epsilon: float, l: int, phi: float) -> float:
beta = math.cosh(math.acosh(1.0 / epsilon) / l)
return epsilon * chebyshev_T(l, beta * math.cos(phi))
对应 C++ QDATest.cpp 第 550–566 行的滤波步骤:
int l_ = static_cast<int>(floor(kappa * log(2.0 / epsilon_)));
vector<double> weights = ComputeFourierCoeffs(epsilon_, l_);
// 构建权重 QRAM → 应用 LCU
5.7 C++ 三对角生产路径:Walk_s_Tridiagonal + GetOutput 后选择¶
三对角情形的 C++ 生产路径位于 SparQ_Algorithm/include/DiscreteAdiabatic/qda_tridiagonal.h:三对角 Poiseuille 矩阵的插值哈密顿量 H(s) 以算术方式块编码(Walk_s_Tridiagonal),调度 f(s) 离散化为 ceil(rate * 2305 * kappa) 个 walk 步,解向量由 GetOutput 后选择提取(对 Thomas 参考解计算 res_dir / res_opt / 保真度 / 成功概率)。复杂度遵循离散绝热 O(κ log(κ/ε)) 规模——步数越多收敛越深而非存在硬底:dim256 下 3688 步的 rate-0.1 调度终值 res_dir 3.1e-2,而全程 40568 步生产调度收敛到 5.9485e-4(保真度 1.000000,成功概率 1.0)。
生产基准 Experiments/QDA/QDA_Poiseuille/PoiseuilleQDABench.cu(可执行文件 Experiment_PoiseuilleQDABench_cuda;CLI 与产物 schema 和 CKS bench 完全一致)在单张 A800 上验证该路径至 2^20 维——三跑生产矩阵终值见 docs/verification/v1d-qda-linsolver-a800.md。其 2026-10-21 补篇给出 --czEps(ClearZero)阈值的维度自适应方法:ClearZero 按 |振幅|² < eps 裁剪,解分支出生单态幅值 ≈ sqrt(2e-6/n) 且随调度细化(ds = 1/步数)线性缩小,应使 sqrt(czEps) 低于出生幅值——可用范围 1e-16~1e-22(canonical 1e-16,经三跑矩阵验证提取读数最干净);默认 1e-14 下解分支自 2^19 维起出生即被剪(实测出生幅值:2^17 2.9e-7 / 2^18 1.5e-7 存活,2^19 7.4e-8 / 2^20 3.7e-8 被剪,断点 1e-7)。
六、CKS 量子线性系统求解器(Childs-Kothari-Somma)¶
6.1 算法概述¶
CKS 算法利用 Chebyshev 多项式逼近和量子游走,在稀疏矩阵条件下达到 O(κ log(κ/ε)) 的复杂度,比 HHL 类算法有更好的常数因子。
PySparQ 版本同样只通过底层 primitive 复刻 C++ HamiltonianSimulationTest.cpp 的量子游走路径。Python 的 SparseMatrix 使用 C++ 同款紧凑 QRAM 布局,TOperator、QuantumBinarySearch_Fast、GetRowAddr、GetDataAddr、GetQWRotateAngle_Int_Int_Int、CondRot_Fixed_Bool、QRAMLoad 和寄存器交换等步骤按 C++ 顺序组合;没有绑定完整 C++ CKS solver,也不暴露用户传入 Python function 的旧泛化 CondRot API。
核心流程:
1. Chebyshev 多项式系数 c_j = erfc((j+0.5)/√b) * 2
2. 构造量子游走算子 W = T† · P_0 · T · Swap
3. LCU: Σ_j c_j W^(2j+1) 逼近 1/A
6.2 Chebyshev 系数的实现(cks_solver.py 第 41–127 行)¶
class ChebyshevPolynomialCoefficient:
def __init__(self, b: int):
# b = κ² log(κ/ε),由 LCU_Container 在初始化时计算
self.b = b
def coef(self, j: int) -> float:
"""第 j 步的 Chebyshev 系数"""
if self.b > 100:
# 大 b 值:使用渐近近似(erfc)
return math.erfc((j + 0.5) / math.sqrt(self.b)) * 2
else:
# 小 b 值:精确计算
ret = 0.0
for i in range(j + 1, self.b + 1):
ret += self.C(2 * self.b, self.b + i)
return ret * 4
def sign(self, j: int) -> bool:
"""奇数步为负(加负号)"""
return (j & 1) == 1
def step(self, j: int) -> int:
"""第 j 步的游走步数 = 2j + 1"""
return 2 * j + 1
对应 C++ HamiltonianSimulationTest.cpp 第 139–149 行:
auto test_chebyshev_polynomial_coef() {
ChebyshevPolynomialCoefficient chebyshev_obj(b);
for (size_t j = 0; j <= 64; ++j)
fmt::print("j={}, coef={}\n", j,
chebyshev_obj.coef(j) * (chebyshev_obj.sign(j) ? -1 : 1));
}
6.3 稀疏矩阵表示(cks_solver.py 第 225–340 行)¶
@dataclass
class SparseMatrixData:
n_row: int # 行数
nnz_col: int # 每列最大非零元素数
data: List[int] # 扁平化矩阵数据(量化后整数)
data_size: int # 量化位数(通常 32)
positive_only: bool # 矩阵是否全正(决定旋转矩阵形式)
sparsity_offset: int # QRAM 稀疏寻址偏移
class SparseMatrix:
@classmethod
def from_dense(cls, matrix: np.ndarray, data_size: int = 32,
positive_only: bool = None) -> "SparseMatrix":
# ① 检测正性
# ② 归一化 + 量化
Amax = 2 ** (data_size - 1) - 1
scaled = matrix / max_val * Amax
# ③ 转两补码(负数)
# ④ 计算 nnz_col
对应 C++ SparseMatrix 类(hamiltonian_simulation.h)和 generate_simplest_sparse_matrix_unsigned_2()。
6.4 量子游走的实现(cks_solver.py 第 637–710 行)¶
class QuantumWalk:
"""
W = T† · P_0 · T · Swap
T: 状态准备算子(|j⟩|0⟩ → Σ_k √(A_jk/‖A_j‖)|j⟩|k⟩)
P_0: 相位反射(关于 |0⟩ 态)
Swap: 行列交换
"""
def __call__(self, state: ps.SparseState) -> None:
# Tdagger
t_op.dag(state)
# 相位反射
ps.ZeroConditionalPhaseFlip(
[self.b1_reg, self.k_reg, self.b2_reg, self.k_comp_reg]
)(state)
# T
t_op(state)
# Swap 行列
ps.Swap_General_General(self.j_reg, self.k_reg)(state)
ps.Swap_General_General(self.b1_reg, self.b2_reg)(state)
ps.Swap_General_General(self.j_comp_reg, self.k_comp_reg)(state)
对应 C++ HamiltonianSimulationTest.cpp 第 116–118 行:
for (int i = 0; i < 99; ++i)
QuantumWalk(qram, j, b1, k, b2, j_comp, k_comp, ...)(system_states);
CKS 的 fidelity 测试与 C++ automatic_Chebyshev_test 对齐时,需要按 C++ 逻辑只比较 post-selection 后的目标寄存器,并使用 SparseMatrix 实际编码出的稠密矩阵表示(包含 nnz_col 归一化),不能直接拿原始输入矩阵 A / ||A|| 做目标态。
6.5 LCU 容器(cks_solver.py 第 843–930 行)¶
class LCUContainer:
def __init__(self, mat, kappa, eps, qram=None):
# b = κ² log(κ/ε) — 决定 Chebyshev 展开项数
self.b = int(kappa * kappa * (math.log(kappa) - math.log(eps)))
# j0 = √(b log(4b/ε)) — 截断点
self.j0 = int(math.sqrt(self.b * (math.log(4 * self.b) - math.log(eps))))
def iterate(self):
j, a = 0, 0.0
while j <= self.j0:
if j != 0:
self.walk.step(self.step_state)
coef = self.chebyshev.coef(j)
sign = self.chebyshev.sign(j)
a += coef
self._add_state(self.step_state, coef, sign)
j += 1
对应 C++ LCU_Container_NoiseFree(HamiltonianSimulationTest.cpp 第 275–326 行):
obj.ExternalInput<Hadamard_Int>(addr_size); // Hadamard 初始化
while (obj.Step()) {
auto [state, success_rate] = obj.PartialTrace_Nondestructive();
double fidelity = get_fidelity(m, target_result);
// 记录每步成功率和保真度
}
6.6 QRAM-free 直接 Oracle 路径:TridiagOracle1/2 + T_Tridiagonal¶
对常对角三对角矩阵 A,每个矩阵元素都可算术求出,因此 CKS walk 的两个 QRAM 表 Oracle 可以替换为直接算术 Oracle(SparQ_Algorithm/include/hamiltonian_simulation_tridiagonal.h,CPU + CUDA):TridiagOracle1/2 逐位复刻 QRAM 电路的复合寄存器映射——元素加载是对计算出的存储字做 XOR,槽位↔列转换是范围测试加行地址加减,垃圾分支与 QRAM 路径一致地标记进 k_comp——从而完全去掉 QRAM 电路。T_Tridiagonal 是配套的态制备算子,ChebyshevInverseCoefficients 在精确量化的 walk 谱上以配置点最小二乘拟合逆级数 1/x ~ Σ d_j T_{2j+1}(x)(原生二项式尾系数族在本用例收敛底约 0.2–0.4);符号约定由 D 变换处理(TridiagParityPhase,A⁻¹|b⟩ = D|A|⁻¹D|b⟩)。
单张 A800 上的 2^20 Poiseuille 生产(基准 Experiments/CKS/CKSPoiseuilleBench.cu,可执行文件 Experiment_CKS_PoiseuilleBench_cuda,构建参数 -DCACHED_REGISTER_SIZE=16):方向残差 0 ≤ 1e-6(640/1024 项提前终止)、保真度 1.0000000000、成功概率 4.75e-2、20,971,512 个 walk 基态、2682 s;dim16/dim64 成功概率与 CPU 参考逐位一致。构造与验证细节见 docs/verification/v1e-cks-direct-oracle-linsolver.md。
七、GHZ 态生成(待实现)¶
7.1 C++ 实现解析¶
C++ GHZTest.cpp(第 26–72 行)的 GHZ 态生成逻辑极其简洁:
// 寄存器布局:ctrl (1 bit) + main registers (分块,每块 ≤ 64 bits)
// 设 nqubit = 65,则:quotient = 1, remainder = 0
// 实际布局:ctrl(1) + main(64)
FlipBools("ctrl")(state); // ctrl → |1⟩
Hadamard_Bool("ctrl")(state); // H → (|0⟩+|1⟩)/√2
// 对每个主量子比特应用受控 X(ctrl=1 时翻转)
for (int i = 1; i < remainder + 1; i++)
X_Bool("main", i-1).conditioned_by_all_ones("ctrl")(state);
for (auto reg : reg_names)
FlipBools(System::get(reg)).conditioned_by_all_ones("ctrl")(state);
生成的态:(|0...0⟩ + |1...1⟩)/√2(nqubit 个量子比特的 GHZ 态)
7.2 Python 转译方案¶
def ghz_state(nqubit: int) -> ps.SparseState:
"""生成 GHZ 态:(|0...0⟩ + |1...1⟩)/√2"""
ps.System.clear()
state = ps.SparseState()
# 处理 > 64 比特的情况(寄存器分块)
quotient, remainder = divmod(nqubit - 1, 64)
ctrl = ps.AddRegister("ctrl", ps.UnsignedInteger, 1)(state)
# 添加主寄存器(每块最多 64 位)
main_regs = []
for k in range(1, quotient + 1):
reg = ps.AddRegister(f"main{k}", ps.UnsignedInteger, remainder or 64)(state)
main_regs.append(reg)
if remainder != 0:
main_reg = ps.AddRegister("main", ps.UnsignedInteger, remainder)(state)
main_regs.append(main_reg)
# GHZ 电路
ps.X_Bool("ctrl", 0)(state) # |0⟩ → |1⟩
ps.Hadamard_Bool("ctrl")(state) # (|0⟩+|1⟩)/√2
for reg in main_regs:
for pos in range(ps.System.size_of(reg)):
ps.X_Bool(reg, pos).conditioned_by_nonzeros("ctrl")(state)
return state
八、实现原则总结¶
8.1 量子算法转译的七大原则¶
原则一:寄存器先行,状态跟随
# 错误:状态在寄存器之前创建
state = ps.SparseState()
addr = ps.AddRegister("addr", ...) # ← 错误顺序
# 正确:先定义寄存器体系,再创建状态
ps.System.add_register("addr", ps.UnsignedInteger, n_bits)
state = ps.SparseState() # 或 ps.SparseState() 自动继承已注册的寄存器
原则二:临时寄存器用完即删
# GroverOracle 每次创建 compare_less/equal,Oracle 返回前删除
compare_less = ps.AddRegister("compare_less", ps.Boolean, 1)(state)
# ... 使用 compare_less ...
ps.RemoveRegister(compare_less)(state) # 防止状态空间指数膨胀
原则三:条件操作链式调用
# 所有条件操作均返回 self,支持链式
op = ps.ZeroConditionalPhaseFlip([cond_reg])
op.conditioned_by_nonzeros(other_reg)(state) # 多次加条件
# 对应 C++ 中:
# X_Bool("ctrl", 0).conditioned_by_all_ones("ctrl")(state);
原则四:自伴算子用 .dag() 逆操作
# QRAMLoad, Hadamard, Swap — 自伴(U = U†)
ps.QRAMLoad(qram, addr, data)(state) # 前向
ps.QRAMLoad(qram, addr, data)(state) # 逆操作(同一操作)
# 一般算子
t_op.dag(state) # 逆操作
原则五:浮点量化是量子-经典接口的关键
# QDA/QDA: 浮点矩阵 → 定点整数
# 量化因子:2^exponent,exponent 通常取 15(保证精度)
Amax = 2 ** (data_size - 1) - 1
scaled = matrix / max_val * Amax # 归一化到 [-Amax, Amax]
int_data = scaled.astype(int) # 量化
原则六:自顶向下,先算法后实现
正确顺序:
① 理解算法数学公式(Grover 迭代 / Shor 相位估计 / Chebyshev 展开)
② 定义寄存器角色(主寄存器、辅助寄存器、精度寄存器)
③ 写出算法主体流程(Python 函数或类)
④ 填入各步对应的 PySparQ 操作
错误顺序:
① 直接从 C++ 代码逐行翻译
② 忽略寄存器长度设计导致溢出
原则七:测量结果的概率归一化
# PartialTrace 返回的 prob 是未归一化的,需要处理
prob_inv0 = PartialTraceSelect({ anc_UA, anc_2, anc_3 }, {0, 0, 0})(state)
prob0 = (1.0 / prob_inv0) ** 2 # 归一化得到成功概率
# 对应 C++ QDATest.cpp 第 415–416 行:
# double prob_inv0 = PartialTraceSelect({anc_UA, anc_2, anc_3}, {0, 0, 0})(state);
# double prob0 = (1.0 / prob_inv0) * (1.0 / prob_inv0);
8.2 常见寄存器配置一览¶
算法 |
主寄存器宽度 |
数据寄存器宽度 |
Ancilla 数量 |
特殊寄存器 |
|---|---|---|---|---|
Grover |
ceil(log2(N)) |
64 |
2 (compare flags) |
search(target) |
Shor |
2×n_bits(N) |
— |
1 (work qubit) |
ancilla (模幂结果) |
QDA |
ceil(log2(n)) |
50 |
4 (anc_1~anc_4) |
anc_UA (块编码) |
CKS |
ceil(log2(n_row)) |
32 |
4 (b1,b2,j_comp,k_comp) |
sparse_offset |
GHZ |
ceil(log2(n)) |
— |
0 |
ctrl (1 bit) |
九、缺失算法的实现路线图¶
9.1 QFT(优先实现)¶
C++ 有完整的 QFT_Full() 和 QFT() 实现(SparQ/include/qft.h),转译简单:
def qft(state: ps.SparseState, reg: str) -> None:
"""对应 C++ QFT("main")(state)"""
n = ps.System.size_of(reg)
for i in range(n):
ps.Hadamard_Bool(reg, i)(state)
for j in range(i + 1, n):
ps.CPhase_Bool(reg, j, i, math.pi / (2 ** (j - i)))(state)
def inverse_qft(state: ps.SparseState, reg: str) -> None:
"""逆 QFT:反向迭代受控相位"""
n = ps.System.size_of(reg)
for i in reversed(range(n)):
for j in reversed(range(i + 1, n)):
ps.CPhase_Bool(reg, j, i, -math.pi / (2 ** (j - i)))(state)
ps.Hadamard_Bool(reg, i)(state)
9.2 GHZ(次优先)¶
参见第 7.2 节的转译方案,实现工作量小且逻辑清晰。
9.3 QCNN(需先恢复 C++)¶
Experiments/QCNN/QCNNTest.cpp 目前被 #if false 禁用,需先:
修复 C++ QCNN 实现
在
PySparQ/pysparq/algorithms/qcnn.py中转译
十、给后续开发者的经验总结¶
从 C++ 到 Python 不是逐行翻译:理解算法的数学本质(Grover = 振幅放大、Shor = 相位估计、CKS = Chebyshev 逼近),用 Python 的思维重写。PySparQ 的
CustomArithmetic等接口比 C++ 版本更简洁,直接传入 Python lambda 即可。寄存器分块是超大量子比特系统的关键:超过 64 比特时,需要像 C++ GHZTest 那样将寄存器分成多个
UnsignedInteger子块(每块 ≤ 64 位)。Python 层通过命名约定("main1","main2")和FlipBools(System::get(reg))实现。稀疏态优化的核心是零振幅剪枝:PySparQ 的
SparseState仅存储非零振幅,ClearZero()操作在每步游走/Chebyshev 迭代后调用,防止状态数爆炸。这是 Grover(O(√N) 状态增长)和 CKS(O(κ) 状态增长)能处理大问题的关键。测试先于实现:参考
test_doc_examples.py中的模式,用 pytest 验证各子模块的正确性,再组装完整算法。单元测试覆盖:Oracle(振幅翻转正确性)、扩散(关于叠加态的反射)、量子游走(Chebyshev 逼近精度)。噪声模型的可组合性:C++ 测试中的
set_noise_models()调用在 PySparQ 中等价于:
qram = ps.QRAMCircuit_qutrit(...)
qram.set_noise_model("depolarizing", 1e-4) # 对应 C++ qram->set_noise_models(...)
这对评估真实硬件上的算法行为非常重要。