Kaggle竞赛可验证量子电路编译文档

1. 项目概况与目标

1.1 项目简介

给定三个真实量子算法子程序的固定规格,通过电路重构、数值优化与参数搜索把它们的容错成本尽可能压低,并用官方提供的经典验证器证明电路仍然算对。

具体来说,项目在 kickmix 电路模型下分别处理三个成本主导子程序(Benchmark I 的倒数平方根相位电路、Benchmark II 的 Reed–Solomon 译码器、Benchmark III 的化学哈密顿量块编码),工作内容包括:解析规格与验证器、复现官方基线、重构电路架构、离线拟合定点系数、构建可逆电路并逐位验证、最后通过排行榜提交闭环。

项目覆盖范围:

比赛本身的信息(主办方、奖池、赛程、三个基准的规模参数、提交格式与评分规则、奖项设置)见第 2 章;验证框架见第 3 章;三个 benchmark 的具体工作分别在 5、6、7 章展开。

1.2 项目目标与完成情况

项目在启动时设定了「工程闭环」与「三个 benchmark 各自改进」两类目标,度量方式以官方验证器实测成本为准:

为实现这些目标,项目采用了四条基本策略:

1. 先建真值:优化之前先用官方验证器复现三个基线的分数,确认本地环境与线上一致;
2. 双向验证:任何候选先在本地跑官方验证器,通过后才消耗提交配额,云端 Grader 复核;
3. 目标校准:用公开参考解的真实成本(本地实测)设定每个 benchmark 的上限与差距;
4. 负结果归档:失败的技术路线同样记录,避免重复投入与人力的浪费。

1.3 主要结果

排行榜提交记录:

1.4 报告结构

2. 比赛概况

2.1 赛事信息

赛事目标可以用一句话概括:在固定的问题规模上,把三个真实量子算法中子程序的容错成本尽可能压低,并用公开的经典验证器证明你的电路仍然算对。参赛者不需要量子物理背景,只需要会写电路、会做数值优化——比赛官方的说法是 "reducing the resources required for quantum applications"。

2.2 三个基准

比赛固定三个 benchmark,每个都是一个"成本主导子程序"的孤立版本,问题规模固定、不可换题:

三个基准共享同一套 kickmix 电路模型与同一个验证思路(见第 3 章),但成本函数与失败预算不同:B1 要求每个测试输入都通过,B2 允许少量失败并计入重复开销,B3 则把误差容限做成硬性接受门槛。

2.3 提交与评分规则

提交物是单个 zip 压缩包,内部固定结构:

submission.zip├── invsqrt.kmx  或  invsqrt.kmb# Benchmark I 电路├── dqi.kmx      或  dqi.kmb# Benchmark II 电路└── dfthcsos/    ├── angle_k_0.km[xb] … angle_k_.km[xb]# Benchmark III 的 ANGLE 电路族    └── submission.npz# 分解参数与 Givens 树

• 电路格式为 kickmix 文本(.kmx)或二进制(.kmb),两者等价;
• 评分时 Graders 用比赛数据里的验证器对每份提交逐 benchmark 模拟,约需 45 分钟;
• 同一份提交会在公开/私有两个 split 上各验证一次,每个 split 使用独立的私有盐值,因此同一份电路在两个 split 上的分数可能略有差异;
• 单项分数为「基线成本 / 提交成本」,总分是三项的几何平均,基线提交恰为 1.0。

2.4 奖项设置

此外比赛按 Kaggle Featured 竞赛惯例授予积分与奖牌。值得注意的是,附加奖共 $50,000,其中两项(Task Performance 与 Milestone)要求公开方案或 notebook——这也是本报告与项目代码选择开源归档的原因之一。

2.5 开放资料与本地验证

比赛官方把验证器源码(invsqrt / dqi / dfthcsos 三套)与 kickmix 运行时随数据一起下发,本地即可完成与线上完全一致的打分:

官方同时发布了 metric 实现(competition metric notebook),其逻辑与本地验证器一致:每个 split用自己的盐值跑三个验证器,再对「基线成本 / 实际成本」取几何平均。这一点让参赛者可以在本地完全复现线上评分,也是本工作能够高频迭代的前提。

3. 验证框架

3.1 问题定义

