Yau Awards Archive 2020 — 2025

Topics选题方案 ／ 计算机奖 ／ K09

K09

纯 CPU 量子线路模拟的可行边界：态矢量法与矩阵乘积态法在 QAOA 线路上的成本交叉点与比特上限标定

推荐优先级：中低（风险偏高）分族：量子计算模拟参赛子类：计算机-量子计算与数值方法资源需求：纯 CPU 笔记本 / 16 GB 内存（内存是唯一硬约束）技能取向：Python + 线性代数 + 数值实验

1 · 研究问题

在一台 16 GB 内存的纯 CPU 笔记本上，态矢量（statevector）模拟与矩阵乘积态（matrix product state, MPS）模拟在量子近似优化算法（QAOA）求解 MaxCut 的线路上，墙钟成本的交叉点位于哪一组参数（比特数 n、层数 p、图的平均度 d）？态矢量法的实际可达比特上限比理论内存上限（2ⁿ × 16 字节）低多少，缺口分别由哪些具体开销（解释器与库的常驻内存、保存态矢量时的副本、门作用时的临时缓冲）贡献？

2 · 研究背景与空白

技术背景。 经典计算机模拟量子线路有两条主流路径。态矢量法显式存储 2ⁿ 个复振幅，每个双精度复数 16 字节，因此内存需求随比特数指数增长，但对任意线路都成立、无近似。矩阵乘积态/张量网络法只存储纠缠结构，成本由"键维"（bond dimension）决定；对低纠缠线路可以远超态矢量法的比特数，但一旦纠缠增长，键维指数上升，反而更慢。QAOA 是这两种方法的天然试验场：p = 1 时纠缠很浅，p 增大时纠缠迅速铺开。这个课题的内存边界必须写清楚且必须自己核实，因为它是整条路线的物理约束：

比特数 n complex128 态矢量（16 B/振幅） complex64（8 B/振幅） 在 16 GiB 机器上的判断
20 16 MB 8 MB 充裕
24 268 MB 134 MB 充裕
26 1.07 GB 0.54 GB 舒适（可保存副本、可并行多组）
27 2.15 GB 1.07 GB 舒适
28 4.29 GB 2.15 GB 可行（保存态矢量的副本会到 8.6 GB，接近上限）
29 8.59 GB 4.29 GB 勉强（不得保存副本，须原地操作）
30 17.18 GB（= 恰好 16 GiB） 8.59 GB 双精度不可行；单精度勉强
31 34.4 GB 17.18 GB 超出范围

即：双精度态矢量在 16 GiB 机器上的绝对上限是 29 比特，实际舒适区是 26–28 比特；改用单精度可上推约 1 比特，但须付出精度代价并在验收标准里量化。这一表格中的每一格都要在项目第 1 阶段用实测内存占用验证，不得直接引用。需核实：Qiskit Aer 在应用多比特门时是否分配临时缓冲、save_statevector 是否产生完整副本——这两项直接决定实际上限比理论值低几比特，也正是本课题研究问题的一部分。

已有工作到哪一步。 Qiskit Aer 文档明确给出"n 比特态矢量占用 2ⁿ 个 16 字节复数"这一公式，并提供 max_memory_mb 参数在超限时报错；Aer 内置了 statevector、density_matrix、matrix_product_state、stabilizer、extended_stabilizer 等多种模拟方法（tensor_network 方法是否要求 GPU 需核实）。QAOA 与 MaxCut 本身是被研究得极为充分的方向，大量工作报告了不同 p 下的近似比与参数优化策略；模拟侧也有大量在 GPU 与 HPC 集群上的性能工作。

