量子译码

经典纠错码 (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 算法的相位查询结构，对应 Barg—Zhou 的量子 simplex 译码算法（Zoo 239）；
• Convolutional code 的合法 codewords 形成稀疏 trellis 上的路径，Viterbi 的动态规划可以被相干化，对应 Grice—Meyer 的 quantum Viterbi algorithm（Zoo 238）；
• 对一般线性码，量子搜索（Grover）与量子行走只能把穷举译码的指数开平方或改进指数常数，这在密码分析中有实际意义（见量子密码分析），但不是多项式加速。

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

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=\underset{c\in C,c\ne 0}{\min }\mathrm{wt}(c),\mathrm{wt}(c):=\#\{i:c_i=1\}.$$

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

$$G{H}^T=0,C=\{c\in {\mathbb{F}}_2^n:H{c}^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:=H{y}^T=H(c\oplus e{)}^T=H{c}^T\oplus H{e}^T=H{e}^T.$$

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

1.3 为什么 ML 译码就是最小重量译码

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

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

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

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

$$\hat{e}=\arg \underset{e:H{e}^T=s}{\min }\mathrm{wt}(e),\hat{c}=y\oplus \hat{e}.$$

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

$$d_H(c,c^{\prime })\le d_H(c,y)+d_H(y,c^{\prime })\le 2t\le d-1<d,$$

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

难点所在。 “解线性方程组 $H{e}^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(\mathrm{mod}2),a\cdot x:=\underset{i=1}{\overset{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、伪随机性）和本节的量子算法中非常自然。

2.2 最小距离的完整证明

Lemma 1. 对任意 $a\ne 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\ne 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\ne 0$，

$$\sum _{x\in {\mathbb{F}}_2^m}(-1{)}^{v\cdot x}=2^{m-1}(1+(-1))=0,$$

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

$$\frac{1}{N}\sum _{x\in {\mathbb{F}}_2^m}(-1{)}^{v\cdot x}={\delta }_{v,0}.$$

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

2.3 译码问题的重述

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

$$\hat{y}(a):=\frac{1}{N}\sum _x(-1{)}^{y_x\oplus c_a(x)}.$$

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

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

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

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

3.1 输入模型：相位反冲

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

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

第一个寄存器是 $m={\log }_{2}N$ 个 qubits 的 index register，第二个是单 qubit target。把 target 制备在 $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$，就是学过的 phase kickback 技巧：

$$O_y|x⟩|-⟩=\frac{|x,y_x⟩-|x,y_x\oplus 1⟩}{\sqrt{2}}=(-1{)}^{y_x}|x⟩|-⟩.$$

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

$$\frac{1}{\sqrt{N}}\sum _x|x⟩|-⟩⟼|{\psi }_y⟩|-⟩,|{\psi }_y⟩=\frac{1}{\sqrt{N}}\sum _x(-1{)}^{y_x}|x⟩.$$

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

3.2 Walsh—Hadamard 变换一步求出全部相关系数

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

$$H^{\otimes m}|x⟩=\frac{1}{\sqrt{N}}\sum _{a\in {\mathbb{F}}_2^m}(-1{)}^{a\cdot x}|a⟩,$$

代入 $|{\psi }_y⟩$ 并按 $a$ 归并系数：

$$H^{\otimes m}|{\psi }_y⟩=\frac{1}{\sqrt{N}}\sum _x(-1{)}^{y_x}\cdot \frac{1}{\sqrt{N}}\sum _a(-1{)}^{a\cdot x}|a⟩=\sum _{a\in {\mathbb{F}}_2^m}\underset{\hat{y}(a)}{\underbrace{\left[\frac{1}{N}\sum _x(-1{)}^{y_x\oplus a\cdot x}\right]}}|a⟩.$$

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

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

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

3.3 无噪声与有噪声的成功概率

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

$$\hat{y}(a)=\frac{1}{N}\sum _x(-1{)}^{(a\oplus a_{\ast })\cdot x}={\delta }_{a,a_{\ast }},\text{即}{H}^{\otimes m}|{\psi }_y⟩=|a_{\ast }⟩.$$

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

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

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

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

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

3.4 一个完整的小例子

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

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

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

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

$$\hat{y}(a)=\frac{1}{8}\sum _x(-1{)}^{y_x\oplus a\cdot x}=\underset{{\delta }_{a,a_{\ast }}}{\underbrace{\frac{1}{8}\sum _x(-1{)}^{(a_{\ast }\oplus a)\cdot x}}}-\frac{2}{8}(-1{)}^{(a_{\ast }\oplus a)\cdot 011}.$$

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

• $a=a_{\ast }$：振幅 $=1-\frac{2}{8}=\frac{3}{4}$，概率 $\frac{9}{16}=0.5625$；
• $a\ne a_{\ast }$（共 $7$ 个）：正交性使第一项为 $0$，振幅 $=\mp \frac{1}{4}$，概率各 $\frac{1}{16}$。

检查归一化：$\frac{9}{16}+7\times \frac{1}{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 }_{2}N$ 个 qubits 上，用 $m$ 个 Hadamard gates。Barg—Zhou 的完整实现进一步把 computation subcircuit 压到 $O({\log }^{2}N)$ 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,\dots ,Q\}$（$Q$ 个状态，对应移位寄存器的内容），每来一个 input symbol $u_t$，按确定规则更新状态并产生该步的输出：

$$q_t=T(q_{t-1},u_t),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 Q{F}^L$ 量级——随 $L$ 指数增长，这就是译码难的原因；但”每一步只有 $F$ 个选择、汇合到 $Q$ 个状态”的稀疏结构，正是经典与量子算法都要利用的东西。

5.2 从似然到路径度量

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

$$\mathrm{Pr}(r_1,\dots ,r_L\mid \pi )=\prod _{t=1}^L\mathrm{Pr}(r_t\mid q_{t-1}\to q_t).$$

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

$${\gamma }_t(q^{\prime },q)=-\log \mathrm{Pr}(r_t\mid q^{\prime }\to q),$$

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

$$M(\pi )=\sum _{t=1}^L{\gamma }_t(q_{t-1},q_t).$$

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

6. Classical Viterbi 递推

6.1 最优子结构与递推

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

$$D_t(q):=\underset{\text{前缀 }{q}_0\to \cdots \to q_t=q}{\min }\sum _{s=1}^t{\gamma }_s(q_{s-1},q_s),$$

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

$$D_t(q)=\underset{q^{\prime }\to q}{\min }\left[D_{t-1}(q^{\prime })+{\gamma }_t(q^{\prime },q)\right].$$

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

$$B_t(q)=\arg \underset{q^{\prime }\to q}{\min }\left[D_{t-1}(q^{\prime })+{\gamma }_t(q^{\prime },q)\right],$$

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

复杂度。 每个 $(t,q)$ 的计算要枚举至多 $F$ 个前驱，共 $LQ$ 个格子，时间为 $O(LQF)$；若 transition graph 稀疏（$F\ll Q$），这远小于路径数 $Q{F}^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\to 0$	$0\to 1$	$1\to 0$	$1\to 1$
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 }_q{D}_3(q)=3$（状态 $1$）。回溯：$B_3(1)=1$，$B_2(1)=0$，$B_1(0)=0$，得路径 $0\to 0\to 1\to 1$，验算总度量 ${\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 验证，必要时重复。

7.2 增益从哪来：$1/p_{\ast }$ 对 $1/\sqrt{p_{\ast }}$

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

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

平方根的来源与 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_{\ast }$ 与目标定义敏感相关，成功率下降；
• 经典对手很强：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 译码化为”在 $H{e}^T=s$ 的解中找最小重量者”。一个直接思路是逐重量穷举：对固定的猜测重量 $w$，在

$${\mathcal{E}}_w=\{e\in {\mathbb{F}}_2^n:\mathrm{wt}(e)=w\}$$

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

$$|{\mathcal{E}}_w|=\left(\genfrac{}{}{0ex}{}{n}{w}\right),$$

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

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

$${\log }_2\left(\genfrac{}{}{0ex}{}{n}{\alpha n}\right)\approx n{H}_2(\alpha ),H_2(\alpha ):=-\alpha {\log }_2\alpha -(1-\alpha ){\log }_2(1-\alpha ),$$

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

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

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

本词条的问题是 classical in / classical out：输入是 classical received word $y$（或它的相干 oracle），输出是 classical message $\hat{u}$ 或路径 $\hat{\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，见），所有处理必须与 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-2d_H/N$，它把 Hamming distance 变成 Walsh amplitude；$H^{\otimes m}$ 一次给出全部 $2^m$ 个相关系数，无噪声时退化为 Bernstein—Vazirani。
• 成功概率的诚实估计要算清两条账：正确振幅 $(1-2\delta {)}^2$，以及噪声接近相对距离边界时其他 characters 的竞争。
• Quantum Viterbi 相干生成合法 paths 并放大高似然分支，增益是 $O(1/p_{\ast })\to O(1/\sqrt{p_{\ast }})$，优势只在明确参数区间（$Q$ 大、$L$ 短、$F\ll Q$）成立。
• 输入电路（$O(N)$ input circuitry）、soft-metric precision、阈值搜索和 classical path output 都必须计入端到端成本；“oracle 免费”的结论要如实标注模型。
• 对一般码，Grover/quantum walk 只把译码攻击的指数减半或改进常数——这足以影响 code-based cryptography 的参数选取，但不改变问题的指数本质。

习题。

1. 对 $m=3$ 写出全部 $8$ 个 Hadamard codewords（即所有 $a\in {\mathbb{F}}_2^3$ 的真值表），并验证每个非零 message 的 codeword weight 都是 $4=2^{m-1}$。（提示：用 Lemma 1 的配对论证，不必逐个硬算。）
2. 若 error fraction $\delta =0.1$，计算正确 simplex message 的单次测量 amplitude 与 probability；其余概率总量是多少？若重复 $5$ 次独立测量并逐位多数表决，定性说明为什么失败概率被压低。
3. 在 6.2 节的 $Q=2$ trellis 上，把 ${\gamma }_3(1\to 1)$ 从 $1$ 改为 $4$，重新手算整张 Viterbi 表 $D_t(q)$ 并给出新的最优路径与总度量。（答案：最优变为 $0\to 0\to 0\to 0$ 或经状态 $1$ 的某条路径，总度量 $4$——请验证是哪一条。）
4. 用 Stirling approximation $\ln n!=n\ln n-n+O(\log n)$ 推导 ${\log }_2\left(\genfrac{}{}{0ex}{}{n}{\alpha n}\right)=n{H}_2(\alpha )+O(\log n)$，从而说明 weight-$w=\alpha n$ 的 Grover syndrome search 查询数约为 $2^{n{H}_2(\alpha )/2}$。对 $\alpha =0.1$ 数值估计 $H_2(\alpha )$ 与 Grover 后的指数。
5. 证明 character orthogonality 的推广形式：对任意 $a,b\in {\mathbb{F}}_2^m$，$\frac{1}{N}{\sum }_x(-1{)}^{(a\oplus b)\cdot x}={\delta }_{a,b}$，并用它严格推出 3.3 节无噪声时 $H^{\otimes m}|{\psi }_y⟩=|a_{\ast }⟩$。
6. 推广 3.4 节的小例子：设 $y$ 是 $c_{a_{\ast }}$ 在坐标集合 $S$（$|S|=t$）上出错的结果，证明输出振幅满足 $\hat{y}(a)={\delta }_{a,a_{\ast }}-\frac{2}{N}{\sum }_{x\in S}(-1{)}^{(a\oplus a_{\ast })\cdot x}$，并用 $t=2$、$m=3$ 自行取一组 $S$ 验证概率归一化 ${\sum }_a|\hat{y}(a){|}^2=1$。

参考文献与 Zoo 覆盖

• Zoo 编号 238：Jon R. Grice 与 David A. Meyer, A quantum algorithm for Viterbi decoding of classical convolutional codes。
• Zoo 编号 239：Alexander Barg 与 Shiyu Zhou, A quantum decoding algorithm of the simplex code。
• 延伸阅读：Bernstein—Vazirani、Amplitude amplification和量子 subset sum。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch16-cryptanalysis-coding/quantum-decoding
• 内容遵循 CC BY-NC-SA 4.0 许可协议