容错量子算法的成本主要由少数子程序决定(整数算术、查表、译码)。这些子程序可以写成kickmix 电路:仅由可逆经典门、对角相位门与基于测量的 uncompute 组成。对任意计算基输入,电路输出仍是单一计算基状态(至多乘一个相位),因此经典模拟时间与门数成正比,而非与 2ⁿ 成正比。

3.2 kickmix 指令集

HMR 对目标量子比特(当它持有 f(x) 时)产生随机相位 kickback:

|x⟩|f(x)⟩ --HMR--> (-1)^(b·f(x)) |x⟩|0⟩,   b ∈ {0,1} 均匀随机

当 b=1 时可用经典控制的 CZ/CCZ/NEG 修复相位,这是测量式 uncompute(MBU)省门的关键。

3.3 验证协议

1. 对电路 .kmb 二进制序列化计算 SHA-256,与比赛私有盐混合后作为 PRNG 种子;
2. 通过 Fiat–Shamir 方式生成测试输入(选手无法针对固定测试集过拟合);
3. 逐 shot 检查三条件:输入寄存器还原;所有 scratch 归零;累计相位在容差内;
4. 失败率 ε 用 Clopper–Pearson 单侧上界 ε⁺(置信度 1−2⁻¹²⁸)处理:   全通过时 ε⁺ ≈ 88.7/N,部分 benchmark 允许少量失败并计入重复开销 R(ε⁺)。

3.4 评分体系

三个任务各自成本函数:

总分 = (∏ cost_ref / cost)^(1/3)(几何平均,基线提交为 1.0)。

4. 工程基础设施

4.1 运行环境

ABI 问题:首次导入报 undefined symbol: PyObject_ClearManagedDict。该符号由 Python 3.13 导出(3.12 无),说明 .so 面向 3.13 编译,故需要使用 3.13 环境。

4.2 提交管道(网络受限环境下的「内核代理」方案)

网络实测:api.kaggle.com 可达;www.googleapis.com 不可达(超时);storage.googleapis.com 可建立连接但传输中被重置。而提交必须经 Google Cloud Storage,因此原生 CLI/SDK/resumable-upload 均无法完成上传。

解决方案:把构建与提交都搬进 Kaggle 网络内的内核。

实现要点:

1. kernels.KernelsApiService.SaveKernel
    以 纯 JSON 内联源码 方式创建脚本内核   (不经过文件上传),同时指定 competition_sources 以挂载比赛数据(含 kickmix 与验证器);
2. CreateKernelSession
    触发执行;若返回 409(已有会话在跑),先CancelKernelSession 再重试;
3. 内核侧执行:写入内联源码 → 用 kickmix 现场构建三个 benchmark 的电路 →   打包 submission.zip → 调用官方提交 API → 打印 SUBMITTED OK;
4. 本地轮询 GetKernelSessionStatus 与 ListKernelSessionOutput 获取日志。

验证记录:用官方 sample_submission 走完整管道提交,排行榜分数 1.00000,与文档一致,确认管道不改变提交内容。

4.3 基线校准

在任何优化前,先本地复现三个官方基线分数以确认环境一致性:

5. Benchmark I:invsqrt(1/√x 相位)

5.1 问题规约

基准 I 要求对每个输入 x 实现一个相位门,精确规格如下:

|x⟩|0…0⟩   →   exp( 2πi · β / √x ) |x⟩|0…0⟩x ∈ [1, 3,133,452],β = 1

5.2 官方基线

数据流:成对前导零移位归一化 → 4 段三次多项式(1,1.5)、(1.5,2)、(2,3)、(3,4)加一步 Newton–Raphson → 逐位 Z_POW 相位 → 逆序 uncompute。

成本分解(按阶段,双向前向估算):Horner 三次求值 ≈ 798、平方 ≈ 340、M·y0² ≈ 1,065、3−z 校正 ≈ 30、y0·(3−z) ≈ 748、归一化/选择 ≈ 13。

5.3 v2:分区 + 降阶(中间版本)

设计:32 个 dyadic 区间(由 x_norm 高位直接选择,无需比较器)、每段二次多项式(离线 LP 最小化最大相对误差)、Newton–Raphson 一步、QROM 式查表加载系数(segment-tree unary iteration,叶子处异或系数后即时 MBU 清理)。