空白在于：几乎所有模拟性能研究都在服务器或 GPU 上给出标度，而"一台普通笔记本上这两类方法各自的可行边界与交叉点在哪"这一对学生与教学最有用的问题，没有系统的公开标定。这个空白属于"方法层面的可复现性贡献"——物理与算法结论均已发表，本项目的贡献是一份跨方法的成本前沿与资源判据。这类贡献在计算领域是被承认的，但定位必须讲清楚，否则会被误读为重复工作：本项目不研究 QAOA 好不好用，只研究"在给定资源下能模拟到哪里、用哪种方法"。

3 · 可检验假设

  • H1：在固定截断保真度（≥ 1 − 10⁻⁶）下，MPS 法与态矢量法的墙钟成本交叉点比特数 n*(p) 随 QAOA 层数 p 单调递减：p = 1 时 n*(1) ≥ 26；p = 3 时 n*(3) ≤ 20。若 n*(3) > 24，H1 被否证，说明 QAOA 在中等 p 下的纠缠增长比预期慢得多——这对模拟方法选择是更有利的结论。
  • H2：态矢量法的实际可达比特上限比表中理论值低 1–2 比特，且缺口的主导项是"保存/读取态矢量时的完整副本"而非常驻内存；关闭态矢量保存（只取测量统计）可回收 ≥ 1 比特。若关闭保存后上限不变，说明主导项是门作用的临时缓冲，这是一条对模拟器使用者同样有用的结论。

4 · 量化验收标准

  1. 方法学校验（硬门槛）：三重校验，全部通过方可继续。（a）与自建模拟器逐振幅比对：自行用 NumPy 实现一个直接的态矢量模拟器（约 100–150 行，门作用用张量重塑实现），在 n ≤ 20 的 QAOA 线路上与 Qiskit Aer 的输出逐振幅比较，最大绝对偏差 ≤ 10⁻¹⁰。（b）与解析结果比对：在 n ≤ 16 时用暴力枚举求出 MaxCut 目标函数在 QAOA 输出态下的精确期望值，与模拟测得值比较，偏差 ≤ 10⁻¹²（p = 1 时还可与已发表的解析表达式核对）。（c）MPS 与态矢量的保真度比对：同一线路的 MPS 结果与态矢量结果的态保真度 ≥ 1 − 10⁻⁶。三条任一不过，后续全部结论无效。
  2. 数值收敛检查：MPS 侧必须做键维收敛扫描——对每个 (n, p) 组合扫描至少 5 个键维档位，报告目标函数期望值随键维的收敛曲线与截断误差累计值；明确报告在给定键维下是否真正达到设定的保真度，不得只报最大键维的结果。这是数值模拟类课题的必备项。
  3. 内存标定：用实测（resource.getrusage 峰值 RSS + /proc/self/status，或平台等价接口）逐比特测量实际内存占用，与理论表逐格比对，报告缺口及其归因；每个配置重复 ≥ 5 次报中位数与 IQR。
  4. 基准测试方法学：每个（方法 × n × p × 图）组合重复 ≥ 10 次；固定 CPU 频率、绑核、禁用 Turbo；报中位数与 IQR，不报均值；线程数固定并在正文声明（Aer 默认多线程，须显式设定 max_parallel_threads 以保证可比）。
  5. 双成本口径：交叉点必须同时用等工作量（相同线路、相同精度目标下的墙钟时间）与等墙钟时间预算（固定 60 秒内两种方法各能达到的最大 n 或最小截断误差）两种口径给出，两者不一致时必须讨论。
  6. 样本量：图实例 ≥ 30 个，覆盖至少 3 类（3-正则图、Erdős–Rényi 图两档密度、几何/网格图），每类 ≥ 8 个；比特数覆盖 ≥ 8 个档位；p ∈ {1, 2, 3, 4}。
  7. 可复现性：全部线路生成、模拟、内存标定与统计脚本开源；一键重跑脚本；随机种子写死；QAOA 参数固定为公开的解析或预优化值（不做参数优化——避免把优化器的随机性混入成本测量，这一选择须在正文说明）。

5 · 数据与工具

