# Decoded Quantum Interferometry：Fourier 稀疏目标与经典码解码 Decoded Quantum Interferometry（DQI）把“偏向高目标值的振幅态”在 Fourier 域展开；若目标由稀疏局部/线性约束组成，频率标签是少量约束向量的和。要清除产生同一频率的组合标签，恰好需要 syndrome decoder。解码半径越大，可实现的 polynomial filter degree 越高，对优解的测量偏置越强。 ## 1. Max-XORSAT 的 Fourier 稀疏性 给 $$ B\in\mathbb F_2^{m\times n},\qquad v\in\mathbb F_2^m. $$ 第 $i$ 个约束 $$ b_i\cdot x=v_i\pmod2. $$ 定义“满足数减违反数” $$ f(x)=\sum_{i=1}^m (-1)^{v_i+b_i\cdot x}. $$ 满足数为 $(m+f(x))/2$。Boolean Fourier transform 中，$f$ 只有 $m$ 个非零频率 $b_i$： $$ f(x)=\sum_i(-1)^{v_i}\chi_{b_i}(x), \qquad\chi_b(x)=(-1)^{b\cdot x}. $$ 所以 $\sum_xf(x)|x\rangle$ 可从 $\sum_i(-1)^{v_i}|b_i\rangle$ 做 Hadamard 得到，但测量概率仅按 $f(x)^2$ 偏置，优化力度有限。 ## 2. 用多项式放大高目标值 DQI 目标态 $$ |P(f)\rangle \propto\sum_xP(f(x))|x\rangle, $$ $P$ 为 degree-$\ell$ polynomial。适当正交多项式/Krawtchouk 系数 $w_0,\ldots,w_\ell$ 最大化期望 objective；degree 越高，$P(f)^2$ 越集中在大 $f$。 $f^k$ 的 Fourier 频率来自选择 $k$ 个约束行。用 indicator $$ y\in\mathbb F_2^m,\qquad|y|=k, $$ 频率与相位为 $$ B^Ty,\qquad(-1)^{v\cdot y}. $$ 因此 $|P(f)\rangle$ 的 Fourier transform 形如 $$ \sum_{k=0}^{\ell} \frac{w_k}{\sqrt{\binom mk}} \sum_{|y|=k} (-1)^{v\cdot y}|B^Ty\rangle, $$ 前提是正确处理不同 $y$ 映到同一 syndrome 的干涉。 ## 3. 五步 DQI 电路 1. 制备 weighted Dicke superposition $$ \sum_{k=0}^{\ell}w_k|D_{m,k}\rangle, \quad |D_{m,k}\rangle=\binom mk^{-1/2} \sum_{|y|=k}|y\rangle. $$ 2. 施加 phase $(-1)^{v\cdot y}$。 3. 可逆计算 syndrome $$ s=B^Ty. $$ 4. 用 $s$ 与 $|y|\le\ell$ 的承诺恢复 $y$，再 XOR 清零原 $y$ register。 5. 对 $s$ register 做 $H^{\otimes n}$，得到 $|P(f)\rangle$，测量输出 $x$。 第 4 步是核心。Code $$ C^\perp=\{d\in\mathbb F_2^m:B^Td=0\} $$ 的 syndrome 是 $B^Ty$；从 syndrome 找 weight $\le\ell$ 的 error 正是 syndrome decoding。若 decoder 唯一/相干地恢复实际 $y$，所有 Fourier 路径以正确相位合并。 ## 4. Decoder radius 到 approximation ratio 对一般 max-LINSAT over $\mathbb F_p$，每约束允许集合大小 $r$。若 decoder 可纠正 fraction $$ \tau=\ell/m $$ 的 errors，随机赋值基线 $q_0=r/p$。最优 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。 这不是“decoder 输出优化解”：decoder 只用来相干 uncompute Fourier history，最终优化解来自干涉态测量。 ## 5. OPI 与 Reed--Solomon Optimal Polynomial Intersection：给 $y\in\mathbb F_p^*$ 的允许值集 $F_y$，找 degree $