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

经典纠错码 (error-correcting code) 解决的问题是：发送方把 $k$ 个 information bits 编成 $n>k$ 个 bits 发送，信道会翻转其中一些 bit，接收方拿到被污染的 received word 后，仍希望恢复原始消息。自 Shannon 1948 年建立信道编码定理、Hamming 1950 年给出第一个显式构造以来，**编码**（如何设计好码）与**译码**（如何高效地从噪声中恢复）一直是两个独立的问题：好码可以构造出来，但"对任意线性码做 maximum-likelihood decoding"这一通用任务已被证明是 NP-hard 的（Berlekamp、McEliece 与 van Tilborg，1978）。因此经典译码算法的全部艺术在于**利用具体码族的结构**：Reed--Muller 码用多数逻辑，Reed--Solomon 码用多项式插值，卷积码用 trellis 上的动态规划（Viterbi 算法，1967）。

那么量子计算能帮上什么忙？首先要泼一盆冷水：量子计算**不会**把这个一般的 NP-hard 问题自动变成 polynomial time——没有任何已知结果表明一般线性码译码属于 BQP。Zoo 收录的量子译码加速全部依赖额外的代数或组合结构：

- **Simplex/Hadamard code** 的 codewords 恰好是 $\mathbb F_2^m$ 上的 Fourier characters，译码等价于求 Walsh 变换的最大分量——这正是 [Bernstein--Vazirani 算法](../ch04-classic-algorithms/bernstein-vazirani-algorithm-tutorial.md)的相位查询结构，对应 Barg--Zhou 的量子 simplex 译码算法（Zoo 239）；
- **Convolutional code** 的合法 codewords 形成稀疏 trellis 上的路径，Viterbi 的动态规划可以被相干化，对应 Grice--Meyer 的 quantum Viterbi algorithm（Zoo 238）；
- 对**一般线性码**，量子搜索（Grover）与量子行走只能把穷举译码的指数开平方或改进指数常数，这在密码分析中有实际意义（见本站[量子密码分析](quantum-cryptanalysis.md)），但不是多项式加速。

本章逐一展开这三条路线。读者应已熟悉本站 ch01–ch08 的内容，特别是相位反冲 (phase kickback)、Hadamard 变换与 [Grover 算法](../ch03-algo-basics/grover.md)、[振幅放大](../ch03-algo-basics/amplitude-amplification.md)。我们会反复回到一个主题：**量子优势到底来自哪一步，又有哪些隐藏成本（输入电路、metric 精度、经典读出）必须如实计入。**

:::{admonition} 本课知识点
:class: tip