用途 来源 / 工具
量子模拟器 Qiskit + Qiskit Aer（pip 可装，纯 CPU 版本无 GPU 依赖）；模拟方法用 AerSimulator(method="statevector") 与 method="matrix_product_state"。method="tensor_network" 需核实是否要求 GPU/cuQuantum，若是则不纳入
独立对照模拟器 自行实现的 NumPy 态矢量模拟器（校验用）；可选 qsim/Cirq（Google，CPU 可用）或 quimb（张量网络，纯 Python/NumPy，CPU 友好）作为第三方交叉校验。仅用于校验与对比，不计入本项目贡献
线路与问题实例 QAOA MaxCut 线路自行构造（结构完全公开）；图实例用 NetworkX 生成器（3-正则、Erdős–Rényi、网格）与固定种子；可另取 SNAP 小图的诱导子图作为真实图样本
精确基准 n ≤ 24 时 MaxCut 的精确最优值可由暴力枚举或 ILP（OR-Tools/CBC）求得，用于把模拟结果换算为近似比。仅作参照，不计入贡献
内存与计时 resource.getrusage、psutil、tracemalloc；time.perf_counter；taskset、cpupower
统计与作图 Python + SciPy + Matplotlib
算力 纯 CPU。硬约束见第 2 块的比特上限表。单次 n = 28、p = 3 的态矢量模拟估计数十秒至数分钟（须实测标定）；总工作量约 2 方法 × 8 比特档 × 4 层数 × 30 图 × 10 重复，须靠"先标定单次成本再裁剪参数网格"控制在 60–100 机时内。超出范围：n ≥ 30 的双精度态矢量模拟、密度矩阵（density matrix）方法（内存为 4ⁿ，n = 15 即达 8.6 GB）、任何含噪声模型的多轨迹模拟——三者均须在正文明确声明为超出范围

6 · 方法路径

  1. 装 Qiskit/Aer，跑通官方教程算例；自行实现 NumPy 态矢量模拟器；完成验收第 1 条的三重校验并归档。
  2. 核实工具能力边界（本课题第一优先级）：Aer 的 tensor_network 方法是否需要 GPU；save_statevector 是否产生副本；多比特门是否分配临时缓冲；单精度模式如何开启及其精度代价；max_parallel_threads 的语义。全部以实测内存与文档双重确认，写成一张能力边界表。
  3. 实测标定比特上限：从 n = 20 起逐比特上推，直到出现内存错误或严重换页，记录每一步的峰值 RSS；分别在"保存态矢量"与"仅取测量统计"两种模式下各做一遍（这是 H2 的直接检验）。
  4. 构建实例集与线路生成器，固定 QAOA 参数（使用公开的解析值或文献报告的预优化值，不自行优化）。
  5. 执行 MPS 侧的键维收敛扫描，为每个 (n, p) 确定达到保真度目标的最小键维，记录截断误差累计。
  6. 执行主扫描（两种方法 × 参数网格 × 重复），出成本曲线、交叉点 n*(p)、双成本口径对照表。
  7. 独立交叉校验：（a）用 quimb 或 qsim 复算至少 3 个 (n, p) 组合，验证成本量级与交叉点位置；（b）在另一台内存不同的机器（如 8 GB 或 32 GB）上复测比特上限表，验证"实际上限 = 理论上限 − 缺口"这一关系是否随内存规模成立。

7 · 新颖性边界

本课题不声称：不提出新的模拟算法，不改进 QAOA，不声称任何关于 QAOA 近似比或参数优化的新结论（这一方向文献极多，本项目一律引用不声称），不涉及任何真实量子硬件，不声称"量子优势"相关的任何判断。Qiskit、Aer、quimb、NetworkX 与全部 QAOA 理论均为他人工作，标注为对照基准，不计入本项目贡献。

