量子译码：线性码、Simplex 的 Walsh 相关与 Quantum Viterbi

经典纠错码把 \(k\) 个 information bits 编成 \(n>k\) 个 bits，使噪声后的 received word 仍可恢复。对任意线性码做 maximum-likelihood decoding 是 NP-hard；量子计算不会把这个一般问题自动变成 polynomial time。Zoo 收录的加速依赖结构：simplex code 的 codewords 是 Fourier characters，convolutional code 的合法路径形成稀疏 trellis。

1. 线性码与译码目标

二元 \([n,k,d]\) linear code 是子空间

\[ C=\{uG:u\in\mathbb F_2^k\}\subseteq\mathbb F_2^n, \]

其中 \(G\) 是 generator matrix，\(d\) 是最小 Hamming distance。Parity-check matrix \(H\) 满足

\[ GH^T=0,\qquad C=\{c:Hc^T=0\}. \]

发送 \(c=uG\)，binary symmetric channel 加 error \(e\)，接收

\[ y=c\oplus e. \]

Syndrome 消去未知 codeword：

\[ s=Hy^T=H(c\oplus e)^T=He^T. \]

对 BSC，maximum-likelihood decoding 等价于找最小 weight 的 \(\widehat e\) 满足

\[ H\widehat e^T=s, \]

再输出 \(\widehat c=y\oplus\widehat e\)。若 \(\operatorname{wt}(e)\le\lfloor(d-1)/2\rfloor\)，最近 codeword 唯一；超过此半径时可能需要 list decoding 或 soft information。任意 \(H\) 的 syndrome decoding/nearest-codeword 问题在最坏情形很难，因此必须利用 code family 的 algebraic 或 trellis structure。

2. Simplex/Hadamard code 是 Fourier 字符

取 \(m\)-bit message \(a\in\mathbb F_2^m\)。Extended Hadamard code 的坐标由 \(x\in\mathbb F_2^m\) 标记：

\[ c_a(x)=a\cdot x\pmod2. \]

长度 \(N=2^m\)；去掉 \(x=0\) 坐标得到 \([2^m-1,m,2^{m-1}]\) simplex code。任意 \(a\ne b\) 时

\[ c_a(x)\oplus c_b(x)=(a\oplus b)\cdot x \]

在恰好一半 \(x\) 上为 \(1\)，所以最小距离为 \(2^{m-1}\)。

解码就是在所有 \(2^m\) 个 linear characters 中寻找与 received word \(y\) 相关性最大的 \(a\)。

3. 相位查询与 Walsh--Hadamard 译码

假设 input circuit 提供 coherent bit access

\[ O_y|x,z\rangle=|x,z\oplus y_x\rangle. \]

将 target qubit 置为 \(|-\rangle=(|0\rangle-|1\rangle)/\sqrt2\)，phase kickback 给

\[ \frac1{\sqrt N}\sum_x|x\rangle|-\rangle \longmapsto |\psi_y\rangle|-\rangle, \qquad |\psi_y\rangle=\frac1{\sqrt N}\sum_x(-1)^{y_x}|x\rangle. \]

丢开 target，对 index register 应用 \(H^{\otimes m}\)：

\[ H^{\otimes m}|\psi_y\rangle = \sum_{a\in\mathbb F_2^m} \left[ \frac1N\sum_x(-1)^{y_x+a\cdot x} \right]|a\rangle. \]

方括号正是 \(y\) 与 codeword \(c_a\) 的 normalized correlation。因为

\[ \frac1N\sum_x(-1)^{y_x+c_a(x)} =1-\frac{2\,d_H(y,c_a)}{N}, \]

测量偏向最近 codewords。

若无噪声，\(y=c_{a_*}\)，character orthogonality 给

\[ H^{\otimes m}|\psi_y\rangle=|a_*\rangle, \]

一次测量精确恢复 message。若 error fraction 为 \(\delta=t/N\)，正确 amplitude 是 \(1-2\delta\)，故单次成功概率至少含有

\[ p_{\mathrm{right}}=(1-2\delta)^2. \]

重复并多数表决可降低 failure probability；但当噪声接近相对距离边界时，其他 characters 也可能有较大相关性，不能只看这一项宣称唯一译码。

4. 复杂度里最容易漏掉的输入电路

Walsh transform 只在 \(m=\log_2N\) 个 qubits 上，用 \(m\) 个 Hadamard gates。Barg--Zhou 的实现把 computation subcircuit 压到 \(O(\log^2N)\) size/time 量级，但按 index 读取一个任意 \(N\)-bit received word 仍需额外 \(O(N)\) input circuitry。

所以结论是 circuit tradeoff：

  • quantum computation core 很小；

  • classical parallel decoder 可在 \(O(\log N)\) time 做 fast Walsh transform，但需 \(O(N\log N)\) 级 computation size；

  • 若 \(O_y\) 被当作免费 oracle，必须单独报告它的构造和数据 movement。

这是“查询/并行电路资源”的优势，不是读取 \(N\) 个任意 classical bits 的无条件 logarithmic-time 算法。

