論文の概要: Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers

• arxiv url: http://arxiv.org/abs/2610.02939v1
• Date: Fri, 02 Oct 2026 07:30:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.254233
• Title: Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers
• Title（参考訳）: ハミルトニアンシミュレーション、微分方程式および線形系解法に対するルートスパーシティスケーリング
• Abstract要約: 我々は、ハミルトニアンシミュレーション、線形微分方程式、および空間性への平方根依存を持つ線形系に対して量子アルゴリズムを与える。 散逸線型微分方程式に対して、$mathcalO(bar g[sqrts(+sqrt)+1]log(Cbar g/)$クエリを得る。 また、時間非依存のハミルトンシミュレーションと散逸型ODEソルバのゲート効率の実装も提供する。
• 参考スコア（独自算出の注目度）: 0.27998963147546146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an $s$-sparse Hermitian matrix with row and column Euclidean norms bounded by $η$, evolution for time $t$ to error $ε$ uses $\mathcal{O}(\sqrt{s}τ+\sqrt{sτ\log(1/ε)}+\log(1/ε))$ queries, where $τ=η|t|$. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in $\sqrt{s}τ$ and $\log(1/ε)$. For dissipative linear differential equations we obtain $\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))$ queries, where $τ$ is the evolution time multiplied by a norm bound, $\bar g$ bounds the ratio of combined input and source norms to the final-solution norm, and $C$ is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give $\mathcal{O}(κ\sqrt{s}\log(1/ε))$ queries when $\|A\|\le1$ and $\|A^{-1}\|\leκ$, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.
• Abstract（参考訳）: 我々は、ハミルトニアンシミュレーション、線形微分方程式、および空間性への平方根依存を持つ線形系に対して量子アルゴリズムを与える。 行と列が有界な $η$ を持つ $s$-スパースエルミート行列に対して、時間 $t$ to error $ε$ は $\mathcal{O}(\sqrt{s}τ+\sqrt{sτ\log(1/ε)}+\log(1/ε))$ クエリを使用し、$τ=η|t|$ である。 同じ境界線は、時間依存ハミルトニアンであり、コヒーレントな時間インデクシングされたスパースアクセスと認定された時間離散化を持つ。 我々の構成は、正確にエントリーワイズ表現とケイリー変換器を組み合わせたものである。 結合の下限は時間、空間、精度に依存し、$\sqrt{s}τ$と$\log(1/ε)$の一様加法境界を除外する。 散逸線型微分方程式に対して、$\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))$ query, where $τ$ is the evolution time multiplied by a norm bound, $\bar g$ bounds the ratio of combination input and source norms to the final-solution norm, $C$ is a absolute constant。 ハミルトン成分と散逸成分を分離し、一般定数生成器を扱い、この境界を研ぎます。 下界は時間依存方程式に対する関節パラメータ依存性と正の半定値散逸に対する精度硬度をキャプチャする。 線型系に対しては、ケイリー・ウォークとチェビシェフ・フィルターは$\mathcal{O}(κ\sqrt{s}\log(1/ε))$ query if $\|A\|\le1$ and $\|A^{-1}\|\leκ$ を与える。 リプシッツ時間依存を含む時間非依存ハミルトニアンシミュレーションのゲート効率な実装や、効率的なエントリ復号、算術、必要なソース準備を与えられた逆精度で多対数的オーバーヘッドを持つクエリ境界を保持する散逸型ODEソルバも提供する。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Quantum simulation of slow analytic time-dependent Hamiltonians [10.542661137364275]
  我々は,H(t)=H(t/T)$を$|H(s)|leq$で解析し,ほぼ加法的なクエリ複雑性とゲートオーバヘッドを実現する量子アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2026-08-18T11:14:53Z)
• Time-Dependent Hamiltonian Simulation with Optimal Query Complexity [7.005823894951329]
  一般的な$n$-qubit 時間依存ハミルトニアン $H(t)$ on $[0,T]$ をシミュレートするためのクエリ最適化アルゴリズムを与える。 トランスデューサを異なる回数で適用する回路の重み付けの組み合わせは、この状態の減衰を要因的に省略することによる誤差を生じさせる。 時間非依存のハミルトニアンに対しては、同じ方法がキュービット化のクエリ最適化の代替となる。
  論文  参考訳（メタデータ） (2026-08-06T14:35:47Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Efficient Quantum Algorithm for Solving Linear Distributed Delay Differential Equations [3.3083504598202733]
  非マルコフ力学は量子系と古典系の両方においてユビキタスである。 線形分散遅延微分方程式を解くための効率的な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-18T17:13:50Z)
• Transmutation based Quantum Simulation for Non-unitary Dynamics [35.35971148847751]
  A=Ldagger L$という形の正半定値作用素によって生成される散逸拡散力学をシミュレートする量子アルゴリズムを提案する。 我々の主な道具はカンナイ変換であり、これは拡散半群 $e-TA$ をユニタリ波動伝搬器のガウス重み付き重ね合わせとして表す。
  論文  参考訳（メタデータ） (2026-01-07T05:47:22Z)
• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。 特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
  論文  参考訳（メタデータ） (2024-10-30T10:09:05Z)
• Control of the von Neumann Entropy for an Open Two-Qubit System Using Coherent and Incoherent Drives [50.24983453990065]
  本稿では、時間依存デコヒーレンス率を誘導するコヒーレント制御と非コヒーレント制御を備えた開2量子系のフォン・ノイマンエントロピー$S(rho(t))$を操作するためのアプローチを開発することに専念する。 a) the final entropy $S(rho(T))$; (b) steering $S(rho(T))$ to a given target value; (c) steering $S(rho(T))$ to a target value and satisfying the pointwise state constraint $S(T)
  論文  参考訳（メタデータ） (2024-05-10T10:01:10Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)

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

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