Decoded Quantum Interferometry

Decoded Quantum Interferometry（DQI）是 Jordan 等人在 2024 年提出的一类量子优化算法（arXiv:2408.08292，Zoo 453）。它的出发点是组合优化中一个朴素而普遍的观察：许多约束满足问题的目标函数在 Boolean Fourier 基下是稀疏的——它只由少数几个”约束行向量”对应的频率叠加而成。DQI 把”偏向高目标值的振幅态”在 Fourier 域展开；若目标由稀疏局部/线性约束组成，频率标签就是少量约束向量的和。要让这些”Fourier 历史”相干地合并成目标态，必须清除产生同一频率（syndrome）的不同组合标签，而这恰好是一个经典编码理论中的 syndrome decoding 问题。于是解码器的性能直接决定算法的优化能力：解码半径越大，可实现的 polynomial filter degree 越高，对优解的测量偏置越强。编码理论半个世纪积累的解码算法（Berlekamp–Massey、belief propagation 等）因此被整体搬进了量子优化。

本词条假设读者已熟悉 Boolean Fourier 分析的基本记号、Hadamard 变换与相位反冲（参见 量子 Fourier 变换 与 振幅放大），以及多项式方法制备对角函数态的思想（参见 QSP 教程，但本词条不需要 QSP 本身）。

1. 问题背景：优化问题、经典基线与 DQI 的位置

我们关心的是约束满足与最大化问题（CSP / max-CSP）：给 $n$ 个变量和 $m$ 个约束，找一个赋值使满足的约束尽可能多。max-XORSAT（每个约束是若干变量的奇偶方程）、MaxCut、max-SAT 都属于这一类。这些问题一般 NP-hard，不可能指望任何算法（量子或经典）在多项式时间内精确求解一般实例；现实的比较标准是近似比 (approximation ratio)：算法输出的期望满足比例，对比最优值或对比某个基线。

经典算法能做什么？最平凡的基线是随机赋值：对每个约束，均匀随机赋值命中其允许集合的概率是某个常数 $q_0$（例如 XORSAT 中 $q_0=1/2$），所以随机赋值期望满足 $q_{0}m$ 个约束。更好的经典算法（半正定规划舍入、局部搜索、模拟退火、针对特定结构的启发式）可以在特定问题族上显著超过 $q_0$，但对一般 max-CSP，多项式时间可证明的近似比存在已知上限，且许多上限与 hardness 结果匹配。

DQI 的价值主张是：当目标函数的 Fourier 谱由线性约束生成、且对应的对偶码存在高效解码器时，量子干涉可以把”解码半径”转换成”近似比”，在某些参数区间给出超过论文所分析的已知经典多项式时间方法的期望满足比例。但必须在一开始就强调两条保留条款，它们会贯穿全文：

• 这不是已证明的复杂度分离。目标参数区间尚无 standard assumption 下的 classical hardness theorem，正确说法是相对已知算法的 apparent/superpolynomial speedup，而不是”经典算法做不到”。事实上后文会看到（第 8 节），在 DQI 可证明非平凡保证的某些实例上，后来真的找到了经典多项式时间算法。
• 渐近高效不等于近期低成本。具体资源估计可达 $10^8$ logical Toffolis 与数千逻辑 qubits。

2. Max-XORSAT 的 Fourier 稀疏性

我们从最简单的载体问题 max-XORSAT 开始，把”Fourier 稀疏”这件事彻底算清楚。

2.1 问题与目标函数

给定

$$B\in {\mathbb{F}}_2^{m\times n},v\in {\mathbb{F}}_2^m.$$

$B$ 的第 $i$ 行记为 $b_i\in {\mathbb{F}}_2^n$，第 $i$ 个约束是线性方程

$$b_i\cdot x=v_i(\mathrm{mod}2),$$

其中 $b_i\cdot x={\sum }_{j=1}^n{b}_{ij}{x}_j(\mathrm{mod}2)$ 是 ${\mathbb{F}}_2$ 内积。max-XORSAT 要求找 $x\in {\mathbb{F}}_2^n$ 使满足的约束数最大。

定义”满足数减违反数”为目标函数

$$f(x)=\sum _{i=1}^m(-1{)}^{v_i+b_i\cdot x}.$$

为什么是 $\pm 1$ 的形式？因为指数 $v_i+b_i\cdot x$ 取 mod 2：当第 $i$ 个约束被满足时 $v_i+b_i\cdot x=0(\mathrm{mod}2)$，该项贡献 $+1$；被违反时贡献 $-1$。设 $x$ 满足 $s(x)$ 个约束、违反 $m-s(x)$ 个，则

$$f(x)=s(x)\cdot (+1)+(m-s(x))\cdot (-1)=2s(x)-m,$$

反解出

$$s(x)=\frac{m+f(x)}{2}.$$

所以最大化满足数与最大化 $f(x)$ 是同一个问题，$f$ 只是满足数的仿射变换。后文全部用 $f$ 工作，因为它在 Fourier 基下形式最简洁。

2.2 Boolean Fourier 变换复习

对 $b\in {\mathbb{F}}_2^n$，定义字符 (character)

$${\chi }_b(x)=(-1{)}^{b\cdot x}.$$

