論文の概要: Query-optimal quantum simulation of Lindblad evolution
- arxiv url: http://arxiv.org/abs/2609.17490v1
- Date: Tue, 15 Sep 2026 17:32:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 14:56:08.638123
- Title: Query-optimal quantum simulation of Lindblad evolution
- Title（参考訳）: リンドブラッド進化のクエリ-最適量子シミュレーション
- Abstract要約: ハミルトニアンシミュレーションは、加法的なクエリの下限、非公式に$(t + Mathrmpolylog (1/))$を提供する。
一般リンドブラッドシミュレーションで知られている最もよく知られたアルゴリズムは、門の複雑さにおいて乗法上界、非公式に$mathcalO(t,mathrmpolylog (1/))$を達成する。
- 参考スコア（独自算出の注目度）: 8.658596218544773
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For the problem of simulating Lindblad evolution for time $t$ to precision $ε$, Hamiltonian simulation provides an additive query lower bound, informally, $Ω(t + \mathrm{polylog}(1/ε))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/ε))$, in gate complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. Although our additional gate complexity is higher than that of existing algorithms, our optimal query complexity resolves the question of how much oracle access is fundamentally necessary and identifies the remaining challenge to achieve the optimal gate complexity.
- Abstract（参考訳）: 時間$t$から精度$ε$へのリンドブラッドの進化をシミュレートする問題に対して、ハミルトニアン・シミュレーションは加法的なクエリの下限(非公式に$Ω(t + \mathrm{polylog}(1/ε))$)を提供する。
しかし、一般リンドブラッドシミュレーションの最もよく知られたアルゴリズムは、ゲート複雑性において、乗法上界、非公式に$\mathcal{O}(t\,\mathrm{polylog}(1/ε))$を達成している。
この乗法的依存が必要とされるかどうかはまだ明らかではない。
本稿では,ブロックエンコーディングモデルにおける進化時間と精度に最適な付加的依存性を持つアルゴリズムを提供することにより,クエリ複雑性のギャップを埋める。
提案手法では, 触媒除去誤差を抑制するために, 異なる長さの再利用回路の線形結合とともに, 1次近似を進化チャネルに構成する際のクエリコストを低減するためにトランスデューサフレームワークを用いる。
我々の追加ゲートの複雑さは既存のアルゴリズムよりも高いが、最適なクエリの複雑さは、どのくらいのオラクルアクセスが必要かという問題を解決し、最適なゲートの複雑さを達成するための残りの課題を特定する。
関連論文リスト
- Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Optimal quantum simulation of linear non-unitary dynamics [0.31439717339537293]
有界時間依存演算子$-A$によって生成される時間進化をシミュレートする量子アルゴリズムを提案する。
本稿では,最近のLinear-Combination-of-Hamiltonian-Simulation (LCHS)フレームワークを一般化する。
論文 参考訳（メタデータ） (2025-08-26T17:58:27Z) - Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
本稿では,次元$d$の適応的複雑性依存性を改善する並列サンプリング手法を提案する。
我々の手法は科学計算による並列シミュレーション技術に基づいている。
論文 参考訳（メタデータ） (2024-12-10T11:50:46Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。
本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
論文 参考訳（メタデータ） (2024-08-11T10:28:49Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Optimal scaling quantum linear systems solver via discrete adiabatic
theorem [0.9846257338039974]
離散的に最適となる線形系を解くための量子アルゴリズムを開発した。
既存の最適化手法と比較して,本アルゴリズムはよりシンプルで実装が容易である。
論文 参考訳（メタデータ） (2021-11-16T00:21:37Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。
これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
論文 参考訳（メタデータ） (2021-02-16T18:15:51Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳（メタデータ） (2021-02-12T12:38:03Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。