1. **[线性码、syndrome 与 ML 译码](#linear-code-syndrome-ml)**——能写出 $[n,k,d]$ 线性码的生成矩阵与校验矩阵刻画，推导 syndrome $s=Hy^T=He^T$ 只依赖错误向量，并证明 BSC 下 ML 译码等价于最小重量译码。
2. **[Simplex/Hadamard 码与字符正交性](#simplex-character-orthogonality)**——能写出 Hadamard 码作为线性函数真值表的构造，并用配对论证证明最小距离为 $2^{m-1}$ 与字符正交性 $\frac1N\sum_x(-1)^{v\cdot x}=\delta_{v,0}$。
3. **[Walsh 系数与最近码字译码](#walsh-nearest-codeword)**——能推导 Walsh 系数公式 $\widehat y(a)=1-\frac{2\,d_H(y,c_a)}{N}$，并解释最大 Walsh 系数译码与最近码字译码为何是同一问题的两种写法。
4. **[相位反冲与 Walsh--Hadamard 译码](#phase-kickback-walsh-decoding)**——能用相位反冲把接收字制备成相位态 $|\psi_y\rangle$，并证明 $H^{\otimes m}|\psi_y\rangle$ 的第 $a$ 个振幅恰为 Walsh 系数 $\widehat y(a)$。
5. **[译码成功概率与输入电路成本](#decoding-success-probability)**——能计算有噪声时的单次成功概率 $(1-2\delta)^2$ 并设计重复多数表决方案，同时说明 $O(N)$ 输入电路成本为何必须计入端到端复杂度。
6. **[卷积码、trellis 与 Viterbi 递推](#viterbi-trellis-recursion)**——能把卷积码译码写成 trellis 上可加度量的最优路径问题，写出 Viterbi 递推并手算小例子的填表过程。
7. **[量子 Viterbi 与一般码量子搜索](#quantum-viterbi-grover-search)**——能解释振幅放大把重复次数从 $O(1/p_*)$ 降到 $O(1/\sqrt{p_*})$ 的适用条件，并用 Stirling 近似推导 Grover 只把 $\binom nw$ 穷举的指数减半。
8. **[与量子纠错译码的区别](#classical-vs-quantum-decoding)**——能从输入输出类型、噪声对象与 no-cloning 约束出发，辨析本章"量子算法译经典码"与量子纠错码译码的差异。

:::

## 1. 线性码与译码目标

### 1.1 基本定义

一个二元 $[n,k,d]$ linear code 是 $\mathbb F_2^n$ 的一个 $k$ 维线性子空间。用 generator matrix $G\in\mathbb F_2^{k\times n}$（$k$ 个基码字的行向量拼成）写出来就是

$$
C=\{uG:u\in\mathbb F_2^k\}\subseteq\mathbb F_2^n.
$$

三个参数的含义：$n$ 是码长（每个 codeword 的 bit 数），$k$ 是维数（能编码 $k$ 个 information bits），$d$ 是最小 Hamming distance，即任意两个不同 codewords 之间不同坐标个数的最小值。线性性带来一个常用简化：两个 codewords 之差仍是 codeword（$c_1\oplus c_2\in C$），所以最小距离等于**最小非零重量**

$$
d=\min_{c\in C,\,c\neq 0}\operatorname{wt}(c),\qquad \operatorname{wt}(c):=\#\{i:c_i=1\}.
$$

与子空间对偶的是 parity-check matrix $H\in\mathbb F_2^{(n-k)\times n}$，它的行张成 $C$ 的正交补，因此满足

$$
GH^T=0,\qquad
C=\{c\in\mathbb F_2^n:Hc^T=0\}.
$$

第二行的读法是：$H$ 给出了 $n-k$ 个线性校验方程，一个向量是合法 codeword 当且仅当它通过全部校验。这个"判 membership 很容易"的性质是后面 syndrome 译码的基础。

### 1.2 信道模型与 syndrome

发送 $c=uG$。我们采用最简单的噪声模型 **binary symmetric channel (BSC)**：每个 bit 独立地以概率 $p<1/2$ 被翻转。等价地，信道加上一个 error vector $e\in\mathbb F_2^n$（$e_i=1$ 表示第 $i$ 位出错），接收方拿到

$$
y=c\oplus e.
$$

译码器的输入只有 $y$。第一步是计算 **syndrome**（校验子）

$$
s:=Hy^T=H(c\oplus e)^T=Hc^T\oplus He^T=He^T.
$$

逐步看这个等式：第一步代入 $y=c\oplus e$；第二步用矩阵对 $\oplus$ 的分配律（在 $\mathbb F_2$ 上加法就是逐位异或）；第三步用 $Hc^T=0$，因为 $c\in C$。结论是：**syndrome 只依赖 error，不依赖发送的是哪个 codeword**。未知量从"$2^k$ 个候选 codewords"约化为"满足 $He^T=s$ 的候选 errors"，这是线性码译码的标准化简。

(linear-code-syndrome-ml)=
### 1.3 为什么 ML 译码就是最小重量译码

BSC 下，给定发送 $c$ 收到 $y$ 的条件概率完全由错误个数 $\operatorname{wt}(y\oplus c)$ 决定：

$$
\Pr(y\mid c)=p^{\operatorname{wt}(y\oplus c)}(1-p)^{\,n-\operatorname{wt}(y\oplus c)}
=(1-p)^n\left(\frac{p}{1-p}\right)^{\operatorname{wt}(y\oplus c)}.
$$

第一个等号是独立性（哪几位错、哪几位对，各自贡献因子 $p$ 或 $1-p$）；第二个等号只是提出公因子。由于 $p<1/2$，比值 $\frac{p}{1-p}<1$，所以 $\Pr(y\mid c)$ 是 Hamming 距离 $d_H(y,c)=\operatorname{wt}(y\oplus c)$ 的**严格递减函数**。因此 maximum-likelihood decoding（找使 $\Pr(y\mid c)$ 最大的 $c$）等价于 nearest-codeword decoding（找离 $y$ 最近的 $c$）。

结合 syndrome 语言：候选 error 必须满足约束 $H\widehat e^{\,T}=s$，ML 译码就是在所有解中找重量最小的：

$$
\widehat e=\arg\min_{e:\,He^T=s}\operatorname{wt}(e),\qquad
\widehat c=y\oplus\widehat e.
$$

**唯一性半径。** 若真实错误满足 $\operatorname{wt}(e)\le t:=\lfloor(d-1)/2\rfloor$，则最近 codeword 唯一。证明是标准的三角不等式：若另有一个 $c'\in C$ 也满足 $d_H(y,c')\le t$，则

$$
d_H(c,c')\le d_H(c,y)+d_H(y,c')\le 2t\le d-1<d,
$$

与最小距离为 $d$ 矛盾（第一步是 Hamming 距离的三角不等式，第二步是两个距离都不超过 $t$）。几何图像：以各 codewords 为球心、$t$ 为半径的 Hamming 球互不相交，球内的 received word 归属唯一。超出此半径时最近码字可能不唯一，就需要 list decoding（输出一个小候选列表）或 soft information（利用信道的模拟输出而非硬判决）等更强的框架。

**难点所在。** "解线性方程组 $He^T=s$"本身用高斯消元是多项式时间的；难的是约束**最小重量**解。对任意给定的 $H$，这个 syndrome decoding / nearest-codeword 问题在最坏情形是 NP-hard 的。所以一切高效译码算法——无论经典还是量子——都必须利用 code family 的 algebraic 或 trellis structure。下面两节先看一个"结构强到量子算法一步译码"的极端例子。

## 2. Simplex/Hadamard code 是 Fourier 字符

### 2.1 构造

取 $m$-bit message $a\in\mathbb F_2^m$。**Extended Hadamard code** 把 $a$ 编码成一个长度为 $N=2^m$ 的向量，其坐标由所有 $x\in\mathbb F_2^m$ 标记：

$$
c_a(x)=a\cdot x\pmod 2,\qquad a\cdot x:=\bigoplus_{i=1}^m a_i x_i.
$$

也就是说，codeword $c_a$ 是线性函数 $x\mapsto a\cdot x$ 的**真值表**：把函数在全部 $2^m$ 个输入上的取值排成一行。这是编码理论中"函数 $\to$ 真值表"的标准对应，Hadamard code 正是所有线性函数的真值表构成的码（一阶 Reed--Muller 码的线性部分）。

坐标 $x=0$ 对所有 $a$ 都满足 $c_a(0)=0$，不携带任何信息；去掉它就得到 $[2^m-1,\,m,\,2^{m-1}]$ **simplex code**。注意它的参数有多极端：$k=m$ 个 information bits 被膨胀到 $n=2^m-1$ 个 bits，码率 $k/n$ 指数小，换来的是巨大的相对距离 $d/n\approx 1/2$。这种码在实用通信中太奢侈，但在理论计算机科学（ hardness amplification、伪随机性）和本节的量子算法中非常自然。

(simplex-character-orthogonality)=
### 2.2 最小距离的完整证明

**Lemma 1**. 对任意 $a\neq b$，$d_H(c_a,c_b)=2^{m-1}$。因此 Hadamard code 的最小距离是 $2^{m-1}$，simplex code（删去恒零坐标不影响非零重量）同样是 $2^{m-1}$。

**证明**。由线性性，$c_a(x)\oplus c_b(x)=(a\oplus b)\cdot x$，所以两码字的距离等于函数 $x\mapsto v\cdot x$ 的重量，其中 $v:=a\oplus b\neq 0$。我们要证明：非零线性函数在恰好一半的输入上取 $1$。

取 $v$ 的某个非零分量 $v_j=1$。把 $\mathbb F_2^m$ 配成 $2^{m-1}$ 对：每个 $x$ 与 $x^{(j)}$（把 $x$ 的第 $j$ 位翻转）配成一对。每一对内

$$
v\cdot x^{(j)}=v\cdot(x\oplus e_j)=v\cdot x\oplus v_j=v\cdot x\oplus 1,
$$

即同一对中两个函数值恰好一 $0$ 一 $1$（第一步用 $\mathbb F_2$ 上内积的双线性，第二步用 $v_j=1$）。$2^{m-1}$ 对每对贡献恰好一个 $1$，总重量为 $2^{m-1}$。Q.E.D.

同一个配对论证还给出量子计算读者更熟悉的形式——**character orthogonality**：对 $v\neq 0$，

$$
\sum_{x\in\mathbb F_2^m}(-1)^{v\cdot x}=2^{m-1}\bigl(1+(-1)\bigr)=0,
$$

因为每对贡献 $(-1)^{v\cdot x}+(-1)^{v\cdot x+1}=0$；而 $v=0$ 时和显然为 $N$。合并写成

$$
\frac1N\sum_{x\in\mathbb F_2^m}(-1)^{v\cdot x}=\delta_{v,0}.
$$

这正是本站 ch04 中 Bernstein--Vazirani 算法"一次 Hadamard 变换读出隐藏字符串"背后的同一个恒等式，第 3 节会反复使用它。

(walsh-nearest-codeword)=
### 2.3 译码问题的重述

接收字是 $y\in\mathbb F_2^N$（坐标同样由 $x$ 标记）。译码要在全部 $2^m$ 个 linear characters $c_a$ 中找与 $y$ 相关性最强的一个。用 $\pm 1$ 记号写出 $y$ 与 $c_a$ 的归一化内积（Walsh 相关系数）：

$$
\widehat y(a):=\frac1N\sum_{x}(-1)^{y_x\oplus c_a(x)}.
$$

逐坐标看：若 $y_x=c_a(x)$，该项贡献 $(-1)^0=+1$；若不同，贡献 $-1$。设有 $d_H(y,c_a)$ 个坐标不同，则

$$
\widehat y(a)=\frac{(N-d_H(y,c_a))-d_H(y,c_a)}{N}=1-\frac{2\,d_H(y,c_a)}{N}.
$$

所以"Walsh 系数最大"与"Hamming 距离最小"是**同一件事**的两种写法：nearest-codeword decoding $\equiv$ 求 $\widehat y(a)$ 的最大分量。这个恒等式是整个 Barg--Zhou 算法的支点——它把译码问题翻译成了 Fourier 分析问题，而量子计算机恰好擅长对真值表做 Fourier 变换。

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

### 3.1 输入模型：相位反冲

假设 input circuit 提供对 received word 的 coherent bit access（按索引读出第 $x$ 位的标准 oracle）：

$$
O_y|x,z\rangle=|x,z\oplus y_x\rangle.
$$

第一个寄存器是 $m=\log_2 N$ 个 qubits 的 index register，第二个是单 qubit target。把 target 制备在 $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$，就是本站 ch01 学过的 phase kickback 技巧：

$$
O_y|x\rangle|-\rangle
=\frac{|x,y_x\rangle-|x,y_x\oplus1\rangle}{\sqrt2}
=(-1)^{y_x}|x\rangle|-\rangle.
$$

中间的等号按 $y_x=0,1$ 分别验证：$y_x=0$ 时 target 不变，因子为 $+1$；$y_x=1$ 时 $|0\rangle-|1\rangle$ 变成 $|1\rangle-|0\rangle=-|-\rangle$，因子为 $-1$。bit 值 $y_x$ 被"踢回"成 index register 上的相位。对 index register 制备均匀叠加并整体作用 $O_y$：

$$
\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.
$$

注意 $|\psi_y\rangle$ 就是 $\pm1$ 向量 $\bigl((-1)^{y_x}\bigr)_x$ 归一化后的**量子态版本**：整个 $N$-bit received word 被压缩进 $m$ 个 qubits 的相位里。这一步只调用了一次 $O_y$，正是"查询复杂度"与"电路复杂度"分离的地方，第 4 节会回到这一点。

(phase-kickback-walsh-decoding)=
### 3.2 Walsh--Hadamard 变换一步求出全部相关系数

丢开 target（它与 index register 已解耦），对 index register 应用 $m$ 位 Hadamard 变换 $H^{\otimes m}$。用 ch03 已建立的恒等式

$$
H^{\otimes m}|x\rangle=\frac1{\sqrt N}\sum_{a\in\mathbb F_2^m}(-1)^{a\cdot x}|a\rangle,
$$

代入 $|\psi_y\rangle$ 并按 $a$ 归并系数：

$$
H^{\otimes m}|\psi_y\rangle
=\frac1{\sqrt N}\sum_x(-1)^{y_x}\cdot\frac1{\sqrt N}\sum_a(-1)^{a\cdot x}|a\rangle
=\sum_{a\in\mathbb F_2^m}
\underbrace{\left[\frac1N\sum_x(-1)^{y_x\oplus\, a\cdot x}\right]}_{\widehat y(a)}|a\rangle.
$$

方括号里 $\mathbb F_2$ 加法 $y_x+a\cdot x$ 就是 $y_x\oplus c_a(x)$，所以**第 $a$ 个振幅恰好是 2.3 节定义的 Walsh 系数 $\widehat y(a)$**。结合那里的恒等式：

$$
\text{输出态 }|a\rangle\text{ 的振幅}=1-\frac{2\,d_H(y,c_a)}{N}.
$$

一次 $H^{\otimes m}$（$m$ 个 Hadamard gates）就把"与全部 $2^m$ 个码字的距离"同时写进了振幅——测量分布直接偏向最近的码字。这就是 Barg--Zhou 算法的核心，也是"Hadamard code 译码 = Walsh 谱分析"的量子实现。

(decoding-success-probability)=
### 3.3 无噪声与有噪声的成功概率

**无噪声情形。** 若 $y=c_{a_*}$，由 2.2 节的 character orthogonality，

$$
\widehat y(a)=\frac1N\sum_x(-1)^{(a\oplus a_*)\cdot x}=\delta_{a,a_*},
\qquad\text{即}\qquad
H^{\otimes m}|\psi_y\rangle=|a_*\rangle.
$$

一次测量以概率 $1$ 恢复 message。这正是 Bernstein--Vazirani 算法——"BV 算法就是 Hadamard code 的无噪声译码"这个对应关系值得记住。

**有噪声情形。** 设 error fraction 为 $\delta=t/N$（$t$ 个坐标被翻转）。正确 message 的振幅是

$$
\widehat y(a_*)=1-\frac{2t}{N}=1-2\delta,
\qquad
p_{\mathrm{right}}=|\widehat y(a_*)|^2=(1-2\delta)^2.
$$

其余 $N-1$ 个错误 candidate 分走剩余概率 $1-(1-2\delta)^2=4\delta(1-\delta)$。只要 $\delta$ 有界地小于 $1/2$，单次测量就以常数概率命中正确 message；独立重复 $O(\log\frac1\varepsilon)$ 次并对测量结果取多数表决（每个 candidate 是一个 $m$-bit 串，逐位取多数即可），可以把 failure probability 压到 $\varepsilon$ 以下，总查询数是 $O(\log\frac1\varepsilon)$ 次 oracle 调用——与 $N$ 无关。

但原文的保留条款必须强调：$p_{\mathrm{right}}=(1-2\delta)^2$ 只是**正确码字那一条振幅**的贡献。当噪声接近相对距离边界（$\delta$ 接近 $1/4$，即 $d/2N$）甚至超过它时，其他 characters 也可能有与 $1-2\delta$ 相当甚至更大的相关性，此时"测到多数 $a_*$"不再自动成立，不能只看这一项就宣称唯一译码——需要 list decoding 式的分析或对噪声模型的额外假设。

### 3.4 一个完整的小例子

取 $m=3$，$N=8$，真实 message $a_*=(1,0,1)$，即 $c_{a_*}(x)=x_1\oplus x_3$。按 $x=000,001,\ldots,111$ 列出真值表：

$$
c_{a_*}=(0,1,0,1,1,0,1,0).
$$

设信道翻转了坐标 $x=011$ 这一位，收到 $y=(0,1,0,\mathbf{0},1,0,1,0)$（粗体为错误位），$\delta=1/8$。按公式，正确振幅应为 $1-2\delta=3/4$，我们直接验证并顺便算出全部 $8$ 个振幅。

把 $\pm1$ 向量写出来：$(-1)^{y_x}$ 在除 $x=011$ 外等于 $(-1)^{c_{a_*}(x)}$，在 $x=011$ 处反号。于是对任意 candidate $a$，

$$
\widehat y(a)=\frac18\sum_x(-1)^{y_x\oplus a\cdot x}
=\underbrace{\frac18\sum_x(-1)^{(a_*\oplus a)\cdot x}}_{\delta_{a,a_*}}
\;-\;\frac{2}{8}(-1)^{(a_*\oplus a)\cdot 011}.
$$

第二步的依据：把求和分成"$x\neq 011$"与"$x=011$"两部分；错误位上 $(-1)^{y_x}$ 与无错值相差一个符号，所以该点贡献要从 $+(-1)^{(a_*\oplus a)\cdot011}$ 改为 $-(-1)^{(a_*\oplus a)\cdot011}$，净差 $-2(-1)^{(a_*\oplus a)\cdot011}$。于是

- $a=a_*$：振幅 $=1-\frac{2}{8}=\frac34$，概率 $\frac{9}{16}=0.5625$；
- $a\neq a_*$（共 $7$ 个）：正交性使第一项为 $0$，振幅 $=\mp\frac14$，概率各 $\frac1{16}$。

检查归一化：$\frac{9}{16}+7\times\frac1{16}=1$，符合酉变换保持范数。单次测量以 $9/16$ 的概率直接给出正确 message；重复三次取逐位多数，失败概率已低于 $(1-9/16)^2$ 量级。这个小例子也说明了 3.3 节的保留条款：错误 candidates 的概率随 $t$ 线性增长（每多一个错误位，部分 candidate 的振幅绝对值增大），噪声越重，"一枝独秀"越不明显。

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

3.2 节的画面非常漂亮：译码 $N=2^m$ 位的码字只用了 $m$ 个 qubits 和 $m$ 个 Hadamard gates。但这个账只算了"量子计算核心"。诚实的复杂度分析必须把数据进出量子处理器的过程也算上，这里正是量子译码文献中最常被误读的地方。

逐项拆开看：

- **量子计算核心**确实很小：Walsh transform 只在 $m=\log_2N$ 个 qubits 上，用 $m$ 个 Hadamard gates。Barg--Zhou 的完整实现进一步把 computation subcircuit 压到 $O(\log^2N)$ size/time 量级。
- **输入电路**无法省略：按 index 读取一个任意 $N$-bit received word 来实现 $O_y$，需要额外 $O(N)$ 的 input circuitry（数据选择/路由电路），其规模与被编码的 classical 数据量同阶。无论经典还是量子，"处理 $N$ 个任意 bits"的物理成本都不可能低于读入它们。
- **与经典算法对比**：经典并行 decoder 可以在 $O(\log N)$ 的 time（深度）内完成 fast Walsh transform——FWT 的 butterfly 结构共 $\log_2 N$ 层，每层 $O(N)$ 个加减操作完全并行——但总的 computation size 是 $O(N\log N)$。量子方案的特点是**深度与 size 都小**（核心部分），代价是需要把数据以相干 oracle 的形式提供。
- **oracle 假设必须单独报告**：若 $O_y$ 被当作免费 oracle，结论只是"查询复杂度 $O(1)$、时间复杂度 $O(\log^2 N)$"；一旦要求从 classical RAM 中的 $N$ 个 bits 构造 $O_y$，就必须单独报告它的构造和数据 movement 成本。

所以正确的表述是一个 circuit tradeoff：**这是"查询/并行电路资源"意义上的优势，不是读取 $N$ 个任意 classical bits 的无条件 logarithmic-time 算法。** 凡是看到"量子译码指数加速"的说法，第一件事就是检查输入模型属于哪一类。

## 5. Convolutional code 与 trellis

### 5.1 编码器是一台状态机

前面讨论的 block code 把消息分块独立编码；convolutional code 则是**流式**的：编码器内部保持一个 memory state $q_t\in\{1,\ldots,Q\}$（$Q$ 个状态，对应移位寄存器的内容），每来一个 input symbol $u_t$，按确定规则更新状态并产生该步的输出：

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

其中 $T$ 是状态转移函数、$E$ 是输出函数。关键观察：编码器是一台**有限状态机**，而一个长度为 $L$ 的合法 codeword 与状态机的一条长度-$L$ 运行轨迹一一对应。把所有时刻的状态并排画出来、合法转移连成边，就得到 **trellis**（格图）：$L+1$ 列、每列 $Q$ 个节点，codeword 对应 trellis 上一条路径

$$
\pi=(q_0\to q_1\to\cdots\to q_L).
$$

设每个 state 只有 $F$ 个合法 outgoing transitions（fanout，通常 $F=2$，每步一个 input bit）。路径总数是 $\sim QF^{L}$ 量级——随 $L$ 指数增长，这就是译码难的原因；但"每一步只有 $F$ 个选择、汇合到 $Q$ 个状态"的稀疏结构，正是经典与量子算法都要利用的东西。

### 5.2 从似然到路径度量

接收方逐时刻拿到 observations $r_1,\ldots,r_L$（BSC 下 $r_t$ 是 $c_t$ 的噪声版本；更一般的软判决下 $r_t$ 可以是模拟值）。由信道的无记忆性（各时刻噪声独立），给定路径 $\pi$ 的似然分解为逐时刻因子之积：

$$
\Pr(r_1,\ldots,r_L\mid\pi)=\prod_{t=1}^L\Pr(r_t\mid q_{t-1}\to q_t).
$$

Maximum-likelihood 译码要最大化这个乘积。取负对数把乘积变和（对数单调，不改变 argmax；取负号把 max 变 min），定义 **branch metric**

$$
\gamma_t(q',q)=-\log\Pr(r_t\mid q'\to q),
$$

则 ML 路径最小化**可加的路径总度量**

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

例：BSC 交叉概率 $p$、每步输出一个 bit 时，$\Pr(r_t\mid q'\to q)$ 只取 $p$ 或 $1-p$ 两个值，所以 branch metric 只差一个常数因子地等于"该步输出与观测的 Hamming 距离"——第 1.3 节"ML = 最小距离"在这里以逐时刻的形式重现。"最小化可加度量"这个形状，是下面动态规划与量子振幅放大都能接上的原因。

## 6. Classical Viterbi 递推

(viterbi-trellis-recursion)=
### 6.1 最优子结构与递推

枚举全部 $\sim QF^L$ 条路径显然不可行。Viterbi 算法（1967）的出发点是**最优子结构**：若最优路径在第 $t$ 步经过状态 $q$，则它的前 $t$ 步必须是"以 $q$ 结尾的所有前缀中度量最小的那个"——否则把前缀换成更优者，总度量严格变小，矛盾。因此只需对每个 $(t,q)$ 记录**最佳前缀度量**

$$
D_t(q):=\min_{\text{前缀 }q_0\to\cdots\to q_t=q}\sum_{s=1}^t\gamma_s(q_{s-1},q_s),
$$

它满足把最后一步拆出来的递推：

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

等式成立的理由：到 $q$ 的最优前缀，其上一步必是某个能转移到 $q$ 的 $q'$，且前 $t-1$ 段在"以 $q'$ 结尾"的前缀中最优（否则同样可替换改进），所以枚举 $q'$ 取最小即可覆盖全部候选。同时记录取得最小值的那个前驱作为 backpointer

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

递推到 $t=L$ 后，从 $\arg\min_qD_L(q)$ 出发沿 backpointer 回溯，即得完整的 ML 路径。

**复杂度。** 每个 $(t,q)$ 的计算要枚举至多 $F$ 个前驱，共 $LQ$ 个格子，时间为 $O(LQF)$；若 transition graph 稀疏（$F\ll Q$），这远小于路径数 $QF^L$。memory 取决于回溯策略（存全部 backpointer 是 $O(LQ)$，也有省内存的分治回溯变体）。**Viterbi 的力量正是合并拥有相同 suffix state 的指数多条 prefixes**：两条路径一旦在某时刻汇合到同一状态，未来完全等价，较差者可以永久丢弃——指数大的路径空间被压缩成 $LQ$ 个格子的动态规划表。

### 6.2 一个手算例子

取 $Q=2$、$F=2$、$L=3$ 的完全 trellis（每个状态可向两个状态转移），起始状态固定为 $q_0=0$（$D_0(0)=0$，$D_0(1)=+\infty$）。Branch metrics 给定如下：

| $t$ | $0\to0$ | $0\to1$ | $1\to0$ | $1\to1$ |
|---|---|---|---|---|
| 1 | 1 | 3 | — | — |
| 2 | 2 | 1 | 1 | 2 |
| 3 | 1 | 2 | 2 | 1 |

（$t=1$ 时只有从状态 $0$ 出发的两条边可达。）逐层填表：

- $t=1$：$D_1(0)=D_0(0)+1=1$；$D_1(1)=D_0(0)+3=3$。
- $t=2$：$D_2(0)=\min(D_1(0)+2,\;D_1(1)+1)=\min(3,4)=3$，$B_2(0)=0$；$D_2(1)=\min(D_1(0)+1,\;D_1(1)+2)=\min(2,5)=2$，$B_2(1)=0$。
- $t=3$：$D_3(0)=\min(D_2(0)+1,\;D_2(1)+2)=\min(4,4)=4$；$D_3(1)=\min(D_2(0)+2,\;D_2(1)+1)=\min(5,3)=3$，$B_3(1)=1$。

终点取 $\min_qD_3(q)=3$（状态 $1$）。回溯：$B_3(1)=1$，$B_2(1)=0$，$B_1(0)=0$，得路径 $0\to0\to1\to1$，验算总度量 $\gamma_1(0,0)+\gamma_2(0,1)+\gamma_3(1,1)=1+1+1=3$，与 $D_3(1)$ 一致。整个计算只做了 $6$ 个格子的加法与比较，而暴力枚举要检查 $2^3=8$ 条路径——$L$ 大时这个差距是指数对线性。

## 7. Quantum Viterbi 的构造思路

### 7.1 为什么 trellis 适合相干化

Grice--Meyer 的 quantum Viterbi algorithm（Zoo 238）观察到 trellis 与 FFT butterfly 有相似的 tensor-product structure：演化是"每步一个局部转移"的重复复合，而局部性正是量子线路擅长表达的。概念步骤是：

1. **相干生成路径**：用每步 transition unitary 在叠加中生成所有合法 paths，而不是所有 bit strings——非法转移（不在 trellis 中的边）从一开始就不被生成，这相当于把搜索空间限制在结构化解集内；
2. **可逆计算度量**：reversible 地计算各 branch metrics，把 total likelihood/metric 写成 phase（或用辅助寄存器暂存，最后 uncompute）；
3. **标记较优路径**：构造阈值或"较优路径"标记 oracle——例如翻转 $M(\pi)\le\tau$ 的路径的相位；
4. **振幅放大**：用 specialized amplitude amplification 提高 most-likely path 的 amplitude；
5. **读出与验证**：测量路径 register，classically 重算 score 验证，必要时重复。

(quantum-viterbi-grover-search)=
### 7.2 增益从哪来：$1/p_*$ 对 $1/\sqrt{p_*}$

设初态中最优路径（或某个可接受的高似然路径集合）的总权重为 $p_*$。两种策略的对比是本站 ch03 的标准结论：

- **generic repetition**：制备—测量—检查，平均 $O(1/p_*)$ 次；
- **理想 amplitude amplification**：把成功振幅相干地旋转放大，$O(1/\sqrt{p_*})$ 次。

平方根的来源与 Grover 完全一样：振幅线性增长、概率平方增长。论文指出的**有利 regime** 是 state space $Q$ 很大、frame $L$ 较短且 fanout $F\ll Q$：此时经典 Viterbi 的 $O(LQF)$ 受 $Q$ 拖累，而量子方案的 state preparation 成本随 $F$（每步只需在 $F$ 个后继上叠加）而非稠密 $Q$-by-$Q$ transitions 增长，稀疏性直接转化为量子线路的浅度。

### 7.3 必须保留的注意事项

这**不是**对所有 Viterbi instances 的统一 quadratic theorem。以下每一条都会侵蚀或限定加速，引用该结果时必须一并说明：

- **阈值未知**：标记"最优"路径需要阈值 $\tau$，而最优度量事先未知；需要搜索阈值或用对解数量不敏感的 amplification 变体，带来额外开销；
- **metric 精度**：branch metrics 是（负对数似然导出的）实数，写成 phase 时的有限精度会引入误差，precision bits 计入线路成本；
- **近简并路径**：若次优路径的度量与最优非常接近，"较优路径"集合的成功权重 $p_*$ 与目标定义敏感相关，成功率下降；
- **经典对手很强**：classical DP 已经避免了 path-space brute force（$O(LQF)$ 而非 $O(F^L)$），量子方案比较的对象是这个多项式基线，不是枚举。

因此实际比较必须把 reversible metric oracle、state preparation、amplification 和完整 path readout（读出整条 $L$-步路径的 classical description，而不是只读一个 bit）全部计入端到端成本。这与第 4 节的教训同构：**量子内核的优势是真的，但只有放进完整输入输出管线里结算，才知道剩下多少。**

## 8. 一般码上的量子搜索

回到没有特殊结构的一般线性码。1.3 节把 ML 译码化为"在 $He^T=s$ 的解中找最小重量者"。一个直接思路是逐重量穷举：对固定的猜测重量 $w$，在

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

上搜索满足 $He^T=s$ 的 $e$（标记函数就是计算 syndrome 并比对，多项式时间）。候选数是组合数

$$
|\mathcal E_w|=\binom nw,
$$

因为重量为 $w$ 的向量就是"从 $n$ 个坐标中选 $w$ 个出错位置"。经典穷举要 $O\bigl(\binom nw\bigr)$ 次查询；Grover 搜索把它降为 $O\bigl(\sqrt{\binom nw}\bigr)$ 次 oracle 调用（每次调用的标记电路是多项式规模）。

**这个加速的真实量级。** 指数没有变：取 $w=\alpha n$，由 Stirling 近似（练习 7 推导）

$$
\log_2\binom{n}{\alpha n}\approx n\,H_2(\alpha),
\qquad
H_2(\alpha):=-\alpha\log_2\alpha-(1-\alpha)\log_2(1-\alpha),
$$

所以经典穷举约为 $2^{\,nH_2(\alpha)}$、Grover 约为 $2^{\,nH_2(\alpha)/2}$——**指数减半，仍是 exponential**。在经典信息集译码 (information-set decoding, ISD) 的更精细框架上，quantum walks 可进一步改进指数常数（而不止是整体开平方）。这类改进有切实后果：code-based cryptography（如 McEliece 型方案）的安全参数正是按"最佳已知译码攻击的复杂度"选取的，量子攻击压低指数常数就直接迫使增大密钥尺寸。但方向也要说清楚：这些结果**没有**证明一般 decoding 属于 BQP——指数级问题的指数级加速，不改变其复杂性类别。

(classical-vs-quantum-decoding)=
## 9. 与量子纠错码译码的区别

名字相近，问题不同，值得单独辨析。

**本章的问题是 classical in / classical out**：输入是 classical received word $y$（或它的相干 oracle），输出是 classical message $\widehat u$ 或路径 $\widehat\pi$；量子计算机只是 decoder 的内部实现，噪声作用在 classical bits 上。

**Quantum error-correcting code 的译码**则保护未知 quantum state：噪声是作用在 data qubits 上的 Pauli error，译码器只能测量 stabilizer syndromes（设计上与 logical 信息对易、不泄露 logical state），并据此推断 Pauli-error 的 **equivalence class**（相差一个 stabilizer 的错误对 logical state 作用相同，只需校正到等价类）。两者共享 syndrome、trellis（如量子卷积码）和 maximum-likelihood 思想，但后者必须保留 logical coherence——**不能先把 data qubits 测量再"复制"一份慢慢算**（no-cloning，见本站 ch07），所有处理必须与 logical 信息解耦地进行。

还要区分"quantum algorithm decoding a classical codeword"（本章）与近期文献中的 **quantum decoding problem**（输入本身可能是 codeword-state 的 superposition，例如在量子采样攻击与格/码密码分析中出现）：三者的 oracle 形式、成功标准和安全含义都不相同，读文献时先确认问题设定再比较复杂度数字。

## 10. 小结

**小结。**

- 一般 linear-code ML decoding 是 NP-hard 的；量子加速全部来自结构——simplex code 的 character 结构，或 convolutional code 的 trellis 结构。
- Simplex 译码的支点是一个恒等式：Walsh 系数 $=1-2\,d_H/N$，它把 Hamming distance 变成 Walsh amplitude；$H^{\otimes m}$ 一次给出全部 $2^m$ 个相关系数，无噪声时退化为 Bernstein--Vazirani。
- 成功概率的诚实估计要算清两条账：正确振幅 $(1-2\delta)^2$，以及噪声接近相对距离边界时其他 characters 的竞争。
- Quantum Viterbi 相干生成合法 paths 并放大高似然分支，增益是 $O(1/p_*)\to O(1/\sqrt{p_*})$，优势只在明确参数区间（$Q$ 大、$L$ 短、$F\ll Q$）成立。
- 输入电路（$O(N)$ input circuitry）、soft-metric precision、阈值搜索和 classical path output 都必须计入端到端成本；"oracle 免费"的结论要如实标注模型。
- 对一般码，Grover/quantum walk 只把译码攻击的指数减半或改进常数——这足以影响 code-based cryptography 的参数选取，但不改变问题的指数本质。

## 练习题

**练习 1【线性码、syndrome 与 ML 译码】**（→ [1.3 节](#linear-code-syndrome-ml)）

1. 取 $k=2$、$G=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$（码字集 $C=\{000,101,011,110\}$）。求一个满足 $GH^T=0$ 的校验矩阵 $H$，计算接收字 $y=111$ 的 syndrome，列出全部满足 $He^T=s$ 的重量 $1$ 错误，并由 $d=2$ 解释为什么最轻错误解不唯一。
2. 证明：BSC（$p<1/2$）下 $\Pr(y\mid c)$ 是 $d_H(y,c)$ 的严格递减函数，因此 ML 译码等价于最近码字译码；进一步证明真实错误重量不超过 $\lfloor(d-1)/2\rfloor$ 时最近码字唯一。

> 提示：比较比值 $\frac p{1-p}$ 与 $1$ 的大小；唯一性用三角不等式 $d_H(c,c')\le d_H(c,y)+d_H(y,c')\le 2t$。

**练习 2【Simplex/Hadamard 码与字符正交性】**（→ [2.2 节](#simplex-character-orthogonality)）

1. 对 $m=3$ 写出全部 $8$ 个 Hadamard codewords（即所有 $a\in\mathbb F_2^3$ 的真值表），并验证每个非零 message 的 codeword weight 都是 $4=2^{m-1}$。（提示：用 Lemma 1 的配对论证，不必逐个硬算。）
2. 对 $m=2$、$v=(0,1)$ 列出 $(-1)^{v\cdot x}$ 在全部 $4$ 个 $x$ 上的取值并验证其和为 $0$；再用配对论证说明对任意非零 $v\in\mathbb F_2^m$ 与任意 $m$，$\sum_x(-1)^{v\cdot x}=0$ 恒成立。

> 提示：取 $v$ 的某个非零分量 $v_j=1$，把每个 $x$ 与翻转第 $j$ 位后的 $x^{(j)}$ 配成一对。

**练习 3【Walsh 系数与最近码字译码】**（→ [2.3 节](#walsh-nearest-codeword)）

1. 设 $N=8$，接收字 $y$ 与某个 codeword $c_a$ 的 Hamming 距离为 $3$。用定义 $\widehat y(a)=\frac1N\sum_x(-1)^{y_x\oplus c_a(x)}$ 直接计算 $\widehat y(a)$，并与公式 $1-\frac{2\,d_H}{N}$ 核对。
2. 证明恒等式 $\widehat y(a)=1-\frac{2\,d_H(y,c_a)}{N}$ 对任意 $y$ 与 $c_a$ 成立，并据此说明"取最大 Walsh 系数的 $a$"与"最近码字译码"给出同一个译码结果。

> 提示：把求和按"坐标相同"与"坐标不同"分成两组，各贡献 $+1$ 与 $-1$。

**练习 4【相位反冲与 Walsh--Hadamard 译码】**（→ [3.2 节](#phase-kickback-walsh-decoding)）

1. 写出 oracle $O_y|x,z\rangle=|x,z\oplus y_x\rangle$ 作用在 $|x\rangle|-\rangle$ 上的结果，并对 $y_x=0$ 与 $y_x=1$ 两种情形分别验证相位反冲因子的符号。
2. 证明 character orthogonality 的推广形式：对任意 $a,b\in\mathbb F_2^m$，$\frac1N\sum_x(-1)^{(a\oplus b)\cdot x}=\delta_{a,b}$，并用它严格推出 3.3 节无噪声时 $H^{\otimes m}|\psi_y\rangle=|a_*\rangle$。

> 提示：令 $v=a\oplus b$，分 $v=0$ 与 $v\neq0$ 讨论；无噪声时各振幅为 $\widehat y(a)=\delta_{a,a_*}$。

**练习 5【译码成功概率与输入电路成本】**（→ [3.3 节](#decoding-success-probability)）

1. 若 error fraction $\delta=0.1$，计算正确 simplex message 的单次测量 amplitude 与 probability；其余概率总量是多少？若重复 $5$ 次独立测量并逐位多数表决，定性说明为什么失败概率被压低。
2. 解释：为什么按 index 读取一个任意 $N$-bit received word 来实现 $O_y$ 需要 $O(N)$ 的输入电路，而量子核心只用到 $m=\log_2 N$ 个 qubits？据此说明"查询复杂度 $O(1)$"与"对任意经典数据的 logarithmic-time 译码"为何是两个不同的结论。
3. 推广 3.4 节的小例子：设 $y$ 是 $c_{a_*}$ 在坐标集合 $S$（$|S|=t$）上出错的结果，证明输出振幅满足 $\widehat y(a)=\delta_{a,a_*}-\frac{2}{N}\sum_{x\in S}(-1)^{(a\oplus a_*)\cdot x}$，并用 $t=2$、$m=3$ 自行取一组 $S$ 验证概率归一化 $\sum_a|\widehat y(a)|^2=1$。

> 提示：把 $(-1)^{y_x}$ 写成 $(-1)^{c_{a_*}(x)}$ 乘上错误集合 $S$ 上的翻转因子，再按 $S$ 内、外拆分求和。

**练习 6【卷积码、trellis 与 Viterbi 递推】**（→ [6.1 节](#viterbi-trellis-recursion)）

1. 写出 branch metric $\gamma_t$、路径度量 $M(\pi)$ 与 Viterbi 递推 $D_t(q)=\min_{q'\to q}[D_{t-1}(q')+\gamma_t(q',q)]$ 中各量的含义，并解释为什么填表复杂度是 $O(LQF)$、而路径总数是 $\sim QF^L$。
2. 在 6.2 节的 $Q=2$ trellis 上，把 $\gamma_3(1\to1)$ 从 $1$ 改为 $4$，重新手算整张 Viterbi 表 $D_t(q)$ 并给出新的最优路径与总度量。（答案：最优变为 $0\to0\to0\to0$ 或经状态 $1$ 的某条路径，总度量 $4$——请验证是哪一条。）

**练习 7【量子 Viterbi 与一般码量子搜索】**（→ [7.2 节](#quantum-viterbi-grover-search)）

1. 设最优路径在初态中的总权重为 $p_*$。分别写出 generic repetition 与理想 amplitude amplification 达到常数成功概率所需的重复次数，并说出 Grice--Meyer 增益成立的参数区间（$Q$、$L$、$F$ 各满足什么条件）。
2. 列出至少两条侵蚀 quantum Viterbi 加速的注意事项（如阈值未知、metric 精度、近简并路径、经典基线），并解释为什么公平的比较对象是 $O(LQF)$ 的经典动态规划而不是路径枚举。
3. 用 Stirling approximation $\ln n!=n\ln n-n+O(\log n)$ 推导 $\log_2\binom{n}{\alpha n}=nH_2(\alpha)+O(\log n)$，从而说明 weight-$w=\alpha n$ 的 Grover syndrome search 查询数约为 $2^{\,nH_2(\alpha)/2}$。对 $\alpha=0.1$ 数值估计 $H_2(\alpha)$ 与 Grover 后的指数。

> 提示：把 $\binom{n}{\alpha n}=\frac{n!}{(\alpha n)!\,((1-\alpha)n)!}$ 的三个阶乘逐个代入 Stirling 近似。

**练习 8【与量子纠错译码的区别】**（→ [第 9 节](#classical-vs-quantum-decoding)）

1. 从"输入与输出的类型""噪声作用的对象""译码器可以测量什么"三个维度中任取两个，写出本章的量子译码问题与量子纠错码译码问题的区别。
2. 解释量子纠错译码为什么"不能先把 data qubits 测量再复制一份慢慢算"（联系 no-cloning 定理），并说明 stabilizer syndrome 测量为何不泄露 logical state 的信息。

> 提示：stabilizer 算符与 logical 算符对易，测量 syndrome 不会坍缩 logical 叠加。

## 参考文献与 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)。