这组 $2^n$ 个函数在归一化内积 $⟨g,h⟩=2^{-n}{\sum }_{x}g(x)h(x)$ 下正交归一：

$$2^{-n}\sum _x{\chi }_b(x){\chi }_{b^{\prime }}(x)={\delta }_{b,b^{\prime }}.$$

证明：左边等于 $2^{-n}{\sum }_x(-1{)}^{(b+b^{\prime })\cdot x}$。若 $b=b^{\prime }$，每项都是 $1$，和为 $2^n$；若 $b\ne b^{\prime }$，取某个坐标 $j$ 使 $b_j\ne b_j^{\prime }$，把 $x$ 与 $x+e_j$ 配对，两项符号相反、两两抵消，和为 $0$。由此任何 $g:{\mathbb{F}}_2^n\to \mathbb{R}$ 都有唯一展开 $g={\sum }_b\hat{g}(b){\chi }_b$，并有 Parseval 恒等式 $2^{-n}{\sum }_{x}g(x{)}^2={\sum }_b\hat{g}(b{)}^2$。

2.3 $f$ 只有 $m$ 个非零频率

把 $f$ 的定义式直接读成 Fourier 展开：

$$f(x)=\sum _{i=1}^m(-1{)}^{v_i}{\chi }_{b_i}(x),{\chi }_b(x)=(-1{)}^{b\cdot x}.$$

也就是说，$f$ 的全部非零 Fourier 系数就是 $\hat{f}(b_i)=(-1{)}^{v_i}$，至多 $m$ 个，频率恰好是约束矩阵的行向量。约束越稀疏（每行只含少量变量），这些频率的 Hamming weight 越低；但即使没有稀疏性，”$f$ 只有 $m$ 个非零频率”这一点已经成立——这就是标题中”Fourier 稀疏目标”的含义：谱的支持集大小 $m$ 远小于一般的 $2^n$。

这个性质有一个直接的量子后果。Hadamard 变换作用在计算基矢上给出

$$H^{\otimes n}|b⟩=\frac{1}{\sqrt{2^n}}\sum _{x\in {\mathbb{F}}_2^n}(-1{)}^{b\cdot x}|x⟩=\frac{1}{\sqrt{2^n}}\sum _x{\chi }_b(x)|x⟩,$$

这只是 $H|0⟩=(|0⟩+|1⟩)/\sqrt{2}$、$H|1⟩=(|0⟩-|1⟩)/\sqrt{2}$ 逐比特展开的合并写法。因此

$$H^{\otimes n}\left(\sum _{i=1}^m(-1{)}^{v_i}|b_i⟩\right)=\frac{1}{\sqrt{2^n}}\sum _x\left(\sum _i(-1{)}^{v_i}{\chi }_{b_i}(x)\right)|x⟩=\frac{1}{\sqrt{2^n}}\sum _{x}f(x)|x⟩.$$

左边括号里是一个只含 $m$ 个计算基矢的叠加态，原则上可以用 $\mathrm{poly}(m,n)$ 个门制备（第 5 节给出系统构造）。所以 ${\sum }_{x}f(x)|x⟩$ 可从 ${\sum }_i(-1{)}^{v_i}|b_i⟩$ 做 Hadamard 得到。

2.4 为什么这还不够

把上式归一化。由 Parseval，${\sum }_{x}f(x{)}^2=2^n{\sum }_b\hat{f}(b{)}^2=2^{n}m$（各 $b_i$ 不同时；一般有相同的 $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ 级修正，结论不变），所以测量 $x$ 的概率为

$$p(x)=\frac{f(x{)}^2}{2^{n}m}.$$

这确实把概率质量推向了 $|f|$ 大的赋值，但有两个缺陷：

• 符号盲：$f(x{)}^2$ 对正负对称，$f$ 很负的坏赋值（违反极多约束）与 $f$ 很正的好赋值得到同样的放大。第 3 节的数值例子会看到这个缺陷真实发生。
• 放大倍数有限：$|f|\le m$，所以单个赋值的概率至多是均匀分布的 $m$ 倍；当 $m=\mathrm{poly}(n)$ 时，相对随机基线的期望改进是多项式因子级别的，不足以改变近似比的量级。

所以测量概率仅按 $f(x{)}^2$ 偏置，优化力度有限。要得到真正强的优化偏置，需要把 $f$ 换成一个在大 $f$ 处增长更快的函数——这就引出多项式滤波。

3. 一个可手算的小例子

在进入一般理论前，用一个最小例子把上面的每个对象都算一遍。取 $n=2$、$m=3$：

$$b_1=(1,0),v_1=0;b_2=(0,1),v_2=0;b_3=(1,1),v_3=1,$$

即三个约束 $x_1=0$、$x_2=0$、$x_1+x_2=1$。注意三者不能同时成立（前两条强制 $x_1+x_2=0$），所以最大满足数是 $2$。目标函数

$$f(x)=(-1{)}^{x_1}+(-1{)}^{x_2}+(-1{)}^{1+x_1+x_2}.$$

逐点计算（每行列出三个约束的逐项贡献与 $f$、$s=(3+f)/2$）：

$$\begin{array}{cccccc}x& (-1{)}^{x_1}& (-1{)}^{x_2}& (-1{)}^{1+x_1+x_2}& f(x)& s(x)\\ 00& +1& +1& -1& 1& 2\\ 10& -1& +1& +1& 1& 2\\ 01& +1& -1& +1& 1& 2\\ 11& -1& -1& -1& -3& 0\end{array}$$

