3. 问题编码的数学基础

把经典问题“翻译”成量子算法可以处理的形式，并不是简单地把变量换成量子比特。真正决定编码方式的是问题背后的数学结构：约束条件通常写成布尔函数，状态演化依赖线性代数，对称性由群论刻画，而变量之间的耦合关系往往天然是一张图。理解这四类工具各自负责什么，才能判断一个问题该用相位编码、振幅编码还是哈密顿量编码。

布尔函数：把约束变成可判定的形式

布尔函数 f:{0,1}ⁿ→{0,1} 是描述组合约束最直接的语言。以 3-SAT 为例，一个子句 (x₁∨¬x₂∨x₃) 对应一个布尔函数，当且仅当三个文字至少一个为真时取 1。整个公式的可满足性就是所有子句布尔函数的合取。量子算法并不直接“求解”这个函数，而是把它嵌入到相位或振幅中：常见做法是构造 f(x) 的量子线路，将 f(x)=1 的解标记出来，再通过振幅放大提高其测量概率。

关键映射原则是：布尔函数决定“哪些输入是解”，量子线路决定“如何以可逆方式计算这个判定”。由于量子门必须可逆，经典中的与、或需要转换为 Toffoli 门加辅助比特的形式。例如计算 x₁∧x₂ 时，用辅助比特 c 初始化为 |0⟩，施加 Toffoli(x₁,x₂;c)，则 c 记录合取结果，整个过程可逆。这一步是后续所有编码的公共基础。

线性代数：状态、算子与编码的载体

量子状态是复希尔伯特空间中的单位向量，n 个量子比特对应 2ⁿ 维空间。线性代数在这里承担三件事：第一，把经典数据编码为向量，例如振幅编码将长度为 N 的向量归一化后映射为 log₂N 个量子比特的振幅；第二，把问题约束写成厄米算子，使问题的解对应某个算子的基态或本征态；第三，用矩阵分解（如谱分解）分析算法复杂度。

以组合优化为例，若目标函数为 C(x)=Σᵢⱼ wᵢⱼxᵢxⱼ，可将其提升为对角哈密顿量 H| x⟩=C(x)|x⟩。此时求最小代价解等价于求 H 的最小本征值对应的本征态。这个“函数→对角矩阵”的转换是变分量子算法（如 QAOA）的起点。需要强调的是，对角矩阵的构造必须保持比特串到基矢的一一对应，否则本征值就失去问题含义。

群论：识别对称性以简化问题

很多问题具有置换、翻转或周期对称性。群论的作用是识别这些对称性，从而压缩搜索空间或设计更高效的线路。典型例子是 Simon 问题：函数满足 f(x)=f(x⊕s)，其对称群由异或平移生成，量子算法正是利用这个群结构在多项式时间内求出 s。另一个例子是图的自同构群，若两个图同构，则存在顶点置换使邻接矩阵在置换下不变，量子图同构算法会借助群表示论构造不变量的量子态。

实操中，识别对称性可以先从问题的输入结构入手：变量是否可互换、约束是否在循环移位下不变、目标函数是否对某些比特翻转保持不变。找到生成元后，可将状态限制在对称子空间中，减少所需量子比特或线路深度。这一步不是必须的，但当问题规模较大时，对称性约简往往能显著降低资源估算中的门数和比特数。

图论：刻画变量耦合与线路拓扑

图论在量子问题表示中有两层含义。第一层是问题图：变量是顶点，耦合是边。MaxCut 问题中，每条边 (i,j) 贡献一个项，目标是最小化割边数，其哈密顿量直接对应图的邻接结构。第二层是硬件拓扑图：量子芯片上比特之间的连接是有限的，若问题图的边与硬件边不匹配，就需要插入 SWAP 门，这会增加线路深度。资源估算时必须同时考虑这两张图。

一个实用的映射原则是：先画问题图，再对照硬件拓扑，统计需要额外路由的边数。例如在 5 比特线形拓扑上实现一个含 6 条边的 MaxCut 问题，若问题图是三角形加两条悬挂边，则部分耦合需要经过中间比特，SWAP 开销会明显上升。这个统计结果直接进入后续的资源估算表。

四类工具如何协同：一个可操作的映射流程

面对一个新问题，可以按以下顺序推进，而不是一上来就写线路。第一步，用布尔函数写出判定条件，明确“解”的集合；第二步，判断该判定能否写成多项式规模的约束，若不能，考虑近似或变分方案；第三步，把目标函数提升为对角哈密顿量，检查其项数与问题图的边数是否一致；第四步，识别对称性，若存在非平凡自同构群，尝试在对称子空间内构造初态；第五步，对照硬件拓扑统计路由开销，把 SWAP 数计入资源估算。

以一个小型 MaxCut 示例说明参数关系：设图有 4 个顶点、5 条边，边权均为 1。问题哈密顿量 H=Σ_(i,j)∈E(1−ZᵢZⱼ)/2，共 5 项。若硬件为 4 比特环形拓扑（边为 1-2、2-3、3-4、4-1），而问题图含边 1-3，则该耦合在硬件上不相邻，需要一次 SWAP 或等效路由。资源估算表中应记录：逻辑比特 4、耦合项 5、额外路由边 1、预计 SWAP 层数 1。这些数字是示例假设，用于说明估算口径，并非实测结果。

最后需要强调，四类工具不是彼此替代的关系，而是分层协作：布尔函数回答“解是什么”，线性代数回答“用什么态和算子表示”，群论回答“哪些结构可以压缩”，图论回答“耦合如何落到硬件上”。掌握这个分层，才能在后续的资源估算中把比特数、门数、深度和路由开销分别归因到正确的数学来源，而不是笼统地给出一个总数。