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

• arxiv url: http://arxiv.org/abs/2509.19161v3
• Date: Fri, 07 Nov 2025 21:36:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 12:49:31.796977
• Title: Realizable Circuit Complexity: Embedding Computation in Space-Time
• Title（参考訳）: 実現可能な回路複雑性: 計算を時空間に埋め込む
• Authors: Benjamin Prada, Ankur Mali,
• Abstract要約: 物理的な$d$次元空間に埋め込まれた、実現可能な回路クラス $mathbfRC_d$ の族を紹介する。 このフレームワークでは、$nd/(d-1))$のアルゴリズムは$nd/(d-1))$の入力にスケールできない。 幾何、因果性、情報フローを統一することにより、$mathbfRC_d$は回路を物理領域に拡張する。
• 参考スコア（独自算出の注目度）: 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 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$次元空間に埋め込まれたモデル計算である $\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$は回路の複雑さを物理領域に拡張し、計算の普遍的なスケーリング法則を明らかにする。

関連論文リスト

• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) [0.9023122463034333]
  $mathsfQAC0$は、任意の単一量子ビットゲートと一般化されたトフォリゲートから構成される定数深さ量子回路のクラスである。 我々は、$mathsfQAC0$回路が従来の回路よりもはるかに強力であることを示す。
  論文  参考訳（メタデータ） (2026-01-06T18:40:44Z)
• 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)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• 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)
• The Space Complexity of Approximating Logistic Loss [11.338399194998933]
  a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound if $epsilon$ is constant。 また、$mu_mathbfy(mathbfX)$は計算が難しいという事前予想も否定する。
  論文  参考訳（メタデータ） (2024-12-03T18:11:37Z)
• On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
  深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。 これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
  論文  参考訳（メタデータ） (2024-10-09T02:55:57Z)
• 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)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。 私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
  論文  参考訳（メタデータ） (2023-11-22T20:27:05Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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