最优赋值是 $00,10,01$（满足 2 个约束），最差的是 $11$（满足 0 个）。Fourier 展开直接读出：$f={\chi }_{(1,0)}+{\chi }_{(0,1)}-{\chi }_{(1,1)}$，确实只有 $m=3$ 个非零频率，系数 $(-1{)}^{v_i}=+1,+1,-1$ 与上表一致。

再看 2.4 节的两个缺陷。按 $f^2$ 偏置的测量分布为

$$p(x)\propto f(x{)}^2=(1,1,1,9),$$

即 $p(11)=9/12$——概率质量最大地落在最差的赋值上，因为 $f(11)=-3$ 的绝对值最大。符号盲不是理论顾虑，在这个 3 约束例子里就直接翻车。

而如果能把振幅制备成 $P(f)$ 的形式、取一个在大 $f$ 处大、负 $f$ 处小的多项式，例如最简单的 $P(f)=(m+f)/2=s$（满足数本身，是 $f$ 的一次多项式），则振幅为 $(2,2,2,0)$，测量概率 $(1/3,1/3,1/3,0)$，最差赋值被精确排除，三个最优赋值平分概率。这个例子说明两件事：(i) 只需要按 $f$ 的值做”滤波”就能修正符号问题；(ii) 滤波函数 $P$ 的 degree 决定实现的难度——下面会看到，degree-$\ell$ 的 $P$ 要求解码器能纠正 weight 不超过 $\ell$ 的错误。

4. 用多项式放大高目标值

4.1 DQI 目标态

DQI 的目标态是把”按 $f$ 滤波”推到极致的振幅态

$$|P(f)⟩\propto \sum _{x}P(f(x))|x⟩,$$

其中 $P$ 为 degree-$\ell$ polynomial，$\ell$ 是一个可选择的参数。第 5 节将证明：系数取适当的正交多项式/Krawtchouk 系数 $w_0,\dots ,w_{\ell }$ 时，这个态恰好可以用一条高效电路制备；而 $P$ 的形状可以在制备前离线优化，使测量分布下的期望 objective 最大。直觉上，degree 越高，$P$ 越能逼近”只在大 $f$ 处非零”的陡峭函数，$P(f{)}^2$ 越集中在大 $f$ 区域——代价是电路里需要更强的解码器。

为什么自然出现 Krawtchouk 多项式？当 $x$ 均匀随机时，每个 $(-1{)}^{b_i\cdot x}$ 是独立的 $\pm 1$ 随机变量（对一般位置的 $b_i$），$f(x)$ 近似是 $m$ 步随机游走，其分布是二项分布；以二项分布为权重的正交多项式系正是 Krawtchouk 多项式。DQI 论文在这一框架下最大化期望 objective，得到最优的 $w_0,\dots ,w_{\ell }$。我们不需要重现这个优化，只需要记住结论：给定允许的 degree $\ell$，存在可计算的最优滤波器；$\ell$ 越大，偏置越强。

4.2 $f^k$ 的 Fourier 频率从哪里来

关键问题是：$P(f)$ 作为 $f$ 的多项式，它的 Fourier 谱长什么样？只要把 $f^k$ 展开即可。由 $f$ 的定义，

$$f(x{)}^k=\sum _{i_1,\dots ,i_k\in [m]}(-1{)}^{v_{i_1}+\cdots +v_{i_k}}{\chi }_{b_{i_1}}(x)\cdots {\chi }_{b_{i_k}}(x).$$

字符的乘积仍是字符：${\chi }_b(x){\chi }_{b^{\prime }}(x)=(-1{)}^{(b+b^{\prime })\cdot x}={\chi }_{b+b^{\prime }}(x)$（加法在 ${\mathbb{F}}_2^n$ 中）。所以上面每一项的频率是 $k$ 个行向量之和 $b_{i_1}+\cdots +b_{i_k}$，相位是 $(-1{)}^{v_{i_1}+\cdots +v_{i_k}}$。

把 $\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ 个有序 $k$ 元组按”哪些行被选中了奇数次”分组。用 indicator 向量

$$y\in {\mathbb{F}}_2^m,y_j=(\text{行 }j\text{ 被选中的次数})\mathrm{mod}2,$$

则该组的频率与相位可以紧凑地写成

$$\sum _j{y}_j{b}_j=B^{T}y,(-1{)}^{{\sum }_j{y}_j{v}_j}=(-1{)}^{v\cdot y}.$$

第一个等号就是矩阵转置乘向量的定义：$B^T\in {\mathbb{F}}_2^{n\times m}$，$(B^{T}y{)}_i={\sum }_j{B}_{ji}{y}_j={\sum }_j{y}_j(b_j{)}_i$，即把行向量按 $y$ 做 ${\mathbb{F}}_2$ 线性组合。注意在 ${\mathbb{F}}_2$ 中，同一行被选中偶数次的贡献相互抵消，所以 weight $|y|$ 与 $k$ 同奇偶且 $|y|\le k$；在整理好的展开中可以直接把 degree-$\ell$ 多项式的谱写成按 $|y|=k$ 分层、$k\le \ell$ 的形式（每一层把 $|y|=k$ 的项归一化为 Dicke 型叠加）。

