量子译码：线性码、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 算法的相位查询结构，对应 Barg--Zhou 的量子 simplex 译码算法（Zoo 239）；

  • Convolutional code 的合法 codewords 形成稀疏 trellis 上的路径，Viterbi 的动态规划可以被相干化，对应 Grice--Meyer 的 quantum Viterbi algorithm（Zoo 238）；

  • 对一般线性码，量子搜索（Grover）与量子行走只能把穷举译码的指数开平方或改进指数常数，这在密码分析中有实际意义（见本站量子密码分析），但不是多项式加速。

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

本课知识点

  1. 线性码、syndrome 与 ML 译码——能写出 \([n,k,d]\) 线性码的生成矩阵与校验矩阵刻画，推导 syndrome \(s=Hy^T=He^T\) 只依赖错误向量，并证明 BSC 下 ML 译码等价于最小重量译码。

  2. Simplex/Hadamard 码与字符正交性——能写出 Hadamard 码作为线性函数真值表的构造，并用配对论证证明最小距离为 \(2^{m-1}\) 与字符正交性 \(\frac1N\sum_x(-1)^{v\cdot x}=\delta_{v,0}\)。

  3. Walsh 系数与最近码字译码——能推导 Walsh 系数公式 \(\widehat y(a)=1-\frac{2\,d_H(y,c_a)}{N}\)，并解释最大 Walsh 系数译码与最近码字译码为何是同一问题的两种写法。

  4. 相位反冲与 Walsh--Hadamard 译码——能用相位反冲把接收字制备成相位态 \(|\psi_y\rangle\)，并证明 \(H^{\otimes m}|\psi_y\rangle\) 的第 \(a\) 个振幅恰为 Walsh 系数 \(\widehat y(a)\)。

  5. 译码成功概率与输入电路成本——能计算有噪声时的单次成功概率 \((1-2\delta)^2\) 并设计重复多数表决方案，同时说明 \(O(N)\) 输入电路成本为何必须计入端到端复杂度。

  6. 卷积码、trellis 与 Viterbi 递推——能把卷积码译码写成 trellis 上可加度量的最优路径问题，写出 Viterbi 递推并手算小例子的填表过程。

  7. 量子 Viterbi 与一般码量子搜索——能解释振幅放大把重复次数从 \(O(1/p_*)\) 降到 \(O(1/\sqrt{p_*})\) 的适用条件，并用 Stirling 近似推导 Grover 只把 \(\binom nw\) 穷举的指数减半。

  8. 与量子纠错译码的区别——能从输入输出类型、噪声对象与 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"，这是线性码译码的标准化简。

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、伪随机性）和本节的量子算法中非常自然。

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 节会反复使用它。

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 节会回到这一点。

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 谱分析"的量子实现。

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 递推

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 验证，必要时重复。

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——指数级问题的指数级加速，不改变其复杂性类别。

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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  1. 从"输入与输出的类型""噪声作用的对象""译码器可以测量什么"三个维度中任取两个，写出本章的量子译码问题与量子纠错码译码问题的区别。

  2. 解释量子纠错译码为什么"不能先把 data qubits 测量再复制一份慢慢算"（联系 no-cloning 定理），并说明 stabilizer syndrome 测量为何不泄露 logical state 的信息。

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

参考文献与 Zoo 覆盖