1. 课程导入与MaxCut问题定义
欢迎进入《量子MaxCut图割优化应用》课程。在正式接触量子线路、QAOA参数或量子退火之前，我们需要先回答三个基础问题：MaxCut到底在优化什么？它为什么难？量子计算又能在其中扮演什么角色？本章作为全课程的起点，将建立统一的问题语言、数学定义与整体学习路线，为后续30章的技术展开打下共同基础。
一、从一个具体场景认识MaxCut
设想一家公司要在若干城市之间铺设光纤骨干网，城市之间的链路有长有短、成本各异。现在需要把城市分成两个区域集群，使得跨越两个集群的链路总权重最大——跨区链路往往代表需要重点保障的骨干连接，或者代表我们希望最大化保留的通信容量。这就是MaxCut（最大割）问题的典型工程原型。
更一般地，给定一个无向带权图 G = (V, E, w)，其中 V 是顶点集合、E 是边集合、w 是边权。MaxCut要求把顶点集合 V 划分为两个互不相交的子集 (S, V\S)，使得两端分别落在不同子集中的边（称为割边）的权重之和最大。用数学语言表达：
最大化 C(S) = Σ w(i,j)，其中 i ∈ S，j ∈ V\S，(i,j) ∈ E
约束：S ∪ (V\S) = V，S ∩ (V\S) = ∅注意这里有一个重要的约定：划分是对称的，即 (S, V\S) 与 (V\S, S) 是同一个割，目标函数值相同。因此解空间大小为 2^(n-1)，n 为顶点数。这个约定在后续讨论量子态编码和对称性时会反复用到。
二、为什么MaxCut是“难”的
MaxCut是经典的NP-hard问题。直观理解：当顶点数 n 增大时，穷举所有划分的代价呈指数增长。n=30 时约有 5.4 亿种本质不同的划分；n=50 时已超过 5.6×10^14 种。工程中常见的图规模动辄成百上千个顶点，精确求解在可接受时间内不可行。
实践中通常退而求其次，追求近似比。一个著名结论是：Goemans与Williamson基于半正定规划（SDP）松弛加随机超平面取整的算法，对非负权MaxCut可达到约 0.878 的近似比。而量子近似优化算法（QAOA）在理论上的近似性能与电路深度 p 相关，p 增大时近似比可逐步逼近1。这构成了“经典近似—量子近似”对比的第一条线索。
三、MaxCut与伊辛模型、QUBO的等价关系
量子优化算法并不直接“理解”图，它处理的是哈密顿量或二次型。因此必须建立MaxCut与伊辛模型之间的映射。给每个顶点 i 分配一个自旋变量 s_i ∈ {+1, −1}，约定 s_i = +1 表示顶点在 S 中，s_i = −1 表示在 V\S 中。一条边 (i,j) 是割边当且仅当 s_i ≠ s_j，即 (1 − s_i s_j)/2 = 1。于是：
C(s) = Σ w_ij · (1 − s_i s_j) / 2
= (1/2) Σ w_ij − (1/2) Σ w_ij s_i s_j最大化 C(s) 等价于最小化哈密顿量 H = Σ w_ij s_i s_j（忽略常数项）。这正是反铁磁伊辛模型的能量形式：边权为正时，系统倾向于让相邻自旋反向排列，从而“切断”这条边。若把自旋变量换成二进制变量 x_i ∈ {0,1}，通过 s_i = 1 − 2x_i 代换，就得到标准的QUBO形式。这一映射是连接图论问题与量子硬件的桥梁，也是第3章的核心内容。
四、量子计算为什么可能有用
MaxCut的解空间是离散且指数大的，经典局部搜索容易陷入局部最优。量子方案的价值主要体现在两点。其一是态空间的并行性：n 个量子比特可同时表示 2^n 个比特串的叠加，QAOA通过交替施加问题哈密顿量演化与混合哈密顿量演化，在叠加态上构造出偏向低能（即大割值）的概率分布。其二是采样即求解：测量一次得到一个候选割，多次采样后取最优，天然适配“近似求解”的需求。
但必须清醒认识到：当前量子硬件受限于比特数、连通性与噪声，短期内不可能在任意大规模MaxCut上全面超越经典算法。因此本课程强调问题规模与算法匹配——小规模图上验证正确性与线路逻辑，中等规模上比较近似质量，大规模上讨论分解与混合策略。这也是第20章之后实践部分的基本立场。
五、本课程的整体路线与学习目标
课程分为五个阶段。第一阶段（第1–6章）建立图论、伊辛模型、QUBO与量子比特编码的共同语言；第二阶段（第7–14章）深入QAOA的线路构造、参数初始化、优化器选择与测量解码；第三阶段（第15–20章）扩展到量子退火、变分本征求解与混合量子-经典方案；第四阶段（第21–26章）进入工程实践，包括建模流程、实验设计、结果判读与常见故障排查；第五阶段（第27–30章）讨论应用场景、性能边界与落地路径。
完成本课程后，你应当能够：独立把一个实际组合优化问题写成MaxCut或QUBO形式；为给定图设计QAOA线路并说明每一层的物理含义；使用模拟器或真实后端运行实验，正确解读采样结果与近似比；并能判断在什么规模、什么结构的问题上量子方案值得尝试。