4.3 Fourier 域中的目标态

综合上节，$|P(f)⟩$ 的 Fourier transform（即 Hadamard 之前的形态）形如

$$\sum _{k=0}^{\ell }\frac{w_k}{\sqrt{\left(\genfrac{}{}{0ex}{}{m}{k}\right)}}\sum _{|y|=k}(-1{)}^{v\cdot y}|B^{T}y⟩,$$

其中 $w_k$ 就是 $P$ 的 Krawtchouk 展开系数，${\left(\genfrac{}{}{0ex}{}{m}{k}\right)}^{-1/2}$ 是把每个 weight 层归一化的因子（weight-$k$ 的 $y$ 共 $\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ 个）。这个态的物理图像是：$y$ 是一条”Fourier 历史”，记录频率 $B^{T}y$ 是由哪些约束行组合出来的；$(-1{)}^{v\cdot y}$ 是这条历史携带的相位。

这里藏着整个算法唯一的难点：不同的历史可能产生同一个频率。若 $y\ne y^{\prime }$ 但 $B^{T}y=B^T{y}^{\prime }$，那么上式中 $|B^{T}y⟩$ 这一项的振幅是两条（甚至更多条）历史的相干叠加。如果我们只是”把 $y$ 寄存器丢掉”，历史信息残留在环境里，干涉就被破坏；要让所有路径以正确相位合并，必须在每个频率上唯一确定地反解出产生它的 $y$，再用它把 $y$ 寄存器相干地清零。前提是正确处理不同 $y$ 映到同一 syndrome 的干涉——这个”前提”正是下一节电路第 4 步的全部内容，也正是”Decoded”一词的来历。

5. 五步 DQI 电路

现在给出完整电路。寄存器：一个 $m$ qubit 的 $y$ 寄存器（初态 $|0{⟩}^{\otimes m}$），一个 $n$ qubit 的 syndrome/输出寄存器（初态 $|0{⟩}^{\otimes n}$）。

第 1 步：制备 weighted Dicke superposition。 定义 Dicke 态

$$|D_{m,k}⟩={\left(\genfrac{}{}{0ex}{}{m}{k}\right)}^{-1/2}\sum _{|y|=k}|y⟩,$$

即所有 weight 恰好为 $k$ 的 $m$ 比特串的均匀叠加（$\left(\genfrac{}{}{0ex}{}{m}{k}\right)$ 项，归一化因子即由此而来）。制备

$$\sum _{k=0}^{\ell }{w}_k|D_{m,k}⟩=\sum _{|y|\le \ell }\frac{w_{|y|}}{\sqrt{\left(\genfrac{}{}{0ex}{}{m}{|y|}\right)}}|y⟩.$$

右边的等号只是把左边按 $y$ 逐个展开：每个 weight-$k$ 的 $y$ 得到振幅 $w_k/\sqrt{\left(\genfrac{}{}{0ex}{}{m}{k}\right)}$。Dicke 态及其加权叠加有已知的多项式规模制备电路，此处成本是 $\mathrm{poly}(m)$ 量级，不是瓶颈。

第 2 步：施加相位 $(-1{)}^{v\cdot y}$。 注意

$$(-1{)}^{v\cdot y}=\prod _{j=1}^m(-1{)}^{v_j{y}_j},$$

而对单比特，$(-1{)}^{v_j{y}_j}$ 就是”当 $v_j=1$ 时对第 $j$ 个 qubit 施加 $Z$”（$Z|y_j⟩=(-1{)}^{y_j}|y_j⟩$）。所以这一步只是对 $v$ 的支持集中的 qubit 各打一个 $Z$ 门，至多 $m$ 个单比特门，且全部对易、可并行。这是整个电路最便宜的一步，但它把约束右端 $v$ 的信息写进了每条历史的相位——优化目标的方向性（区分满足与违反）全部来自这里。

第 3 步：可逆计算 syndrome $s=B^{T}y$。 引入第二个寄存器并做

$$|y⟩|0{⟩}^{\otimes n}⟼|y⟩|B^{T}y⟩.$$

$s$ 的第 $i$ 个比特是 $(B^{T}y{)}_i={⨁}_{j:B_{ji}=1}{y}_j$，即若干 $y$ 比特的 XOR。XOR 的可逆实现就是 CNOT：对每个 $(i,j)$ 满足 $B_{ji}=1$，做一次以 $y_j$ 为控制、$s_i$ 为目标的 CNOT。总门数至多是 $B$ 的非零元个数，即 $O(mn)$（稀疏情形更少）。这一步之后，态是

$$\sum _{|y|\le \ell }\frac{w_{|y|}}{\sqrt{\left(\genfrac{}{}{0ex}{}{m}{|y|}\right)}}(-1{)}^{v\cdot y}|y⟩|B^{T}y⟩.$$

第 4 步（核心）：用 syndrome 反解 $y$ 并相干清零。 考虑线性码

$$C^{\perp }=\{d\in {\mathbb{F}}_2^m:B^{T}d=0\},$$

