スーパーポジションにおける計算に対する線形リードアウト床としきい値回復

要旨: 重ね合わせ（スーパーポジション）における計算のための2つの最近のアプローチは、異なる再帰的な容量（キャパシティ）の領域に到達する。H"anniらは、近似線形の再帰テンプレートによって、幅 d において O(d^{3/2}) で計算可能な特徴量を保証する。一方、Adler と Shavit は、閾値処理されたブール（Boolean）回復を用いて、ほぼ2次の容量（対数因子まで）に到達する。本論文の主な貢献は概念的であり、これらの結果は両立しないのではなく、異なるインターフェースの不変条件を維持しているため矛盾しないことを論じ、その違いを形式化する。
ツールとして、双直交（biorthogonal）な線形読み出しに対する rank-trace Welch 型の下界を記録する。F f d のとき、単位対角（unit-diagonal）の任意の線形読み出しの最悪の場合の対角外クロストークは O(d^{-1/2}) であり、その下界は、単位ノルムのタイトフレームに対して平均的に厳密に達成される。特徴量の負荷が2次（quadratic）で F=d^2 の場合、ランダム支持（random-support）の閾値回復は、疎度 s=O(d/\log d) で成功するが、線形読み出しは依然として、ベルヌーイ疎状態（Bernoulli sparse states）に対して、座標あたりの平均2乗誤差が O(s/d) を負う。Welch 床（floor）を H"anni 補正層に対して公開されている許容誤差に照合すると、d^{3/2} スケールは、そのテンプレートに対する整合性（compatibility）の閾値であって普遍的な上界ではないことが説明できる。H"anni テンプレートを超える頑健な非線形リセットは未解決として残されている。