論文の概要: Realizable Circuit Complexity: Embedding Computation in Space-Time

• arxiv url: http://arxiv.org/abs/2509.19161v2
• Date: Tue, 04 Nov 2025 17:17:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 16:37:26.440736
• Title: Realizable Circuit Complexity: Embedding Computation in Space-Time
• Title（参考訳）: 実現可能な回路複雑性: 計算を時空間に埋め込む
• Authors: Benjamin Prada, Ankur Mali,
• Abstract要約: 本稿では,実行時テキスト実現可能な回路クラスである $mathbfRC_d$ を紹介する。 このフレームワーク内では、$omega(nd/(d-1))$のアルゴリズムはエントロピーの入力にスケールできないこと、そして$d$次元の並列実装は、その最適シーケンシャルなアルゴリズムよりも少なくとも$(d-1)$のスピードアップを提供することを示す。
• 参考スコア（独自算出の注目度）: 0.2750124853532831
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classical circuit complexity characterizes parallel computation in purely combinatorial terms, ignoring the physical constraints that govern real hardware. The standard classes $\mathbf{NC}$, $\mathbf{AC}$, and $\mathbf{TC}$ treat unlimited fan-in, free interconnection, and polynomial gate counts as feasible -- assumptions that conflict with geometric, energetic, and thermodynamic realities. We introduce the family of \textit{realizable circuit classes} $\mathbf{RC}_d$, which model computation embedded in physical $d$-dimensional space. Each circuit in $\mathbf{RC}_d$ obeys conservative realizability laws: volume scales as $\mathcal{O}(t^d)$, cross-boundary information flux is bounded by $\mathcal{O}(t^{d-1})$ per unit time, and growth occurs through local, physically constructible edits. These bounds apply to all causal systems, classical or quantum. Within this framework, we show that algorithms with runtime $\omega(n^{d/(d-1)})$ cannot scale to inputs of maximal entropy, and that any $d$-dimensional parallel implementation offers at most a polynomial speed-up of degree $(d-1)$ over its optimal sequential counterpart. In the limit $d\to\infty$, $\mathbf{RC}_\infty(\mathrm{polylog})=\mathbf{NC}$, recovering classical parallelism as a non-physical idealization. By unifying geometry, causality, and information flow, $\mathbf{RC}_d$ extends circuit complexity into the physical domain, revealing universal scaling laws for computation.
• Abstract（参考訳）: 古典的な回路複雑性は、並列計算を純粋に組合せ的に特徴付け、実際のハードウェアを管理する物理的な制約を無視している。 標準クラス $\mathbf{NC}$, $\mathbf{AC}$, $\mathbf{TC}$ は、幾何学的、エネルギー的、熱力学的現実性と矛盾する仮定として、無限ファンイン、自由相互接続、多項式ゲート数を扱う。 物理的に$d$次元空間に埋め込まれたモデル計算である、textit{realizable circuit class} $\mathbf{RC}_d$の族を紹介する。 ボリュームスケールは$\mathcal{O}(t^d)$, クロスバウンダリ情報フラックスは、単位時間当たり$\mathcal{O}(t^{d-1})$でバウンドされ、局所的、物理的に構築可能な編集によって成長する。 これらの境界は古典的あるいは量子的な全ての因果系に適用できる。 このフレームワーク内では、実行時 $\omega(n^{d/(d-1)})$ のアルゴリズムは最大エントロピーの入力にスケールできないこと、そして任意の$d$次元並列実装は、その最適シーケンシャルの次数に対して少なくとも$(d-1)$の多項式スピードアップを提供することを示した。 d\to\infty$, $\mathbf{RC}_\infty(\mathrm{polylog})=\mathbf{NC}$ の極限において、古典的並列性は非物理的理想化として回復する。 幾何、因果関係、情報フローを統一することにより、$\mathbf{RC}_d$は回路の複雑さを物理領域に拡張し、計算の普遍的なスケーリング法則を明らかにする。

関連論文リスト

• Spectral Small-Incremental-Entangling: Breaking Quasi-Polynomial Complexity Barriers in Long-Range Interacting Systems [2.911917667184046]
  量子複雑性の鍵となる課題は、エンタングルメント構造が動的からどのように現れるかである。 本稿では,作用素の構造エンタング力を測定するスペクトルエンタングリング強度について紹介する。 我々はスペクトルSIE定理を証明し、R'enyi tanglement growth を$alpha ge 1/2$で普遍極限とし、絡み合いスペクトルの頑健な1/s2$tailを明らかにした。
  論文  参考訳（メタデータ） (2025-09-15T14:56:40Z)
• A Quantum Computational Perspective on Spread Complexity [0.0]
  我々は、時間進化と重ね合わせという2つの基本的な操作から構築された回路複雑性フレームワークの制限ケースとして、拡散複雑性が出現することを示すことによって、拡散複雑性と量子回路複雑性の直接的な接続を確立する。 提案手法では,単位ゲートとビーム分割演算がターゲット状態を生成する計算装置を活用し,合成コストの最小化により,無限小時間進化限界における複雑性の拡散に収束する複雑性尺度が得られた。
  論文  参考訳（メタデータ） (2025-06-08T19:04:42Z)
• Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding [30.769940410718558]
  テンソルバージョンにおけるキー値キャッシュは、推論中に重大なボトルネックを示す。 我々の研究は、テンソルアテンションバージョンによる空間複雑性障壁を一般化する。 全体として、我々の研究は、テンソルアテンションデコーディングにおけるKVキャッシュ圧縮の時間メモリトレードオフを理解するための理論的基盤を提供する。
  論文  参考訳（メタデータ） (2025-03-14T06:01:42Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  連続状態と行動空間を持つ非線形力学系の一般設定におけるオンライン強化学習のサンプル複雑性について検討した。 我々のアルゴリズムは、$mathcalO(N epsilon2 + Mathrmln(m(epsilon)/epsilon2)$のポリシーを後悔する。 力学がコンパクトで実数値のパラメータ集合によってパラメータ化される特別な場合、$mathcalO(sqrt)のポリシー後悔を証明する。
  論文  参考訳（メタデータ） (2025-01-27T10:01:28Z)
• Surrogate Constructed Scalable Circuits ADAPT-VQE in the Schwinger model [0.0]
  我々は,量子コンピュータ上の周期システムのシミュレーションをさらに進めるため,新しいアプローチ (SC)$2$-ADAPT-VQE を開発した。 我々の手法は、任意に大きいが、任意に小さくない体積に対して定義される座標不変作用素のプールからアンザッツを構築する。 提案手法では,古典的にトラクタブルなサーロゲート構成法を用いて,無関係な演算子をプールから取り除き,拡張性のある回路を定義する最小サイズを小さくする。
  論文  参考訳（メタデータ） (2024-08-22T18:00:00Z)
• Recurrent Complex-Weighted Autoencoders for Unsupervised Object Discovery [62.43562856605473]
  複雑な重み付き再帰的アーキテクチャの計算上の優位性について論じる。 本稿では,反復的制約満足度を実現する完全畳み込みオートエンコーダSynCxを提案する。
  論文  参考訳（メタデータ） (2024-05-27T15:47:03Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)

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

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