即以 $B^T$ 为校验矩阵的码。在编码理论的语言里，$B^{T}y$ 正是 $y$ 的 syndrome；从 syndrome 找 weight $\le \ell$ 的 error 正是经典的 syndrome decoding 问题。设我们有一个经典高效解码器，能在”真实 error 重量不超过 $\ell$“的承诺下唯一地输出 $D(s)=y$。把它可逆化（任何多项式时间经典算法都有多项式开销的可逆实现），作用为

$$|y⟩|s⟩⟼|y\oplus D(s)⟩|s⟩=|0{⟩}^{\otimes m}|s⟩,$$

其中第二个等号用了 $D(s)=y$（承诺成立时）与 $y\oplus y=0$。这一步之后 $y$ 寄存器干净地回到 $|0⟩$，不再与输出寄存器纠缠，所有产生同一 $s$ 的历史已经以各自的相位 $(-1{)}^{v\cdot y}$ 相干地合并进 $|s⟩$ 的振幅：

$$|0{⟩}^{\otimes m}\otimes \sum _{k=0}^{\ell }\frac{w_k}{\sqrt{\left(\genfrac{}{}{0ex}{}{m}{k}\right)}}\sum _{|y|=k}(-1{)}^{v\cdot y}|B^{T}y⟩.$$

若 decoder 唯一/相干地恢复实际 $y$，所有 Fourier 路径以正确相位合并。反过来说，如果某个 syndrome $s$ 对应多条 weight $\le \ell$ 的历史（唯一解码失败），这一步就无法把它们区分清零，$y$ 寄存器残留纠缠，后面的干涉就会出现误差——解码器的唯一解码半径因此成为整个算法的硬约束。

第 5 步：对 $s$ 寄存器做 $H^{\otimes n}$，测量输出 $x$。 由 2.3 节的 Hadamard 公式，

$$H^{\otimes n}|B^{T}y⟩=\frac{1}{\sqrt{2^n}}\sum _x(-1{)}^{(B^{T}y)\cdot x}|x⟩.$$

化简相位：$(B^{T}y)\cdot x=y\cdot (Bx)$，这由定义直接验证——

$$(B^{T}y)\cdot x=\sum _{i=1}^n\left(\sum _{j=1}^m{B}_{ji}{y}_j\right)x_i=\sum _{j=1}^m{y}_j\left(\sum _{i=1}^n{B}_{ji}{x}_i\right)=y\cdot (Bx),$$

即转置的伴随恒等式。于是输出态（丢弃已清零的 $y$ 寄存器，略去整体归一化）为

$$\sum _{x}A(x)|x⟩,A(x)=\sum _{k=0}^{\ell }\frac{w_k}{\sqrt{\left(\genfrac{}{}{0ex}{}{m}{k}\right)}}\sum _{|y|=k}(-1{)}^{v\cdot y+y\cdot (Bx)}.$$

5.1 振幅逐点恒等式：电路确实制备了 $P(f)$

我们来证明 $A(x)$ 正是 $f(x)$ 的一个 degree-$\ell$ 多项式，这是”DQI 制备 $|P(f)⟩$“的严格含义。固定 $x$，记 $u\in {\mathbb{F}}_2^m$，$u_j=v_j+(Bx{)}_j$，则内层求和只与 $u$ 的 Hamming weight 有关：

$$\sum _{|y|=k}(-1{)}^{u\cdot y}=\sum _{|y|=k}\prod _j(-1{)}^{u_j{y}_j}=\sum _{j=0}^k(-1{)}^j(\genfrac{}{}{0ex}{}{|u|}{j}\left)\right(\genfrac{}{}{0ex}{}{m-|u|}{k-j})=:K_k(|u|).$$

第二个等号是组合计数：从 $u$ 的 $|u|$ 个非零位置中选 $j$ 个、从其余 $m-|u|$ 个位置中选 $k-j$ 个组成 $y$，该项贡献 $(-1{)}^j$，对所有这样的 $y$ 求和即得。$K_k$ 就是 Krawtchouk 多项式，它是变量 $|u|$ 的 degree-$k$ 多项式。

而 $|u|$ 有直接的组合意义：$u_j=1$ 当且仅当 $v_j\ne (Bx{)}_j=b_j\cdot x$，即第 $j$ 个约束被违反。所以 $|u|=m-s(x)$ 是违反数，由 2.1 节 $s(x)=(m+f(x))/2$ 得

$$|u|=m-\frac{m+f(x)}{2}=\frac{m-f(x)}{2}.$$

代回 $A(x)$：

$$A(x)=\sum _{k=0}^{\ell }\frac{w_k}{\sqrt{\left(\genfrac{}{}{0ex}{}{m}{k}\right)}}{K}_k\left(\frac{m-f(x)}{2}\right)=:P(f(x)).$$

$K_k$ 是 $|u|$ 的 degree-$k$ 多项式，$|u|$ 是 $f$ 的一次函数，所以 $P$ 是 $f$ 的 degree-$\ell$ 多项式，其系数由 $w_0,\dots ,w_{\ell }$ 完全决定；反过来，给定目标多项式 $P$，可以解出对应的 $w_k$。这就完成了第 4 节开头的承诺：制备 $|P(f)⟩$ 的全部成本，是一个能纠正 weight $\le \ell$ 错误的高效 syndrome decoder。

