3. 量子计算基础速览

在进入量子背包问题求解之前，需要先建立一套“量子语言”。经典计算的基本单位是比特，取值只能是 0 或 1；量子计算的基本单位是量子比特（qubit），它可以处于 |0⟩ 与 |1⟩ 的叠加态。对背包问题而言，这意味着一个量子寄存器可以同时“携带”多个物品选择组合的振幅信息，从而为并行探索解空间提供物理基础。本节聚焦后续建模真正会用到的五个概念：量子比特、叠加、纠缠、量子门与测量，并说明它们如何对应到背包问题的变量编码与结果读取。

一、量子比特与状态表示

一个量子比特的纯态可写成 |ψ⟩ = α|0⟩ + β|1⟩，其中 α、β 为复数振幅，满足 |α|² + |β|² = 1。|α|² 与 |β|² 分别是测量得到 0 和 1 的概率。注意振幅是复数，带有相位信息，这一点在后续用振幅放大或相位估计类算法时非常关键。多个量子比特组成寄存器，n 个量子比特的联合态张成 2ⁿ 维希尔伯特空间，基向量可记为 |x₀x₁…xₙ₋₁⟩，对应十进制下标 0 到 2ⁿ−1。

对背包问题，最自然的编码是：第 i 个量子比特表示第 i 件物品是否放入背包，|1⟩ 表示放入，|0⟩ 表示不放入。若背包有 4 件物品，则寄存器 |q₃q₂q₁q₀⟩ 的一个基态如 |1010⟩ 表示选中第 3、1 件物品。这样，一个 4 比特寄存器天然覆盖 16 种选择组合，为后续构造“满足重量约束且价值最大”的振幅分布提供了载体。

二、叠加：并行性的来源

叠加不是“同时处于两个确定状态”，而是测量前状态由振幅共同描述。对每个量子比特施加哈达玛门 H，可得到均匀叠加态。以 2 个量子比特为例：

H|0⟩ = (|0⟩ + |1⟩)/√2
H⊗H|00⟩ = (|00⟩ + |01⟩ + |10⟩ + |11⟩)/2

四个基态的振幅均为 1/2，测量时各以 1/4 概率出现。推广到 n 比特，均匀叠加态包含 2ⁿ 个基态，每个振幅为 1/√(2ⁿ)。这正是量子算法“一次操作触及大量组合”的直观来源。但必须强调：叠加本身并不等于能直接读出所有解，测量只能得到一个基态，因此后续必须通过量子门构造干涉，让目标解的振幅增强、非目标解的振幅相消，这就是振幅放大的基本思想。

三、纠缠：寄存器内部的关联

纠缠是指多量子比特联合态不能写成各自状态的张量积。典型例子是贝尔态：

|Φ⁺⟩ = (|00⟩ + |11⟩)/√2

测量第一个比特若得 0，第二个必为 0；若得 1，第二个必为 1，两者结果完全关联。在背包求解中，纠缠常用于表达约束之间的耦合，例如“物品 A 与物品 B 不能同时选”这类逻辑关系，可通过受控门把辅助比特与决策比特纠缠起来，使不满足约束的基态在后续干涉中被抑制。理解纠缠有助于明白：量子寄存器不是一堆独立比特的简单拼盘，门操作会建立跨比特的关联结构。

四、量子门：对振幅的可控变换

量子门是作用在量子比特上的酉变换，必须可逆且保持归一化。后续背包求解最常用的门包括：

• H 门：制造叠加，常用于初始化。
• X 门：比特翻转，相当于经典非门。
• CNOT 门：受控翻转，控制位为 1 时翻转目标位，是制造纠缠的基本门。
• RZ / 相位门：给特定基态附加相位，是构造干涉、标记目标解的关键。
• 多控 Z 门：当一组比特满足特定模式时翻转相位，可用于把“满足约束的组合”标记出来。

一个典型的小例子：对 2 比特施加 H⊗H 后，再用受控相位门给 |11⟩ 附加 −1 相位，状态变为 (|00⟩+|01⟩+|10⟩−|11⟩)/2。此时四个基态概率仍各为 1/4，但 |11⟩ 的相位已与其他不同。若再施加一次 H⊗H，干涉会使 |11⟩ 的振幅被放大。这个“标记—干涉—放大”的套路，正是许多量子优化算法读取目标解的通用手法。

五、测量：从量子态到经典结果

测量是量子计算与经典世界之间的接口。在计算基下测量 n 比特寄存器，会按 |振幅|² 的概率坍缩到某一个基态，并输出对应的 n 位经典串。测量具有破坏性，重复测量同一量子态通常需要重新制备。因此实际求解流程一般是：制备初态 → 施加门序列 → 测量多次（shots）→ 统计各比特串出现频率 → 选取高频且满足约束的比特串作为候选解。

例如设置 shots = 1024，若某比特串出现 600 次，则其经验概率约为 0.586。判断算法是否有效，不能只看单次结果，而要看目标解是否在统计上显著高于均匀分布（n 比特均匀分布下每个基态概率为 1/2ⁿ）。对 4 比特背包，均匀分布下每个组合概率为 1/16 ≈ 0.0625；若目标组合经验概率明显高于该值，说明振幅放大起了作用。

六、把五个概念串成求解流程

将上述概念组合起来，量子背包求解的典型流程是：用 n 个量子比特编码 n 件物品的选择；用 H 门制备均匀叠加，使所有组合等幅出现；用 CNOT、多控 Z、RZ 等门把重量约束与价值目标编码为相位或振幅条件，使可行且高价值的组合获得更大振幅；最后通过多次测量统计比特串频率，取高频可行解作为候选。需要清醒认识的是，当前含噪声中等规模量子（NISQ）设备比特数有限、门保真度有限，直接求解大规模背包仍不现实，因此本课程后续会结合小规模示例与经典基准进行对比，重点理解算法结构与适用边界，而非追求规模上的绝对优势。