論文の概要: Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness
- arxiv url: http://arxiv.org/abs/2609.40100v1
- Date: Wed, 30 Sep 2026 16:35:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:28.090686
- Title: Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness
- Title（参考訳）: 対数次元フェルミオンサンプリング:抗濃度と平均硬度
- Abstract要約: 両保証の対数深度は同じアンサンブルで十分であることを示す。
我々は、4つのネイティブ層にハードインスタンスを構築し、それらを典型的なスケジュールに埋め込み、合理的な線形プログラムデコーダを用いてケイリーパスに沿って補間する。
- 参考スコア（独自算出の注目度）: 0.42970700836450476
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sampling problems give some of the clearest conditional separations between quantum and classical computation. In Fermion Sampling, passive linear optics acts on a non-Gaussian magic input. Globally Haar-random transformations give anticoncentration and high-precision average-case hardness, but require linear depth and quadratically many gates. A natural open question is whether linear depth is necessary? We show that logarithmic depth suffices for both guarantees in the same ensemble. For fresh uniform matchings with independent Haar two-mode gates, the collision reaches the passive-Haar scale at a sharp threshold of $\log n/\log(9/4)\approx0.855\log_2 n$ layers, with an explicit limiting transition profile and a matching lower bound from two-particle correlations. The mechanism is input-dependent: the magic input suppresses the extensive weight of the slowest relaxation mode, leaving the next to set the scale. An occupation-basis input retains large collision even under full Haar randomness. At a larger logarithmic depth, we prove, in the real-RAM model, average-case $\#\mathsf{P}$-hardness of estimating output probabilities to additive error $2^{-O(n\log^2 n)}$ on any fixed fraction of instances above $3/4$. We construct hard instances in four native layers, embed them in typical schedules, and interpolate along Cayley paths using a rational linear-program decoder. A finite $192$-gate alphabet preserves the collision law exactly. Both guarantees use logarithmic native fermionic depth between arbitrary mode pairs and $O(n\log n)$ gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the $1/N$ scale, where $N=\binom{n}{n/2}$, required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.
- Abstract（参考訳）: サンプリング問題は、量子計算と古典計算の最も明確な条件的分離を与える。
フェルミオンサンプリングでは、受動線形光学は非ガウス魔法の入力に作用する。
大域的にハールランダム変換は、反濃度と高精度の平均ケース硬度を与えるが、線形深さと二次的な多くのゲートを必要とする。
自然開問題とは、線形深さが必要かどうかである。
両保証の対数深度は同じアンサンブルで十分であることを示す。
独立なハール2モードゲートとの新しい均一なマッチングでは、衝突は2粒子相関による明示的な制限遷移プロファイルと一致した下界を持つ、$\log n/\log(9/4)\approx0.855\log_2 n$のシャープしきい値でパッシ・ハールスケールに達する。
このメカニズムは入力に依存しており、マジック入力は最も遅い緩和モードの広い重量を抑え、次にスケールを設定する。
職業ベース入力は、完全なハールランダム性の下でも大きな衝突を保持する。
より大きい対数深さでは、平均ケース $\#\mathsf{P}$-hardness of estimates output probabilities to additive error $2^{-O(n\log^2 n)}$ on any fixed fraction of instance/4$。
我々は、4つのネイティブ層にハードインスタンスを構築し、それらを典型的なスケジュールに埋め込み、合理的な線形プログラムデコーダを用いてケイリーパスに沿って補間する。
有限の192$ゲートのアルファベットは、衝突法則を正確に保存する。
どちらも任意のモードペアと$O(n\log n)$ゲートの間の対数的ネイティブフェルミオン深さを保証し、グローバル・ハール構成の二次予算を置き換える。
証明された精度は1/N$スケールよりも細かく、サンプリング・トゥ・カウントで要求される$N=\binom{n}{n/2}$であり、一定の全変量距離におけるサンプリングの硬さは依然としてオープンである。
関連論文リスト
- Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks [38.61040361525374]
入力は、異なる入力がネットワーク全体を使用する場合であっても、ほとんど隠れたユニットを起動する。
本研究では,この入力依存空間の統計的複雑さを1層ReLUモデルで検討する。
論文 参考訳（メタデータ） (2026-09-08T17:53:03Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency [0.5076419064097732]
最寄りのハードウェアに対する$k$粒子フェルミオンアーキテクチャを提案する。
レンガの壁は動的リー代数 $mathfraku(n)$ を持ち、Givens 回転を介して$U(n)$ を直接パラメトリズする。
同様の硬度保証は、勾配ごとに8klog n$の評価で達成し、同じ係数が3n/(8k)$還元である。
論文 参考訳（メタデータ） (2026-07-27T05:23:32Z) - Wavelet Variance Equipartition as a Threshold for World-Model Quality and Quantum Kernel TN-Simulability [0.0]
我々はウェーブレットスケーリング指数$$を臨界診断として同定する。
振幅符号化された量子カーネルの古典的シミュラビリティのシャープな遷移境界として$=1/2$を確立する。
この分散は、厳密には$Var[X] = (d-2)$としてスケールする。
論文 参考訳（メタデータ） (2026-05-12T05:41:12Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion [16.463220658992064]
分布の幅広いクラスに対する最初のサンプリングアルゴリズムを提供する。
我々のアルゴリズムは時間反転拡散過程をシミュレートする。
メタスタビリティを回避し、モード位置に関する事前の知識を必要とせず、よく知られた対数平滑性仮定を緩和する。
論文 参考訳（メタデータ） (2024-12-31T17:51:39Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Approximate unitary $t$-designs by short random quantum circuits using
nearest-neighbor and long-range gates [0.0]
ply(t)cdot n1/D$-depth local random quantum circuits with two qudit Near-ighbor gates are almost $t$-designs in various measures。
また,異なるモデルを用いた深度O(log(n)loglog(n)において,反濃縮が可能であることを証明した。
論文 参考訳（メタデータ） (2018-09-18T22:28:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。