sanity check：取 $\ell =1$、$w_0=0$、$w_1=1$。直接算 $K_1(t)=\left(\genfrac{}{}{0ex}{}{t}{0}\right)\left(\genfrac{}{}{0ex}{}{m-t}{1}\right)-\left(\genfrac{}{}{0ex}{}{t}{1}\right)\left(\genfrac{}{}{0ex}{}{m-t}{0}\right)=(m-t)-t=m-2t$，代入 $t=(m-f)/2$ 得 $K_1=f$，于是 $A(x)=f(x)/\sqrt{m}$——电路退化为 2.3 节那个”按 $f$ 偏置”的朴素态，与直接展开一致。用第 3 节的例子再验证一次：$m=3$，振幅应正比于 $f=(1,1,1,-3)$，测量概率 $(1,1,1,9)/12$，与 2.4 节逐点算出的分布相同。恒等式在数值上闭合。

5.2 复杂度账目

逐项列出一次制备的成本，可以看出每个因子来自哪里：

• 第 1 步 Dicke 叠加制备：$\mathrm{poly}(m)$ 门（$y$ 寄存器只有 $m$ 个 qubit，与 $2^n$ 无关）；
• 第 2 步相位：至多 $m$ 个单比特门；
• 第 3 步 syndrome：至多 $mn$ 个 CNOT（$B$ 的每个非零元一个；稀疏实例更少）；
• 第 4 步 decoder：经典解码算法运行时间的多项式倍（可逆化开销），这是总成本的主导项，也是”DQI 是否高效”的全部赌注；
• 第 5 步：$n$ 个 Hadamard。

所以只要 decoder 是多项式时间的，整个制备就是多项式时间的；目标 degree $\ell$ 的选择是一场交易——$\ell$ 越大滤波越陡、近似比越好，但 decoder 必须能在更大的错误重量下唯一解码。参数平衡在 $\tau =\ell /m$（解码半径比例）处结算：把 $\ell$ 顶到对偶码唯一解码能力的上限。下一节给出这场交易的显式公式。

6. Decoder radius 到 approximation ratio

6.1 max-LINSAT 设置

把 max-XORSAT 推广到一般的 max-LINSAT over ${\mathbb{F}}_p$：变量 $x\in {\mathbb{F}}_p^n$，每个约束是对 $x$ 的某个线性组合限制在一个允许集合内，每约束允许集合大小为 $r$。XORSAT 是 $p=2$、$r=1$ 的特例。随机赋值命中单个约束允许集合的概率是

$$q_0=\frac{r}{p},$$

所以 $q_0$ 是随机赋值基线的期望满足比例（XORSAT 中 $q_0=1/2$）。

6.2 半圆公式

设对偶码的 decoder 可纠正 fraction

$$\tau =\frac{\ell }{m}$$

的 errors（即 degree-$\ell$ 滤波所需的唯一解码半径为 $\ell =\tau m$）。DQI 论文证明：在此半径内，取最优 polynomial filter，测量分布下的期望满足比例为 semicircle-type 公式

$$\frac{\mathbb{E}[s]}{m}={\left(\sqrt{\tau (1-q_0)}+\sqrt{q_0(1-\tau )}\right)}^2$$

（在相应参数区间成立；超过阈值时可饱和为 1）。编码定理（“这个码能在多大半径内唯一解码”）因此直接变成优化 approximation guarantee——不需要任何额外的量子分析。

逐项理解这个公式：

• $\tau =0$ 时 $\mathbb{E}[s]/m=q_0$，退化为随机基线：degree-$0$ 的 $P$ 是常数，$|P(f)⟩$ 是均匀叠加，测量就是随机赋值，一致性检查通过；
• 公式关于 $\tau$ 的增量来自滤波能力：$\tau$ 越大，$P$ 的 degree 越高，偏置越强；
• 上界饱和：把两个根号看成向量点积，$(\sqrt{\tau },\sqrt{1-\tau })\cdot (\sqrt{1-q_0},\sqrt{q_0})$，由 Cauchy—Schwarz 不等式

$${\left(\sqrt{\tau (1-q_0)}+\sqrt{q_0(1-\tau )}\right)}^2\le (\tau +(1-\tau ))((1-q_0)+q_0)=1,$$

等号当且仅当 $(\sqrt{\tau },\sqrt{1-\tau })$ 与 $(\sqrt{1-q_0},\sqrt{q_0})$ 平行，即 $\tau =1-q_0$。所以期望满足比例恒不超过 $1$（废话上界被公式自动尊重），且当解码半径达到 $\tau =1-q_0$ 时饱和为 1——解码能力强到一定程度，滤波器可以把全部概率质量压到最优赋值上。这就是”超过阈值时可饱和为 1”的来源。

对最重要的特例 XORSAT（$q_0=1/2$）化简：

$$\frac{\mathbb{E}[s]}{m}={\left(\sqrt{\frac{\tau }{2}}+\sqrt{\frac{1-\tau }{2}}\right)}^2=\frac{\tau +(1-\tau )+2\sqrt{\tau (1-\tau )}}{2}=\frac{1}{2}+\sqrt{\tau (1-\tau )},$$

其中第一个等号展开平方、第二个等号通分。它在 $\tau =1/2$ 处达到最大值 $1$，与上面的 Cauchy—Schwarz 分析（$1-q_0=1/2$）一致。

6.3 一个常见的误解

