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 \(<n\) 多项式 \(Q\)，最大化

\[ |\{y:Q(y)\in F_y\}|. \]

把 \(Q\) 系数作为变量，Vandermonde evaluation matrix \(B\) 给 max-LINSAT；dual code 是 Reed--Solomon。Berlekamp--Massey 可 polynomial-time unique decode 到半距离，故 DQI 可取

\[ \ell=\left\lfloor\frac{n+1}{2}\right\rfloor \]

并得到强 approximation bias。

该性能超过论文分析的已知经典 polynomial-time 方法，但目标参数区间尚无 standard assumption 下的 classical hardness theorem；应称相对已知算法的 apparent/superpolynomial speedup，不是已证明复杂度分离。具体资源估计可达 \(10^8\) logical Toffolis 与数千逻辑 qubits，渐近高效不等于近期低成本。

6. Sparse clauses 与 LDPC

若每约束只含少量变量，\(B\) sparse，\(C^\perp\) 是 LDPC code。Belief propagation 等 classical decoder 可处理线性比例随机 errors；可逆实现后给高-degree DQI。

原工作构造某些 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 结构也可能暴露经典可解性。

7. Quantum/soft decoders 与扩展

Soft decoder 输出 error distribution/amplitudes而非唯一 error，可扩大可用半径；quantum decoding measurements 与 Regev lattice duality 的新 tight bounds 改善 DQI parameter regime。扩展包括：

  • quadratic constraints 的更高阶 Fourier labels；

  • algebraic-geometry codes；

  • Hamiltonian DQI，准备 Gibbs/low-energy states；

  • planted inference 与 random-oracle separations 的近亲结构。

但 decoder 本身若 NP-hard 或需要 postselection，DQI 不再高效。Hamiltonian/quantum decoder 还要把 state preparation、成功概率与 uncomputation 全部计入。

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

8. 小结与习题

  • 稀疏约束使 objective 的 Fourier 支持由少量行向量生成。

  • Degree-\(\ell\) filter 对应 weight-\(\le\ell\) Fourier histories。

  • Syndrome decoder 相干恢复 history 以完成干涉，解码半径决定 approximation ratio。

  • OPI 有强相对已知经典算法表现但无匹配 hardness；MaxCut 已知限制必须保留。

  1. 推导 max-XORSAT objective 与满足数关系。

  2. 展开 \(f(x)^2\)，验证频率为 \(B^T y\)、\(|y|=2\)。

  3. 解释为什么 syndrome 相同的不同 \(y\) 会阻碍直接 uncompute。

  4. 在 \(q_0=1/2\) 时化简 semicircle formula。

参考文献与 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。