一、缘起
今天注册了开物社区账号,做活动中心新手任务时遇到了平台新手教程题:一道最大割(Max-Cut)问题,题目给了一张 10 个节点的图。作为组合优化的经典入门问题,它很适合用来体会如何把问题翻译成 Ising/QUBO 语言。这篇笔记记录我的求解过程,以及随后学习《参数精度适配指南(8bit整数)》时整理的降精度方法要点,给同样刚入门的朋友参考。

二、最大割:题面与建模
最大割问题:给定无向图 G(V,E),把顶点分成两群,使横跨两群的边数(或边权和)最大。用自旋语言描述:给每个顶点 σi ∈ {+1, −1},割值 Z = Σ_{i
三、我的求解过程:笨办法,但可靠
10 个顶点共 2^10 = 1024 种分割,穷举毫无压力。我的做法分三步:
1. 从题目图中精确提取边集:先定位 10 个节点圆心,再对全部 45 个点对沿连线做像素采样,统计线段命中率。真边的命中率接近 1,非边低于 0.3,本图没有介于两者之间的模糊案例,共得到 23 条边;各顶点度数之和 46 = 2×23,交叉验证自洽。
2. 固定顶点 0 在 A 组,枚举其余 9 个顶点的 512 种分组。
3. 逐组计数割边,得最大割值 19;达到最优的分割有两种:A={0,2,5,6,7,9},B={1,3,4,8},以及把 9 挪到 B 组的等价解。
提交后平台判定正确。顺带提醒:新手教程一天只能提交 5 次,提交前建议先自己验证,穷举是最省心的验证方式。

四、真机求解前的功课:8-bit 降精度四种方法
专用量子计算机(SPQC)只支持 8 位有符号整数 [−128, 127] 的系数精度,且该限制作用在最终提交真机求解的 Ising 矩阵上。学习地图《参数精度适配指南(8bit整数)》以 Kaiwu SDK v1.4.0 为例给了四种降精度方法,按适用场景整理:
1. 直接截断 adjust_ising_matrix_precision:系数缩放后取整,适合元素差异较小的稀疏矩阵,简单但可能损失精度;
2. 动态范围压缩 perform_precision_adaption_mutate:整体压缩系数动态范围,让极值落进 8-bit 区间;
3. 变量拆分 perform_precision_adaption_split:把带极端系数的变量拆成辅助变量,适合有极端值的矩阵,代价是问题规模变大;
4. 降低精度装饰类 PrecisionReducer:以装饰类方式包装矩阵,对现有代码侵入最小。
官方文档还有一个容易忽略的点:QUBO 建模阶段不必强行限幅,转换成 Ising 后检查动态范围即可。这与包括我在内的很多新手的第一直觉相反,值得注意。

五、小结
从一道新手题到降精度方法,第一天最大的感受是学习地图的中文文档对新手相当友好。10 节点的最大割穷举仍是标准答案,但规模一大,经典算力就吃紧了——需要专用量子计算这样的新算力,这大概也是这道新手题想传达的。接下来我准备继续过 QUBO 建模与约束处理的教程,有心得再来交流。

一、缘起
今天注册了开物社区账号,做活动中心新手任务时遇到了平台新手教程题:一道最大割(Max-Cut)问题,题目给了一张 10 个节点的图。作为组合优化的经典入门问题,它很适合用来体会如何把问题翻译成 Ising/QUBO 语言。这篇笔记记录我的求解过程,以及随后学习《参数精度适配指南(8bit整数)》时整理的降精度方法要点,给同样刚入门的朋友参考。

二、最大割:题面与建模
最大割问题:给定无向图 G(V,E),把顶点分成两群,使横跨两群的边数(或边权和)最大。用自旋语言描述:给每个顶点 σi ∈ {+1, −1},割值 Z = Σ_{i
三、我的求解过程:笨办法,但可靠
10 个顶点共 2^10 = 1024 种分割,穷举毫无压力。我的做法分三步:
1. 从题目图中精确提取边集:先定位 10 个节点圆心,再对全部 45 个点对沿连线做像素采样,统计线段命中率。真边的命中率接近 1,非边低于 0.3,本图没有介于两者之间的模糊案例,共得到 23 条边;各顶点度数之和 46 = 2×23,交叉验证自洽。
2. 固定顶点 0 在 A 组,枚举其余 9 个顶点的 512 种分组。
3. 逐组计数割边,得最大割值 19;达到最优的分割有两种:A={0,2,5,6,7,9},B={1,3,4,8},以及把 9 挪到 B 组的等价解。
提交后平台判定正确。顺带提醒:新手教程一天只能提交 5 次,提交前建议先自己验证,穷举是最省心的验证方式。

四、真机求解前的功课:8-bit 降精度四种方法
专用量子计算机(SPQC)只支持 8 位有符号整数 [−128, 127] 的系数精度,且该限制作用在最终提交真机求解的 Ising 矩阵上。学习地图《参数精度适配指南(8bit整数)》以 Kaiwu SDK v1.4.0 为例给了四种降精度方法,按适用场景整理:
1. 直接截断 adjust_ising_matrix_precision:系数缩放后取整,适合元素差异较小的稀疏矩阵,简单但可能损失精度;
2. 动态范围压缩 perform_precision_adaption_mutate:整体压缩系数动态范围,让极值落进 8-bit 区间;
3. 变量拆分 perform_precision_adaption_split:把带极端系数的变量拆成辅助变量,适合有极端值的矩阵,代价是问题规模变大;
4. 降低精度装饰类 PrecisionReducer:以装饰类方式包装矩阵,对现有代码侵入最小。
官方文档还有一个容易忽略的点:QUBO 建模阶段不必强行限幅,转换成 Ising 后检查动态范围即可。这与包括我在内的很多新手的第一直觉相反,值得注意。

五、小结
从一道新手题到降精度方法,第一天最大的感受是学习地图的中文文档对新手相当友好。10 节点的最大割穷举仍是标准答案,但规模一大,经典算力就吃紧了——需要专用量子计算这样的新算力,这大概也是这道新手题想传达的。接下来我准备继续过 QUBO 建模与约束处理的教程,有心得再来交流。