已有工作完成了什么：Qiskit Aer 文档给出了态矢量的内存公式与多种模拟方法；QAOA 求解 MaxCut 的性能、参数优化与理论分析已有大量公开结果；模拟器的性能标度在 GPU 与 HPC 平台上已被系统研究。丘奖计算机赛道 2023 年铜奖《MNIST Handwritten Digit Classification with Quantum Neural Network》（北京市第一零一中学）是历届获奖中与量子计算最相邻的一项，但它做的是量子神经网络在图像分类上的应用，与本课题的模拟方法学成本标定在对象、方法与判断依据上均不重叠。

本项目的贡献：给出纯 CPU 消费级硬件上的模拟可行边界与方法交叉点的定量标定——包括实测的比特上限及其与理论值的缺口归因、MPS 与态矢量的成本交叉点 n*(p)、以及一份可直接复用的资源判据。这是主结论，属于"方法层面的可复现性贡献"，定位必须在论文摘要第一句就写明，避免被误读为 QAOA 研究。

为什么有价值：量子算法的教学与入门研究绝大多数在个人电脑上进行，而"我这台机器能模拟到多少比特、该用哪种方法"目前只能靠试错。一份带误差棒的可行边界表与交叉点判据，对这一大批使用者是可直接采纳的结果。

风险提示：本路线的最大风险是被误读为"又一个 QAOA 项目"。缓解方式是把 QAOA 严格降格为"提供可控纠缠强度的线路族"，正文中不出现任何关于 QAOA 优劣的论断，全部结论只关于模拟成本。

8 · 决策门槛（go / no-go）

  • 第 4 周：内存上限实测必须完成，且实测表与第 2 块的理论表逐格对上。若实测上限比理论值低 3 比特以上且原因不明，这不是失败而是研究内容——把归因分析正式列为主结论之一（H2 的加强版），但必须在本周确定分析手段（内存剖析工具）。
  • 第 8 周：工具能力边界表必须完成，tensor_network 方法的 GPU 依赖必须核实清楚——这是需要提前确认而非边做边发现的事项。若 Aer 的 MPS 方法在本机不可用或性能异常，降级路径 A：MPS 侧改用 quimb（纯 Python + NumPy，CPU 原生，键维完全可控），主结论框架（两类方法的成本交叉点）完全保留，仅实现来源改变。
  • 第 14 周：三重方法学校验硬门槛。若逐振幅比对偏差 > 10⁻¹⁰，排查门序约定（比特序 little/big endian）、参数符号约定、随机种子三项最常见原因；第 17 周仍不过关则降级路径 B：放弃与 Aer 的逐振幅比对，改以自建 NumPy 模拟器为唯一真值来源（n ≤ 24 内它足够快），Aer 降为被测对象之一而非参照。校验硬门槛替换为"自建模拟器在 n ≤ 16 上与暴力解析结果偏差 ≤ 10⁻¹²"。
  • 第 22 周：键维收敛扫描必须完成。若 MPS 在 p ≥ 2 时键维就爆炸到无法在可行时间内达到保真度目标，降级路径 C：把 p 的范围缩为 {1, 2}，并把研究问题重心从"交叉点"转为"MPS 可用区的边界刻画"——即在 (n, p, d) 空间中标出 MPS 仍优于态矢量的区域及其边界形状。主结论框架保留，且这个刻画本身信息量不低。
  • 第 30 周：主扫描完成且 H1 有明确判定。若进度不足，降级路径 D：图类别从 3 类减为 2 类（3-正则 + Erdős–Rényi），比特档位从 8 个减为 6 个，重复次数保持 10 次不变。
  • 预算裁剪顺序：图类别数 → 比特档位数 → p 档位数（下限 2）→ （绝不裁剪）三重校验、键维收敛扫描与重复次数。
  • 选择前提：仅在学生已具备线性代数基础（张量积、酉算符）、且明确接受"本课题不产出量子算法结论、只产出模拟方法学结论"这一定位时才启动。若学生或家长期待"做量子计算研究"的叙事，须提前说清本课题的实际内容，否则中途改题的风险很高。