必须强调：这不是”decoder 输出优化解”。decoder 在整个过程中只处理 syndrome，它恢复的是 Fourier 历史 $y$（哪几行约束组合出这个频率），与优化变量 $x$ 没有直接关系；它的唯一用途是相干 uncompute Fourier history，让干涉干净发生。最终的优化解来自对干涉态 $|P(f)⟩$ 的测量。把 DQI 理解成”用量子加速经典解码来解优化”是错的——解码是手段，干涉才是输出。

7. OPI 与 Reed—Solomon：旗舰例子

7.1 Optimal Polynomial Intersection 问题

DQI 论文主推的应用是 Optimal Polynomial Intersection（OPI）：对每个 $y\in {\mathbb{F}}_p^{\ast }$ 给一个允许值集 $F_y\subseteq {\mathbb{F}}_p$，找 degree $<n$ 多项式 $Q$，最大化

$$|\{y:Q(y)\in F_y\}|,$$

即让 $Q$ 在尽可能多的点上”落入允许集”。可以把它想成”带逐点松散约束的多项式拟合”：$F_y=\{\text{单点}\}$ 时就是多项式插值/重建的近亲。

7.2 为什么 OPI 是 max-LINSAT

把 $Q$ 的系数作为变量：$Q(X)={\sum }_{i=0}^{n-1}{q}_i{X}^i$，未知数是 $q=(q_0,\dots ,q_{n-1})\in {\mathbb{F}}_p^n$。在每个点 $y$ 处，约束 $Q(y)\in F_y$ 即

$$\sum _{i=0}^{n-1}{y}^i{q}_i\in F_y,$$

左边对未知数 $q$ 是线性的。所以 OPI 是一个 max-LINSAT：约束矩阵是 Vandermonde evaluation matrix

$$B_{y,i}=y^i,y\in {\mathbb{F}}_p^{\ast },0\le i<n,$$

共 $m=p-1$ 个约束、$n$ 个变量；每约束允许集大小 $r=|F_y|$，基线 $q_0=r/p$。

7.3 对偶码是 Reed—Solomon，解码器现成

syndrome 由 $B^T$ 给出，对偶码 $C^{\perp }=\{d\in {\mathbb{F}}_p^{p-1}:{\sum }_y{d}_y{y}^i=0\forall i<n\}$ 正是（广义）Reed—Solomon 码——有限域上研究最充分的码族之一。关键事实是：Berlekamp—Massey 算法可以 polynomial-time unique decode 到半距离（minimum distance $d$ 的码唯一解码半径为 $\lfloor (d-1)/2\rfloor$：若两个重量 $\le \ell$ 的 error 有相同 syndrome，它们的差是属于码的重量 $\le 2\ell$ 的非零码字，与最小距离矛盾）。对 OPI 的 RS 参数，这给出可用的滤波 degree

$$\ell =\lfloor \frac{n+1}{2}\rfloor .$$

代入 $\tau =\ell /m$（$m=p-1$）与 6.2 节的半圆公式，即得 DQI 在 OPI 上的期望满足比例。由于 RS/Berlekamp—Massey 是教科书级的成熟算法，第 4 步的可逆实现是彻底的”工程问题”而非”研究问题”，并得到强 approximation bias。

7.4 优势声明的准确表述

该性能超过论文分析的已知经典 polynomial-time 方法，但目标参数区间尚无 standard assumption 下的 classical hardness theorem；因此应称相对已知算法的 apparent/superpolynomial speedup，不是已证明复杂度分离。“已知方法做不到”与”任何经典方法做不到”之间的区别在这里不是修辞——下节的 MaxCut 结果说明这个差距可能真的被后来的经典工作填上。资源方面，具体估计可达 $10^8$ logical Toffolis 与数千逻辑 qubits：渐近高效不等于近期低成本，OPI 的 DQI 实现是容错量子计算机时代的算法。

8. Sparse clauses 与 LDPC：另一类解码器

若每约束只含少量变量（sparse clauses），$B$ sparse，则 $C^{\perp }$ 是 LDPC code（low-density parity-check：校验矩阵每行每列只有常数个非零元）。LDPC 码的标准解码器不是 Berlekamp—Massey 而是 belief propagation（BP） 等迭代消息传递算法，它们可处理线性比例（$\tau =\Omega (1)$）的随机 errors。把 BP 可逆实现后嵌入第 4 步，就得到高-degree 的 DQI——线性比例的 $\tau$ 意味着 $\ell =\Theta (m)$ 的滤波，这是最强的渐近区间。

但稀疏情形的 benchmark 故事给上了词条，必须如实陈述：

• 原工作构造了某些 max-XORSAT family，使 DQI+BP 在同等 decoder-step 比较中胜过 general-purpose annealing（通用退火启发式）；
• 然而 tailored classical heuristic（针对该实例族专门设计的经典启发式）后来在这些实例上略胜 DQI；
• 论文明确不把该 family 宣称为 superpolynomial quantum advantage。

2025 年的 MaxCut limitation 结果更强：在 DQI 能证明非平凡 asymptotic guarantee 的 MaxCut 实例上，存在 classical polynomial-time exact algorithm。也就是说，使 Fourier/decoder 结构高效运转的同一结构，也可能恰恰暴露了实例的经典可解性——_decoder 能跑多强_与_问题本身有多难_之间存在微妙的耦合，这是评估一切 DQI 优势声明时必须检查的环节。