5. Convolutional code 与 trellis

Convolutional encoder 有 memory state \(q_t\in\{1,\ldots,Q\}\)。每步输入 symbol \(u_t\)，按确定规则

\[ q_t=T(q_{t-1},u_t), \qquad c_t=E(q_{t-1},u_t) \]

产生输出。若每个 state 只有 \(F\) 个合法 outgoing transitions，长度 \(L\) 的 codeword 对应 trellis 上一条路径

\[ \pi=(q_0\to q_1\to\cdots\to q_L). \]

给 observations \(r_1,\ldots,r_L\)，branch metric 可取 negative log-likelihood

\[ \gamma_t(q',q) =-\log\Pr(r_t\mid q'\to q). \]

Maximum-likelihood path 最小化

\[ M(\pi)=\sum_{t=1}^L\gamma_t(q_{t-1},q_t). \]

6. Classical Viterbi 递推

动态规划保留到每个 state 的最佳 prefix：

\[ D_t(q) = \min_{q'\to q} \left[D_{t-1}(q')+\gamma_t(q',q)\right]. \]

同时存 backpointer

\[ B_t(q)= \arg\min_{q'\to q} \left[D_{t-1}(q')+\gamma_t(q',q)\right]. \]

最终从 \(\arg\min_qD_L(q)\) 回溯。若 transition graph 稀疏，时间约为 \(O(LQF)\)，memory 取决于回溯策略。Viterbi 的力量正是合并拥有相同 suffix state 的指数多条 prefixes，而非枚举 \(F^L\) 条完整路径。

7. Quantum Viterbi 的构造思路

Grice--Meyer 的 quantum Viterbi algorithm 利用 trellis 与 FFT butterfly 相似的 tensor-product structure。概念步骤是：

  1. 用每步 transition unitary 在叠加中生成所有合法 paths，而不是所有 bit strings；

  2. reversible 地计算 branch metrics，并把 total likelihood/metric 写成 phase；

  3. 构造阈值或“较优路径”标记；

  4. 用 specialized amplitude amplification 提高 most-likely path 的 amplitude；

  5. 测量路径 register，验证 score，必要时重复。

若初态中最优路径总权重为 \(p_*\)，generic repetition 需 \(O(1/p_*)\) 次，而理想 amplitude amplification 需 \(O(1/\sqrt{p_*})\) 次。论文的有利 regime 是 state space \(Q\) 很大、frame \(L\) 较短且 fanout \(F\ll Q\)；state preparation 的成本随 \(F\) 而非稠密 \(Q\)-by-\(Q\) transitions 增长。

这不是对所有 Viterbi instances 的统一 quadratic theorem。标记“最优”可能需要未知 threshold，metric precision 影响 phase，近简并路径降低成功率，而且 classical DP 已避免 path-space brute force。实际比较必须包括 reversible metric oracle、state preparation、amplification 和完整 path readout。

8. 一般码上的量子搜索

对任意 syndrome \(s\)，可在 weight-\(w\) errors 上搜索

\[ \mathcal E_w=\{e\in\mathbb F_2^n:\operatorname{wt}(e)=w\} \]

并标记 \(He^T=s\)。Grover 把候选数

\[ |\mathcal E_w|=\binom nw \]

的穷举查询从 \(O(\binom nw)\) 降为 \(O(\sqrt{\binom nw})\)，但仍是 exponential。Quantum walks 可进一步改进 information-set decoding 的指数常数；这会影响 code-based cryptography parameter selection，却没有证明一般 decoding 属于 BQP。

9. 与量子纠错码译码的区别

本章输入和输出都是 classical bits，量子计算机只是 decoder。Quantum error-correcting code 则保护未知 quantum state，并从 stabilizer syndromes 推断 Pauli-error equivalence class。两者共享 syndrome、trellis 和 maximum-likelihood 思想，但后者必须保留 logical coherence，不能先测量并复制 data qubits。

还要区分“quantum algorithm decoding a classical codeword”与近期文献中的 quantum decoding problem（其输入本身可能是 codeword-state superposition）；oracle、成功标准和安全含义并不相同。

10. 小结与习题

  • 一般 linear-code ML decoding 很难；加速来自 simplex character 或 convolutional trellis。

  • Simplex 译码把 Hamming distance 变成 Walsh amplitude。

  • Quantum Viterbi 相干生成合法 paths 并放大高似然分支，优势只在明确参数区间成立。

  • 输入电路、soft-metric precision 和 classical path output 都必须计入。

  1. 对 \(m=3\) 写出全部 Hadamard codewords，并验证非零 message 的 weight 为 \(4\)。

  2. 若 \(\delta=0.1\)，计算正确 simplex message 的单次 amplitude 与 probability。

  3. 为一个 \(Q=4,F=2,L=3\) trellis 手算 Viterbi 表 \(D_t(q)\)。

  4. 用 Stirling approximation 估计 \(w=\alpha n\) 时 Grover syndrome search 的指数。

参考文献与 Zoo 覆盖