实现过程中修正的问题:(a) 区间选择基址计算(base = 2^B − 有效区间数);(b) segment-tree 的 AND 生命周期必须即时清理,否则两个半区共享 ancilla 会破坏状态;(c) 寄存器宽度必须按 p = y0(3−z) 的实际上界留位(x=1 时 p 接近 2^(wp+1))。

该版本已提交并得到 publicScore 1.08475。

5.4 v3:符号数字(centered signed-digit)架构

这是本项目 B1 的最终方案。核心数据流:

s  = 21 − floor(log2 x)            归一化移位(0..21)xn = x << s                        xn ∈ [2²¹, 2²²)e  = s & 1                         奇偶a  = (xn >> 14) & 127              128 段索引d  = xn & 0x3FFF                   14 位局部坐标1/√x = 2^(s/2) · 2^(-10.5) / √M,  M = xn · 2^-21

段内用符号数字表示残差:sig_i = 2·bit_i(d) − 1,于是 Σ sig_i 2^(i−21) = 2(d·2⁻²¹ − center),中心值被吸收进系数。二次多项式在符号数字上求值,乘法退化为有条件加/减。

电路实现要点:

精度配置与验证:

系数拟合方法:按段在精确可达域上做加权 minimax(Lawson 迭代)拟合,再做整数搜索。可达域结构:奇偶性 e=1 的段只有偶数 d 可达;e=0 且 a≥64 的段只有 d ≡ 0 (mod 4) 可达(a=63 段受 x 上界限制)。在该配置下,本实现与公开最优系数表逐位一致(0/256 段不同),可视为同一数学最优解的两个独立收敛。

自包含性:构建器不依赖任何外部数据文件;运行时重新拟合系数并构建,产物SHA-256 与已验证电路逐位一致,可在 Kaggle 内核中重建。

5.5 参数消融(全部失败,记录如下)

结论:(F2,F1,FYR,GY) = (8,19,27,1)、drop row 5 是该架构族内的验证最优配置。更高档位(63 qubits / 108.5k 得分)依赖锚定相位流 + 压缩查表 + 23 线归一化等30 余级逐级等价替换,需要 SAT 级别的等价性证书,本轮未实施。

6. Benchmark II:DQI(Reed–Solomon 译码,进行中)

6.1 问题规约

6.2 官方基线与目标架构

官方基线为 Proos–Zalka 同步 EEA 译码器:1,893 qubits、5,725,461 Toffoli、R = 1.191、得分 2.44 × 10¹³。

目标架构(Berlekamp–Massey + 半次 Bézout / Ψ 路线):

资源预算参考(公开参考实现):442,397 T / 1,837 Q(论文);工程移植版 533,034 T / 888 Q,本地实测得分 5.05 × 10¹¹(48.3×)。

6.3 反向轮分支判定(关键正确性问题)

BM 反向轮需要判定每一轮正向时执行的是 replace 还是 retain。早期用 τ 系数判据rep = (τ₀≠0) ∧ (d≤0) ∧ (τ₀≠τ₃₅),在小域测试中出现结构性漏判:当 σ₀ = σ₃₅ 时(大域概率 2⁻¹²、小域 2⁻⁴)真 replace 被误杀;另一侧 nrep 轮 τ 循环移位在τ₃₅=τ₃₄≠0 时产生假阳性。

正确规则为栈标签规则,不引用任何 τ 系数:

# 正向轮:push 控制 = d<0(pre-update),栈顶写入轮标签 r# 反向轮开头:d -= 1# 补码后 d[7] = replace OR pushedrt = [stack_top.tag == r]# flip_if_equalrep = d[7] AND NOT rt

全边界情形验证表:

GF(2¹²) 上 280,000 轮模拟:0 错配。

6.4 栈深度与失败预算

历史栈容量与失败率实测(20,000 样本):

栈深度分布:[19714, 283, 3, 0, ...]。选定 caps=2:总 Q ≈ 1,842,失败预算可忽略。

6.5 当前状态

经典模型已 100% 通过(与公开带权重测试样例逐位对拍);电路构建器完成BM 正/反向轮、归一化、Ω 乘积、平方根变换,EEA 与 Chien 扫描收尾中。

