4. 功能等价与等价性检查问题定义
量子电路等价性检查（Quantum Equivalence Checking, QEC）要回答的核心问题是：给定两个量子电路 C₁ 和 C₂，它们在什么意义下“实现同一功能”？与经典电路等价性检查不同，量子电路作用于复向量空间，允许全局相位、相对相位、辅助比特、测量与噪声等额外自由度，因此“等价”必须被精确定义，否则判定结果会随定义漂移。本节先给出 QEC 的形式化问题，再区分完全等价、部分等价、近似等价与带辅助比特等价四类变体，最后分析其计算复杂度。
4.1 形式化问题定义
设 C₁ 与 C₂ 是作用在 n 个量子比特上的电路，分别实现酉算子 U₁、U₂ ∈ U(2ⁿ)。最朴素的等价定义是要求 U₁ = U₂ 逐元素相等。但量子力学中，两个仅相差全局相位的酉算子 e^{iθ}U 与 U 对所有测量统计完全不可区分，因此更合理的定义是“等价到全局相位”：存在 θ ∈ [0, 2π)，使得 U₁ = e^{iθ}U₂。若进一步允许电路在辅助比特上工作，则还需考虑辅助比特的初态与末态约束。
形式化地，QEC 的判定问题可表述为：输入为两个量子电路描述（门序列、门类型、连接关系、参数），输出为“等价”或“不等价”，并可选地给出反例（区分两者的输入态或可观测量）。当电路含参数化门（如 Rz(θ)）时，问题升级为符号等价性检查：判定对所有参数取值是否等价，或给出使两者不等价的参数区间。
4.2 四类等价变体
完全等价（Exact Equivalence）。 要求 U₁ = e^{iθ}U₂ 严格成立，允许全局相位差，但不允许任何相对相位、幅度或纠缠结构的偏差。这是最严格的定义，常用于验证电路优化（如门合并、交换律重排）是否保持语义不变。判定方法包括：将两电路映射为矩阵并比较、使用代数规范形式（如ZX演算、Pauli旋转群）做符号化简、或通过等价性检查工具（如QCEC、Feynman）进行决策过程。
部分等价（Partial Equivalence）。 只要求在某个受限输入子空间或某个可观测子集上等价。例如，两电路在计算基态 |0…0⟩ 上输出相同，但在叠加态上不同；或只要求对某组测量算符的期望值一致。部分等价常见于“仅关心特定初态”的场景，如量子机器学习中的态制备电路，或量子化学中只关心基态能量。判定时需明确限定域：是限定输入态集合、限定输出可观测量，还是限定测量基。
近似等价（Approximate Equivalence）。 允许 U₁ 与 e^{iθ}U₂ 之间存在有界误差，通常用算子范数、Frobenius范数或钻石范数度量。例如要求 ‖U₁ − e^{iθ}U₂‖ ≤ ε，其中 ε 是容差。近似等价是NISQ时代最实用的定义，因为门误差、分解误差和数值舍入不可避免。判定时需区分“最坏情况误差”与“平均误差”，并注意误差在电路深度上的累积。
带辅助比特等价（Equivalence with Ancilla）。 允许电路使用额外辅助比特，但要求辅助比特在计算前后处于指定状态（通常为 |0⟩ 或 |0…0⟩），且不与被计算比特纠缠。形式化地，若 C₁ 与 C₂ 分别实现 U₁ ⊗ I_a 与 U₂ ⊗ I_a 在扩展空间上的作用，且辅助比特初末态均为 |0⟩，则称两者在辅助比特辅助下等价。这类等价在量子纠错、态制备和块编码中极为常见，判定时需同时验证辅助比特的“清洁性”（uncomputation）。
4.3 计算复杂度分析
QEC 的复杂度取决于等价定义与电路描述方式。若电路以矩阵形式显式给出，完全等价检查只需比较两个 2ⁿ×2ⁿ 矩阵，时间复杂度 O(4ⁿ)，空间复杂度 O(4ⁿ)，对 n 稍大即不可行。若电路以门序列给出，问题变得更有趣：判定两个多项式规模量子电路是否完全等价，属于 coQMA 完全问题——即“不等价”存在量子见证（一个输入态使两者输出可区分），而“等价”的证明需要验证所有输入态，这超出了 QMA 的典型范围。
近似等价检查的复杂度与容差 ε 密切相关。当 ε 为常数时，问题属于 BQP：可以用量子算法估计 ‖U₁ − e^{iθ}U₂‖ 并判断是否小于 ε。当 ε 随 n 指数减小（如要求 ε = 2^{-n}）时，问题升级为 QMA 完全，因为需要验证所有输入态上的误差上界。带辅助比特等价检查通常也是 QMA 完全的，因为辅助比特的清洁性验证本身就是一个 QMA 问题。
部分等价检查的复杂度取决于限定域的大小。若限定域是多项式规模的计算基态集合，则可在多项式时间内完成；若限定域是任意子空间或任意可观测量集合，则问题可能退化为 QMA 完全。参数化等价检查（含符号参数）的复杂度最高，通常属于 PSPACE 或更高，因为需要处理参数空间上的全称量化。
4.4 判定流程与关键参数
面对一个具体的 QEC 任务，可按以下顺序决策：首先确认电路是否含参数——含参数则进入符号等价分支；其次确认是否允许辅助比特——允许则需额外验证清洁性；然后确认等价强度——完全、部分还是近似；最后根据强度选择判定算法。关键参数包括：量子比特数 n、电路深度 d、门集合、容差 ε、置信度 δ、辅助比特数 a。这些参数共同决定判定所需的时间与空间资源。
| 变体 | 判定条件 | 典型复杂度 | 适用场景 |
|---|---|---|---|
| 完全等价 | U₁ = e^{iθ}U₂ | coQMA 完全 | 电路优化验证 |
| 部分等价 | 限定域上一致 | 依赖域大小 | 态制备、特定初态 |
| 近似等价 | ‖U₁ − e^{iθ}U₂‖ ≤ ε | BQP / QMA | NISQ 硬件验证 |
| 带辅助比特等价 | 辅助比特清洁且不纠缠 | QMA 完全 | 纠错、块编码 |
理解这些变体与复杂度边界，是后续选择验证算法、设计测试用例和解读验证结果的基础。实际工程中，往往需要根据电路规模与验证目标，在严格性与可行性之间做出权衡：对关键子电路采用完全等价，对大规模电路采用近似等价并配合随机化测试，对含辅助比特的模块单独验证清洁性。