揭示量子叠加态计算中两种方法的差异本质，解释容量上限为何不同。
Linear-Readout Floors and Threshold Recovery in Computation in Superposition
- 提出双正交线性读出的秩-迹下界，揭示误差下限机制
- 在特征数 $F=d^2$ 时，阈值恢复可处理稀疏度 $s=O(d/"log d)$
- 解释 $d^{3/2}$ 容量源于模板兼容性，非普适上限
近期两种叠加态计算方法得出不同递归容量：Hänni 等基于近似线性递归模板，证明宽度为 $d$ 时可计算 $\tilde{O}(d^{3/2})$ 特征；Adler 与 Shavit 则通过阈值布尔恢复实现接近二次容量（含对数因子）。本文核心贡献为概念性：指出二者结果不矛盾，因维护不同接口不变量，并予以形式化。作为工具，我们给出双正交线性读出的秩-迹 Welch 型下界：当 $F \gg d$ 时，任意单位对角线线性读出的最坏情况非对角交叉干扰为 $Ω(d^{-1/2})$，且在单位范数紧框架上平均紧致。当特征负载达二次 $F=d^2$ 时，随机支持阈值恢复对稀疏度 $s=O(d/\log d)$ 可成功，而线性读出在伯努利稀疏态上仍存在 $Ω(s/d)$ 的平均坐标平方误差。将 Welch 下界与 Hänni 修正层容差匹配，解释了 $d^{3/2}$ 规模实为该模板的兼容性阈值，而非通用上限。超越 Hänni 模板的鲁棒非线性重置仍待探索。
原文摘要 · Abstract (English)
Two recent approaches to computation in superposition reach different recursive capacity regimes: Hänni et al. certify $\tilde{O}(d^{3/2})$ computable features in width $d$ via an approximate-linear recursive template, while Adler and Shavit reach near-quadratic capacity (up to logarithmic factors) using thresholded Boolean recovery. The main contribution of this paper is conceptual: we argue these results are not contradictory because they maintain different interface invariants, and we formalize the distinction. As a tool, we record a rank-trace Welch-type lower bound for biorthogonal linear readouts: for $F \gg d$, the worst-case off-diagonal cross-talk of any unit-diagonal linear readout is $Ω(d^{-1/2})$, and the bound is tight on average for unit-norm tight frames. At quadratic feature load $F=d^2$, random-support threshold recovery succeeds for sparsities $s=O(d/\log d)$, while linear readouts still incur $Ω(s/d)$ average per-coordinate squared error on Bernoulli sparse states. Matching the Welch floor against the published tolerance of the Hänni correction layer explains the $d^{3/2}$ scale as a compatibility threshold for that template, not a universal upper bound. Robust nonlinear reset beyond the Hänni template is left open.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。