7. Benchmark III:DFTHC(FeMoCo 化学,阻塞)

7.1 问题规约

7.2 λ_eff 的严格下界

由 E_gap 分解式 E_gap = −559.132 + 2|Σneg| + ½ΣW²(常数项 = E_upper − ecore + ηβ₁),配合 Λ₁ ≥ 2|Σneg|、Λ₂ ≥ ¼ΣW²(三角不等式)可得:

2Λ − E_gap ≥ 559.132λ_eff = √(E_gap(2Λ − E_gap)) ≥ √(3.914898 × 559.132) = 46.79

即任何合法提交的 λ_eff 不低于 46.79,基线 49.30 距下限仅 5%。因此 B3 的改进必须来自 T·Q(资源压缩),而非 λ_eff。

7.3 分解优化实验

失败原因分析:

1. 特征切片投影的 Gram 主方向与「每组共享 u_b」结构不对齐,大 B 也无法救;
2. 小 L 时受限子空间无法同时容纳主导 Coulomb 对角扇区与 H0(一阶哈密顿量)坐标;
3. (65,60,30) 截断解虽拟合 ε₂ 达标,但 H0 覆盖不足导致 E_gap ≥ 763 Ha,   远超 4 Ha 目标;这不是调参能解决的容量问题。

7.4 QROM 侧分析(证伪两条捷径)

假设:官方成本模型 QR(L, M1) = L/2^k + M1·(2^k−1) 暗示查表成本可降至约 1/3。

分析结论:

1. 该定价对应 QROAM(swap 寄存器)结构:k=3 时需要 2³ × 96 = 768 个 swap qubit   加 108 个寄存器,约 890 qubits,远超 128 qubit 硬限;k=1(192+108)同样超限。
2. 2-地址 banked QROM(差分库)实测:J=5 需 132 qubits(超限 4);J=4 为   110 qubits / 80,332 Toffoli,与朴素 segment-tree 79,480 基本持平,无净收益。
3. 基线 delta 表在 ANF 意义上是密码学式随机函数(每列最多 2,120 项,96 列用满   全部 4,096 个 support),对随机数据 segment-tree 已接近最优。
4. 公开参考的 337-Toffoli/批电路建立在重构后的分解形状上   ((R,B,C) = (6,192,76)、brot=8、A=1,228),配合 XOR-AND DAG 合成器 + SAT 证书,   与基线数据不可迁移。

7.5 结论

B3 的改进必须「分解重构 + 查表合成」联合设计;单独优化 QROM 或单独优化分解都无法在 128 qubit 约束内交付。当前保留基线提交作为兜底。

8. 结果汇总与参考校准

本工作同时把公开参考解按官方验证器在本地复现,得到三个基准的真实上限,用于目标校准:

排行榜进度与项目时间线:

9. 复现说明

9.1 环境

# WSL2 Ubuntu 24.04 + conda-forge Python 3.13python -m pip install numpy scipy ”jax[cpu]” optax# kickmix:使用比赛数据内的 kickmix/kickmix.so(PYTHONPATH 指向该目录)

9.2 数据获取

kaggle competitions download -c google-verifiable-quantum-circuit-compilation -p datakaggle datasets download -d sohier/verifiable-circuit-compilation-starter-kit -p data/starter_kit

9.3 关键命令

9.4 产物

10. 参考

1. T. Khattar et al., Leveraging verifiable structure in quantum circuits to find more   efficient compilations with agentic AI, arXiv:2610.23832
2. A. Gu, A. H. Kemeny, S. F. Yelin, M. D. Lukin, Discovering state-of-the-art quantum   circuits with large language models, arXiv:2610.22367
3. Google Quantum AI, kickmix / Qualtran, Apache-2.0
4. 比赛数据:data/verifiers/*(验证器)、data/metric/metric.py(官方 metric 实现)
5. 公开参考解(用于目标校准,均已用官方验证器本地复现):   - 19.5 分提交包与源码包(vqcc_19_53750 / vqcc_6_17493 public resources)   - VQC Verified Optimization Atlas(kozykappa/quantum-ai-dataset)

项目仓库:github.com/zikuanqi/google-verifiable-quantum-circuit-compilation