# Decoded Quantum Interferometry：Fourier 稀疏目标与经典码解码 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 变换](../ch03-algo-basics/quantum-fourier-transform.md) 与 [振幅放大](../ch03-algo-basics/amplitude-amplification.md)），以及多项式方法制备对角函数态的思想（参见 [QSP 教程](../ch05-hamiltonian-qsp/qsp-tutorial.md)，但本文不需要 QSP 本身）。 :::{admonition} 本课知识点 :class: tip 1. **[max-XORSAT 的目标函数](#xorsat-objective)**——能写出目标函数 $f(x)=\sum_{i=1}^m(-1)^{v_i+b_i\cdot x}$，推导满足数关系 $s(x)=\frac{m+f(x)}{2}$，并说明最大化 $f$ 等价于最大化满足数。 2. **[Boolean Fourier 稀疏性](#fourier-sparsity)**——能证明字符 $\chi_b$ 的正交归一性，读出 $f$ 的全部非零 Fourier 系数 $\hat f(b_i)=(-1)^{v_i}$，并用 Hadamard 变换写出从 $\sum_i(-1)^{v_i}|b_i\rangle$ 到 $\sum_x f(x)|x\rangle$ 的制备关系。 3. **[符号盲与手算例子](#worked-example-decoded-quantum-interferometry)**——能对具体实例逐点计算 $f(x)$ 与按 $f^2$ 偏置的测量分布，解释符号盲与放大有限两个缺陷，并验证线性滤波 $P(f)=\frac{m+f}{2}$ 对符号问题的修正。 4. **[多项式滤波与 Fourier 历史](#poly-filter-state)**——能写出 DQI 目标态 $|P(f)\rangle$，把 $f^k$ 的 Fourier 展开整理成按 $|y|=k$ 分层、频率为 $B^Ty$、相位为 $(-1)^{v\cdot y}$ 的形式，并解释不同历史产生同一 syndrome 为何是核心难点。 5. **[五步 DQI 电路](#five-step-circuit)**——能按序描述五步电路每一步的操作与门成本，说明第 4 步可逆解码器如何把 $y$ 寄存器相干清零、让 Fourier 路径以正确相位合并。 6. **[振幅恒等式与 Krawtchouk 多项式](#krawtchouk-identity)**——能推导 Krawtchouk 求和 $\sum_{|y|=k}(-1)^{u\cdot y}=K_k(|u|)$ 与违反数 $|u|=\frac{m-f(x)}{2}$，证明电路输出振幅逐点等于 $P(f(x))$。 7. **[解码半径与半圆公式](#semicircle-formula)**——能写出随机基线 $q_0=\frac rp$ 与半圆公式，用 Cauchy--Schwarz 说明期望满足比例在 $\tau=1-q_0$ 处饱和为 $1$，并纠正"decoder 输出优化解"的误解。 8. **[OPI、Reed--Solomon 与优势边界](#opi-reed-solomon)**——能把 OPI 写成约束矩阵为 Vandermonde 矩阵的 max-LINSAT，说明其对偶码是 Reed--Solomon 码、Berlekamp--Massey 给出 $\ell=\lfloor\frac{n+1}{2}\rfloor$，并准确复述 apparent speedup 与 MaxCut 限制。 ::: ## 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 稀疏"这件事彻底算清楚。 (xorsat-objective)= ### 2.1 问题与目标函数 给定 $$ B\in\mathbb F_2^{m\times n},\qquad v\in\mathbb F_2^m. $$ $B$ 的第 $i$ 行记为 $b_i\in\mathbb F_2^n$，第 $i$ 个约束是线性方程 $$ b_i\cdot x=v_i\pmod 2, $$ 其中 $b_i\cdot x=\sum_{j=1}^n b_{ij}x_j\pmod 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\pmod 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$ 个函数在归一化内积 $\langle g,h\rangle=2^{-n}\sum_x g(x)h(x)$ 下正交归一： $$ 2^{-n}\sum_{x}\chi_b(x)\chi_{b'}(x)=\delta_{b,b'}. $$ 证明：左边等于 $2^{-n}\sum_x(-1)^{(b+b')\cdot x}$。若 $b=b'$，每项都是 $1$，和为 $2^n$；若 $b\neq b'$，取某个坐标 $j$ 使 $b_j\neq b'_j$，把 $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$。 (fourier-sparsity)= ### 2.3 $f$ 只有 $m$ 个非零频率 把 $f$ 的定义式直接读成 Fourier 展开： $$ f(x)=\sum_{i=1}^m(-1)^{v_i}\chi_{b_i}(x), \qquad\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\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\mathbb F_2^n}(-1)^{b\cdot x}|x\rangle =\frac{1}{\sqrt{2^n}}\sum_x\chi_b(x)|x\rangle, $$ 这只是 $H|0\rangle=(|0\rangle+|1\rangle)/\sqrt2$、$H|1\rangle=(|0\rangle-|1\rangle)/\sqrt2$ 逐比特展开的合并写法。因此 $$ H^{\otimes n}\left(\sum_{i=1}^m(-1)^{v_i}|b_i\rangle\right) =\frac{1}{\sqrt{2^n}}\sum_x\left(\sum_i(-1)^{v_i}\chi_{b_i}(x)\right)|x\rangle =\frac{1}{\sqrt{2^n}}\sum_x f(x)|x\rangle. $$ 左边括号里是一个只含 $m$ 个计算基矢的叠加态，原则上可以用 $\operatorname{poly}(m,n)$ 个门制备（第 5 节给出系统构造）。所以 $\sum_xf(x)|x\rangle$ 可从 $\sum_i(-1)^{v_i}|b_i\rangle$ 做 Hadamard 得到。 ### 2.4 为什么这还不够 把上式归一化。由 Parseval，$\sum_x f(x)^2=2^n\sum_b\hat f(b)^2=2^n m$（各 $b_i$ 不同时；一般有相同的 $\binom{m}{2}$ 级修正，结论不变），所以测量 $x$ 的概率为 $$ p(x)=\frac{f(x)^2}{2^n m}. $$ 这确实把概率质量推向了 $|f|$ 大的赋值，但有两个缺陷： - **符号盲**：$f(x)^2$ 对正负对称，$f$ 很负的坏赋值（违反极多约束）与 $f$ 很正的好赋值得到同样的放大。第 3 节的数值例子会看到这个缺陷真实发生。 - **放大倍数有限**：$|f|\le m$，所以单个赋值的概率至多是均匀分布的 $m$ 倍；当 $m=\operatorname{poly}(n)$ 时，相对随机基线的期望改进是多项式因子级别的，不足以改变近似比的量级。 所以测量概率仅按 $f(x)^2$ 偏置，优化力度有限。要得到真正强的优化偏置，需要把 $f$ 换成一个在大 $f$ 处增长更快的函数——这就引出多项式滤波。 (worked-example-decoded-quantum-interferometry)= ## 3. 一个可手算的小例子 在进入一般理论前，用一个最小例子把上面的每个对象都算一遍。取 $n=2$、$m=3$： $$ b_1=(1,0),\ v_1=0;\qquad b_2=(0,1),\ v_2=0;\qquad 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}{c|ccc|c|c} x & (-1)^{x_1} & (-1)^{x_2} & (-1)^{1+x_1+x_2} & f(x) & s(x)\\\hline 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. 用多项式放大高目标值 (poly-filter-state)= ### 4.1 DQI 目标态 DQI 的目标态是把"按 $f$ 滤波"推到极致的振幅态 $$ |P(f)\rangle \propto\sum_xP(f(x))|x\rangle, $$ 其中 $P$ 为 degree-$\ell$ polynomial，$\ell$ 是一个可选择的参数。第 5 节将证明：系数取适当的正交多项式/Krawtchouk 系数 $w_0,\ldots,w_\ell$ 时，这个态恰好可以用一条高效电路制备；而 $P$ 的形状可以在制备前离线优化，使测量分布下的期望 objective 最大。直觉上，degree 越高，$P$ 越能逼近"只在大 $f$ 处非零"的陡峭函数，$P(f)^2$ 越集中在大 $f$ 区域——代价是电路里需要更强的解码器。 为什么自然出现 Krawtchouk 多项式？当 $x$ 均匀随机时，每个 $(-1)^{b_i\cdot x}$ 是独立的 $\pm1$ 随机变量（对一般位置的 $b_i$），$f(x)$ 近似是 $m$ 步随机游走，其分布是二项分布；以二项分布为权重的正交多项式系正是 Krawtchouk 多项式。DQI 论文在这一框架下最大化期望 objective，得到最优的 $w_0,\ldots,w_\ell$。我们不需要重现这个优化，只需要记住结论：**给定允许的 degree $\ell$，存在可计算的最优滤波器；$\ell$ 越大，偏置越强**。 ### 4.2 $f^k$ 的 Fourier 频率从哪里来 关键问题是：$P(f)$ 作为 $f$ 的多项式，它的 Fourier 谱长什么样？只要把 $f^k$ 展开即可。由 $f$ 的定义， $$ f(x)^k=\sum_{i_1,\ldots,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'}(x)=(-1)^{(b+b')\cdot x}=\chi_{b+b'}(x)$（加法在 $\mathbb F_2^n$ 中）。所以上面每一项的频率是 $k$ 个行向量之和 $b_{i_1}+\cdots+b_{i_k}$，相位是 $(-1)^{v_{i_1}+\cdots+v_{i_k}}$。 把 $\binom{m}{k}$ 个有序 $k$ 元组按"哪些行被选中了奇数次"分组。用 indicator 向量 $$ y\in\mathbb F_2^m,\qquad y_j=(\text{行 }j\text{ 被选中的次数})\bmod 2, $$ 则该组的频率与相位可以紧凑地写成 $$ \sum_{j}y_jb_j=B^Ty, \qquad (-1)^{\sum_j y_jv_j}=(-1)^{v\cdot y}. $$ 第一个等号就是矩阵转置乘向量的定义：$B^T\in\mathbb F_2^{n\times m}$，$(B^Ty)_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)\rangle$ 的 Fourier transform（即 Hadamard 之前的形态）形如 $$ \sum_{k=0}^{\ell} \frac{w_k}{\sqrt{\binom mk}} \sum_{|y|=k} (-1)^{v\cdot y}|B^Ty\rangle, $$ 其中 $w_k$ 就是 $P$ 的 Krawtchouk 展开系数，$\binom{m}{k}^{-1/2}$ 是把每个 weight 层归一化的因子（weight-$k$ 的 $y$ 共 $\binom{m}{k}$ 个）。这个态的物理图像是：$y$ 是一条"**Fourier 历史**"，记录频率 $B^Ty$ 是由哪些约束行组合出来的；$(-1)^{v\cdot y}$ 是这条历史携带的相位。 这里藏着整个算法唯一的难点：**不同的历史可能产生同一个频率**。若 $y\neq y'$ 但 $B^Ty=B^Ty'$，那么上式中 $|B^Ty\rangle$ 这一项的振幅是两条（甚至更多条）历史的相干叠加。如果我们只是"把 $y$ 寄存器丢掉"，历史信息残留在环境里，干涉就被破坏；要让所有路径以正确相位合并，必须在每个频率上**唯一确定地反解出产生它的 $y$**，再用它把 $y$ 寄存器相干地清零。前提是正确处理不同 $y$ 映到同一 syndrome 的干涉——这个"前提"正是下一节电路第 4 步的全部内容，也正是"Decoded"一词的来历。 (five-step-circuit)= ## 5. 五步 DQI 电路 现在给出完整电路。寄存器：一个 $m$ qubit 的 $y$ 寄存器（初态 $|0\rangle^{\otimes m}$），一个 $n$ qubit 的 syndrome/输出寄存器（初态 $|0\rangle^{\otimes n}$）。 **第 1 步：制备 weighted Dicke superposition。** 定义 Dicke 态 $$ |D_{m,k}\rangle=\binom mk^{-1/2}\sum_{|y|=k}|y\rangle, $$ 即所有 weight 恰好为 $k$ 的 $m$ 比特串的均匀叠加（$\binom{m}{k}$ 项，归一化因子即由此而来）。制备 $$ \sum_{k=0}^{\ell}w_k|D_{m,k}\rangle =\sum_{|y|\le\ell}\frac{w_{|y|}}{\sqrt{\binom{m}{|y|}}}\,|y\rangle. $$ 右边的等号只是把左边按 $y$ 逐个展开：每个 weight-$k$ 的 $y$ 得到振幅 $w_k/\sqrt{\binom{m}{k}}$。Dicke 态及其加权叠加有已知的多项式规模制备电路，此处成本是 $\operatorname{poly}(m)$ 量级，不是瓶颈。 **第 2 步：施加相位 $(-1)^{v\cdot y}$。** 注意 $$ (-1)^{v\cdot y}=\prod_{j=1}^m(-1)^{v_jy_j}, $$ 而对单比特，$(-1)^{v_jy_j}$ 就是"当 $v_j=1$ 时对第 $j$ 个 qubit 施加 $Z$"（$Z|y_j\rangle=(-1)^{y_j}|y_j\rangle$）。所以这一步只是对 $v$ 的支持集中的 qubit 各打一个 $Z$ 门，至多 $m$ 个单比特门，且全部对易、可并行。这是整个电路最便宜的一步，但它把约束右端 $v$ 的信息写进了每条历史的相位——优化目标的方向性（区分满足与违反）全部来自这里。 **第 3 步：可逆计算 syndrome $s=B^Ty$。** 引入第二个寄存器并做 $$ |y\rangle|0\rangle^{\otimes n}\longmapsto|y\rangle|B^Ty\rangle. $$ $s$ 的第 $i$ 个比特是 $(B^Ty)_i=\bigoplus_{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{\binom{m}{|y|}}}(-1)^{v\cdot y}\,|y\rangle\,|B^Ty\rangle. $$ **第 4 步（核心）：用 syndrome 反解 $y$ 并相干清零。** 考虑线性码 $$ C^\perp=\{d\in\mathbb F_2^m:B^Td=0\}, $$ 即以 $B^T$ 为校验矩阵的码。在编码理论的语言里，$B^Ty$ 正是 $y$ 的 **syndrome**；从 syndrome 找 weight $\le\ell$ 的 error 正是经典的 **syndrome decoding** 问题。设我们有一个经典高效解码器，能在"真实 error 重量不超过 $\ell$"的承诺下唯一地输出 $D(s)=y$。把它可逆化（任何多项式时间经典算法都有多项式开销的可逆实现），作用为 $$ |y\rangle|s\rangle\longmapsto|y\oplus D(s)\rangle|s\rangle=|0\rangle^{\otimes m}|s\rangle, $$ 其中第二个等号用了 $D(s)=y$（承诺成立时）与 $y\oplus y=0$。这一步之后 $y$ 寄存器干净地回到 $|0\rangle$，不再与输出寄存器纠缠，所有产生同一 $s$ 的历史已经以各自的相位 $(-1)^{v\cdot y}$ 相干地合并进 $|s\rangle$ 的振幅： $$ |0\rangle^{\otimes m}\otimes\sum_{k=0}^{\ell}\frac{w_k}{\sqrt{\binom mk}}\sum_{|y|=k}(-1)^{v\cdot y}|B^Ty\rangle. $$ 若 decoder 唯一/相干地恢复实际 $y$，所有 Fourier 路径以正确相位合并。反过来说，如果某个 syndrome $s$ 对应多条 weight $\le\ell$ 的历史（唯一解码失败），这一步就无法把它们区分清零，$y$ 寄存器残留纠缠，后面的干涉就会出现误差——解码器的**唯一解码半径**因此成为整个算法的硬约束。 **第 5 步：对 $s$ 寄存器做 $H^{\otimes n}$，测量输出 $x$。** 由 2.3 节的 Hadamard 公式， $$ H^{\otimes n}|B^Ty\rangle=\frac{1}{\sqrt{2^n}}\sum_x(-1)^{(B^Ty)\cdot x}|x\rangle. $$ 化简相位：$(B^Ty)\cdot x=y\cdot(Bx)$，这由定义直接验证—— $$ (B^Ty)\cdot x=\sum_{i=1}^n\Big(\sum_{j=1}^m B_{ji}y_j\Big)x_i =\sum_{j=1}^m y_j\Big(\sum_{i=1}^n B_{ji}x_i\Big)=y\cdot(Bx), $$ 即转置的伴随恒等式。于是输出态（丢弃已清零的 $y$ 寄存器，略去整体归一化）为 $$ \sum_x A(x)\,|x\rangle, \qquad A(x)=\sum_{k=0}^{\ell}\frac{w_k}{\sqrt{\binom mk}}\sum_{|y|=k}(-1)^{v\cdot y+y\cdot(Bx)}. $$ (krawtchouk-identity)= ### 5.1 振幅逐点恒等式：电路确实制备了 $P(f)$ 我们来证明 $A(x)$ 正是 $f(x)$ 的一个 degree-$\ell$ 多项式，这是"DQI 制备 $|P(f)\rangle$"的严格含义。固定 $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_jy_j} =\sum_{j=0}^{k}(-1)^j\binom{|u|}{j}\binom{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\neq(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{\binom mk}}\,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,\ldots,w_\ell$ 完全决定；反过来，给定目标多项式 $P$，可以解出对应的 $w_k$。这就完成了第 4 节开头的承诺：**制备 $|P(f)\rangle$ 的全部成本，是一个能纠正 weight $\le\ell$ 错误的高效 syndrome decoder**。 sanity check：取 $\ell=1$、$w_0=0$、$w_1=1$。直接算 $K_1(t)=\binom{t}{0}\binom{m-t}{1}-\binom{t}{1}\binom{m-t}{0}=(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 叠加制备：$\operatorname{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$）。 (semicircle-formula)= ### 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)\rangle$ 是均匀叠加，测量就是随机赋值，一致性检查通过； - 公式关于 $\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\big(\tau+(1-\tau)\big)\big((1-q_0)+q_0\big)=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{\tfrac{\tau}{2}}+\sqrt{\tfrac{1-\tau}{2}}\right)^2 =\frac{\tau+(1-\tau)+2\sqrt{\tau(1-\tau)}}{2} =\frac12+\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)\rangle$ 的测量。把 DQI 理解成"用量子加速经典解码来解优化"是错的——解码是手段，干涉才是输出。 (opi-reed-solomon)= ## 7. OPI 与 Reed--Solomon：旗舰例子 ### 7.1 Optimal Polynomial Intersection 问题 DQI 论文主推的应用是 **Optimal Polynomial Intersection（OPI）**：对每个 $y\in\mathbb F_p^*$ 给一个允许值集 $F_y\subseteq\mathbb F_p$，找 degree $ 提示：对每个约束项用配对论证 $2^{-n}\sum_x(-1)^{b_i\cdot x}=0$。 **练习 2【Boolean Fourier 稀疏性】**（→ [2.3 节](#fourier-sparsity)） 1. 用第 3 节的 3 约束例子，验证 Fourier 正交归一关系 $2^{-n}\sum_x\chi_b(x)\chi_{b'}(x)=\delta_{b,b'}$ 在 $b=(1,0)$、$b'=(1,1)$ 上成立；再用 Parseval 验证 $\sum_x f(x)^2=2^n\cdot 3$。 2. 对一般 $b\neq b'$ 证明正交归一关系，并由此说明 $f=\sum_i(-1)^{v_i}\chi_{b_i}$ 中各频率互不干扰、展开系数恰为 $\hat f(b_i)=(-1)^{v_i}$。 > 提示：取坐标 $j$ 使 $b_j\neq b'_j$，把每个 $x$ 与 $x+e_j$ 配对，两项相加为零。 **练习 3【符号盲与手算例子】**（→ [第 3 节](#worked-example-decoded-quantum-interferometry)） 1. 对第 3 节实例（$n=2$、$m=3$、$v_3=1$）逐点重算 $f(x)$ 与 $s(x)$，计算按 $f^2$ 偏置的测量分布并求 $p(11)$；再列出 2.4 节指出的两个缺陷，指出本例中哪一个真实发生。 2. 验证线性滤波 $P(f)=(m+f)/2$ 在该实例上给出振幅 $(2,2,2,0)$、测量分布 $(1/3,1/3,1/3,0)$，并解释为什么 $P(f(11))=P(-3)=0$ 恰好把最差赋值的概率精确清零。 > 提示：$P(f(x))=s(x)$，而该实例的满足数恰为 $(2,2,2,0)$。 **练习 4【多项式滤波与 Fourier 历史】**（→ [4.1 节](#poly-filter-state)） 1. 写出 DQI 目标态 $|P(f)\rangle\propto\sum_xP(f(x))|x\rangle$ 及其 Fourier 域形态 $\sum_{k=0}^{\ell}\frac{w_k}{\sqrt{\binom mk}}\sum_{|y|=k}(-1)^{v\cdot y}|B^Ty\rangle$，并说明 $y$（Fourier 历史）、$B^Ty$（频率标签）与 $(-1)^{v\cdot y}$（历史相位）各自的含义。 2. 展开 $f(x)^2$，验证其 Fourier 频率形如 $B^Ty$、$|y|=2$（加上 $|y|=0$ 的常数项），相位为 $(-1)^{v\cdot y}$。指出同一频率最多可由几对不同的 $\{i,j\}$ 产生，由此说明"历史合并"为什么已经非平凡。 > 提示：用 $\chi_b(x)\chi_{b'}(x)=\chi_{b+b'}(x)$，把交叉项按"哪些行被选中奇数次"分组。 **练习 5【五步 DQI 电路】**（→ [第 5 节](#five-step-circuit)） 1. 按顺序列出五步电路各步的操作与门成本量级（Dicke 制备、相位、syndrome、可逆解码、Hadamard），并指出哪一步是总成本的主导项。 2. 解释为什么 syndrome 相同的不同 $y$ 会阻碍直接 uncompute：如果在第 4 步只对 $y$ 寄存器做测量（而非相干清零），第 5 步之后的测量分布会发生什么变化？ > 提示：单条历史 $|B^Ty\rangle$ 经 $H^{\otimes n}$ 后给出均匀分布；测量把相干叠加换成按历史的概率混合。 **练习 6【振幅恒等式与 Krawtchouk 多项式】**（→ [5.1 节](#krawtchouk-identity)） 1. 解释 $u_j=v_j+(Bx)_j$ 为什么当且仅当第 $j$ 个约束被违反时取 $1$，从而 $|u|=m-s(x)=\frac{m-f(x)}{2}$ 是违反数。 2. 由定义 $K_k(t)=\sum_{j=0}^{k}(-1)^j\binom{t}{j}\binom{m-t}{k-j}$ 计算 $K_0(t)$ 与 $K_1(t)$，并验证正文 $\ell=1$、$w_0=0$、$w_1=1$ 的 sanity check：输出振幅 $A(x)=f(x)/\sqrt m$。 3. 推导 $K_2(t)$ 的闭式并代入 $t=\frac{m-f}{2}$，说明 degree-2 滤波的振幅正比于 $f^2-m$；用第 3 节实例（$m=3$）核对 $K_2$ 在 $f=1$ 与 $f=-3$ 处的取值。 > 提示：$K_2(t)=\binom{m-t}{2}-t(m-t)+\binom{t}{2}$，合并后用 $m-2t=f$。 **练习 7【解码半径与半圆公式】**（→ [6.2 节](#semicircle-formula)） 1. 写出 max-LINSAT 的随机基线 $q_0=r/p$ 与半圆公式，并验证 $\tau=0$ 时公式退化为 $q_0$。 2. 用一两句话说明 decoder 在 DQI 电路中的确切角色，并指出"decoder 的输出就是优化解"这一说法错在哪里。 3. 在 $q_0=1/2$ 时把 semicircle formula 化简为 $\frac12+\sqrt{\tau(1-\tau)}$，求其取最大值 $1$ 的 $\tau$，并用 Cauchy--Schwarz 解释为什么这个 $\tau$ 恰好是 $1-q_0$。 > 提示：把两个根号写成内积 $(\sqrt\tau,\sqrt{1-\tau})\cdot(\sqrt{1-q_0},\sqrt{q_0})$。 **练习 8【OPI、Reed--Solomon 与优势边界】**（→ [第 7 节](#opi-reed-solomon)） 1. 把 OPI 写成 max-LINSAT：以多项式系数为变量写出线性约束 $\sum_{i=0}^{n-1}y^iq_i\in F_y$ 与 Vandermonde 约束矩阵，并给出约束数 $m=p-1$、每约束允许集大小 $r=|F_y|$ 与随机基线满足比例。 2. 准确表述 DQI 在 OPI 上的优势声明（相对已知算法的 apparent speedup 而非已证明复杂度分离，以及 $10^8$ logical Toffolis 量级的资源估计），并复述 MaxCut 限制结果给出的教训。 3. 设 $C^\perp$ 的 minimum distance 为 $d$。证明：若 $\ell 提示：若两个 weight $\le\ell$ 的 error 有相同 syndrome，其差是属于码的重量 $\le 2\ell$ 的非零码字，与最小距离矛盾。 ## 参考文献与 Zoo 覆盖 - Zoo 453：Jordan 等, [Optimization by Decoded Quantum Interferometry](https://arxiv.org/abs/2408.08292). - 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。