9. Quantum/soft decoders 与扩展

经典唯一解码器的半径受半距离限制，两条路线可以放宽它：

• Soft decoder：输出 error 的 distribution/amplitudes 而非唯一 error。在第 4 步，这对应把 $|s⟩$ 映射到若干候选 $y$ 的相干叠加再清零——可覆盖唯一解码失败但”少数候选集中大部分概率”的 syndrome，从而扩大可用半径。代价是清零不再精确，需要把残留纠缠计入最终误差。
• Quantum decoding：用量子算法解 decoding 问题本身。quantum decoding measurements 与 Regev lattice duality 的新 tight bounds 改善了 DQI 的 parameter regime（参见 Zoo 548—551 一组文献）。

其他方向的扩展包括：

• quadratic constraints 的更高阶 Fourier labels（频率标签从行的和变成更复杂的代数对象）；
• algebraic-geometry codes（比 RS 更长的渐近好码）；
• Hamiltonian DQI，把同样的机制用于准备 Gibbs/low-energy states 而非优化测量分布；
• planted inference 与 random-oracle separations 的近亲结构（DQI 机制与这些问题的结构联系，参见 Zoo 5、78、454—455）。

但有两条红线不变：decoder 本身若 NP-hard 或需要 postselection，DQI 不再高效——第 4 步必须在最坏意义（或压倒性比例的 syndrome）上多项式时间完成；Hamiltonian/quantum decoder 还要把 state preparation、成功概率与 uncomputation 全部计入成本，不能只报解码一步的复杂度。

（编辑注：Zoo 源码该段有编号/anchor 错位：CT23、BCT25、GJ25 实际 bibliography 是 548、549、547，而显示编号曾对应 448、449/坏链接；本词条按论文标题与 arXiv 链接校正。）

10. 小结与习题

小结。

• 稀疏约束使 objective 的 Fourier 支持由少量行向量生成：max-XORSAT 的 $f$ 只有 $m$ 个非零频率 $b_i$。
• Degree-$\ell$ filter 对应 weight-$\le \ell$ 的 Fourier histories $y$，振幅由 Krawtchouk 系数 $w_k$ 控制，且电路振幅逐点等于 $P(f(x))$。
• Syndrome decoder 相干恢复 history 以完成干涉；解码半径决定 approximation ratio，半圆公式把 $\tau =\ell /m$ 直接映射为期望满足比例。
• OPI/Reed—Solomon 是旗舰例子：有强相对已知经典算法的表现，但无匹配 hardness，只能称 apparent speedup；MaxCut 的已知限制必须保留在记忆里——decoder 结构可能同时暴露经典可解性。

习题。

1. （概念）推导 max-XORSAT objective 与满足数的关系 $s(x)=(m+f(x))/2$，并说明为什么最大化 $f$ 等价于最大化满足数。
2. （计算）用第 3 节的 3 约束例子，验证 Fourier 正交归一关系 $2^{-n}{\sum }_x{\chi }_b(x){\chi }_{b^{\prime }}(x)={\delta }_{b,b^{\prime }}$ 在 $b=(1,0)$、$b^{\prime }=(1,1)$ 上成立；再用 Parseval 验证 ${\sum }_{x}f(x{)}^2=2^n\cdot 3$。
3. （推导）展开 $f(x{)}^2$，验证其 Fourier 频率形如 $B^{T}y$、$|y|=2$（加上 $|y|=0$ 的常数项），相位为 $(-1{)}^{v\cdot y}$。指出同一频率最多可由几对不同的 $\{i,j\}$ 产生，由此说明”历史合并”为什么已经非平凡。
4. （概念）解释为什么 syndrome 相同的不同 $y$ 会阻碍直接 uncompute：如果在第 4 步只对 $y$ 寄存器做测量（而非相干清零），第 5 步之后的测量分布会发生什么变化？
5. （推导）设 $C^{\perp }$ 的 minimum distance 为 $d$。证明：若 $\ell <d/2$，则任意 syndrome 至多对应一个 weight $\le \ell$ 的 $y$（唯一解码的半距离条件），并说明这正是 Berlekamp—Massey 能保证的半径量级。
6. （计算）在 $q_0=1/2$ 时把 semicircle formula 化简为 $\frac{1}{2}+\sqrt{\tau (1-\tau )}$，求其取最大值 $1$ 的 $\tau$，并用 Cauchy—Schwarz 解释为什么这个 $\tau$ 恰好是 $1-q_0$。

参考文献与 Zoo 覆盖

• Zoo 453：Jordan 等, Optimization by Decoded Quantum Interferometry.
• Zoo 534、544—547：soft decoders、quadratic constraints、MaxCut limitation、Hamiltonian DQI 与 algebraic-geometry codes。
• Zoo 548—551：quantum decoding problem、tight measurements 与 Regev-style reductions（Zoo 页面显示编号有错位）。
• Zoo 5、78、454—455：Aharonov—Ta-Shma/Regev duality、planted inference 与 verifiable random-oracle advantage。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch14-optimization-numerics/decoded-quantum-interferometry
• 内容遵循 CC BY-NC-SA 4.0 许可协议