# 量子译码：线性码、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 覆盖

- Zoo 编号 238：Jon R. Grice 与 David A. Meyer, [A quantum algorithm for Viterbi decoding of classical convolutional codes](https://arxiv.org/abs/1405.7479)。
- Zoo 编号 239：Alexander Barg 与 Shiyu Zhou, [A quantum decoding algorithm of the simplex code](https://www.terpconnect.umd.edu/~abarg/reprints/rm1dq.pdf)。
- 延伸阅读：[Bernstein--Vazirani](../ch04-classic-algorithms/bernstein-vazirani-algorithm-tutorial.md)、[Amplitude amplification](../ch03-algo-basics/amplitude-amplification.md)和[量子 subset sum](../ch09-algebra-number-theory/quantum-subset-sum.md)。