論文の概要: Learning at the Edge of Causality: Optimal Learning-Sample Complexity from No-Signaling Constraints

• arxiv url: http://arxiv.org/abs/2601.12651v1
• Date: Mon, 19 Jan 2026 01:52:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:22.722971
• Title: Learning at the Edge of Causality: Optimal Learning-Sample Complexity from No-Signaling Constraints
• Title（参考訳）: 因果関係の端で学ぶ:無署名制約による最適学習-サンプル複雑度
• Authors: Jeongho Bang, Kyoungho Cho, Jeongwoo Jae,
• Abstract要約: 量子学習のサンプルコストを最終的にどう解決するかを研究する。 標準量子論はそのような未知の状態反射を禁ずる。 非署名は学習可能性の規制機関として機能する。
• 参考スコア（独自算出の注目度）: 0.3277163122167433
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: What ultimately fixes the sample cost of quantum learning -- algorithmic ingenuity or physical law? We study this question in an arena where computation, learning, and causality collide. A twist on Grover's search that reflects about an a priori unknown state can collapse the query complexity from $O(\sqrt{N})$ to $O(\log N)$ over a search space $N$, i.e., an exponential speedup. Yet, standard quantum theory forbids such a unknown-state reflection (no-reflection theorem). We therefore build a state-learning-assisted architecture, called ``amplify-learn,'' which alternates the coherent amplitude amplification with state learning. Embedding this amplify-learn into the Bao-Bouland-Jordan no-signaling framework, we show that the logarithmic-round dream would open a super-luminal communication channel unless each round expends the learning-sample and reflection-circuit budgets scaling at least as $Ω(\sqrt{N}/\log N)$. In parallel, we derive tight computational learning-theoretic sample bounds for learning circuit-generated pure states, revealing a state-universal ansatz ``lock'' at order $N$ in the worst case. The dramatic closure is that no-signaling does not merely veto the unphysical primitive, but it fixes the only consistent reflection-circuit complexity, and feeding this causality-enforced complexity into the computational learning bound makes it collapse onto the very same $\sqrt{N}/\log N$ scaling demanded by no-signaling alone. No-signaling thus acts as a regulator of learnability: a constraint that mediates between physics and computation, welding query, gate, and sample complexities into a single causality-compatible triangle.
• Abstract（参考訳）: 結局、量子学習のサンプルコスト、アルゴリズムの創発性や物理法則をどう解決するか? 我々は,この問題を計算,学習,因果関係が衝突する領域で研究する。 先行しない状態に関するグロバーの探索のツイストは、クエリの複雑さを$O(\sqrt{N})$から$O(\log N)$に分解することができる。 しかし、標準量子論はそのような未知状態の反射(非反射定理)を禁ずる。 そこで我々は'amplify-learn'と呼ばれる状態学習支援アーキテクチャを構築し、コヒーレント振幅増幅と状態学習を交互に行う。 この増幅学習をBao-Bouland-Jordan no-signalingフレームワークに組み込むと、各ラウンドが学習サンプルと反射回路の予算を少なくとも$Ω(\sqrt{N}/\log N)$にスケーリングしなければ、対数単位の夢が超光通信チャネルを開くことが示される。 並列に、回路生成された純粋状態の学習のための厳密な計算学習理論サンプルバウンドを導出し、最悪の場合、状態ユニバーサルなアンサッツ ``lock'' をオーダー$N$で表す。 劇的な閉包は、非シグナリングは単に非物理学的プリミティブを拒否するだけでなく、唯一一貫したリフレクション・サーキットの複雑さを修正し、この因果性強化された複雑さを計算学習境界に供給することで、非シグナリングによって要求されるスケーリングが全く同じ$\sqrt{N}/\log N$に崩壊するということである。 物理と計算の間を仲介する制約、溶接クエリ、ゲート、サンプル複雑度を1つの因果整合三角形に制限する。

関連論文リスト

• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  量子多体系のシミュレーションを劇的に高速化するマルコフ連鎖モンテカルロ(MCMC)アルゴリズムを導入する。 我々は,量子物理学のベンチマーク問題に対するアルゴリズムの有効性を検証し,既知の理論結果を正確に再現する。 我々の研究は、大規模確率的推論のための強力なツールを提供し、物理学に着想を得た生成モデルのための道を開く。
  論文  参考訳（メタデータ） (2025-10-13T07:57:21Z)
• A Quantum Algorithm For Computing Contextuality Bounds [0.0]
  我々はGroverの探索アルゴリズムに基づく量子アルゴリズムを提供し、古典的なブルート力法よりも高速な$O(sqrtn loglogn)$$$$O(sqrtn loglogn)$O(sqrtn loglogn)$O(n$)$O(sqrtn loglogn)$の文脈性を計算する。 また,基本状態の位相に関連情報をエンコードし,回路幅と深度要件を低減させるGroverのバリエーションについても検討した。
  論文  参考訳（メタデータ） (2025-09-24T15:36:02Z)
• Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
  量子多体物理学における基本的な問題は、局所ハミルトニアンの基底状態を見つけることである。 基底状態特性を学習するためのシステムサイズ$n$とは無関係に,一定のサンプル複雑性を実現する2つのアプローチを導入する。
  論文  参考訳（メタデータ） (2024-05-28T18:00:32Z)
• Learning quantum states and unitaries of bounded gate complexity [2.034135396070497]
  我々は、G$2量子ビットゲートを持つ量子回路によって生成された状態を微量なトレース距離に学習するには、G$で線形にスケールするサンプル複雑性が必要であることを証明した。 また、$G$ゲートによって生成されるユニタリを、小さな平均ケースエラーに対して線形に$G$で学習するのに最適なクエリの複雑さが証明される。
  論文  参考訳（メタデータ） (2023-10-30T18:00:03Z)
• Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications [0.0]
  量子アルゴリズムは量子状態の振幅を操作して計算問題の解を求める。 量子状態の振幅に非線形関数の一般クラスを適用するための枠組みを提案する。 我々の研究は、最適化、状態準備、量子化学、機械学習といった分野において、潜在的に多くの応用が可能な重要かつ効率的なビルディングブロックを提供する。
  論文  参考訳（メタデータ） (2023-09-18T14:57:21Z)
• Simulating Structural Plasticity of the Brain more Scalable than Expected [69.39201743340747]
  Rinkeらは、Barnes-Hutアルゴリズムの変種を用いて、現在のハードウェア上で最大10億のニューロンに対して構造的可塑性をシミュレートするスケーラブルなアルゴリズムを導入した。 アルゴリズムを慎重に検討すると、理論ランタイムは$O(n log2 n)$と分類できる。
  論文  参考訳（メタデータ） (2022-10-11T09:02:43Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  古典ベクトル $mathbfb$ は量子状態の振幅で符号化される。 任意の状態の$Q$ qubitsは通常、約2Q$のエンタングゲートを必要とする。 状態準備に必要な量子資源を柔軟に削減できる決定論的(非変分法)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-26T07:37:54Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。 格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。 NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
  論文  参考訳（メタデータ） (2020-02-25T19:18:36Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。