論文の概要: Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm
- arxiv url: http://arxiv.org/abs/2610.02030v1
- Date: Thu, 01 Oct 2026 16:47:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 01:19:24.309255
- Title: Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm
- Title（参考訳）: 最大列ユークリッドノルムに最適依存を持つスパースハミルトンシミュレーション
- Abstract要約: 我々は、$d$sparse Hermitian Hamiltonian $H$をシミュレートするための量子アルゴリズムを与える。
$d>1$と$tgelog (2/)$の場合、バウンダリは最悪のケースの低いバウンダリと一致する。
また、行と列ごとに最大$d$のノンゼロエントリを持つブラックボックスユニタリのゲート効率の実装も提供します。
- 参考スコア（独自算出の注目度）: 5.374239522015395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a quantum algorithm for simulating a $d$-sparse Hermitian Hamiltonian $H$, assuming a known upper bound $Λ$ on its maximum column Euclidean norm $\|H\|_{1\to2}$. For $tΛ\ge1/2$, simulation with operator-norm error $ε$ uses \[ O\!\left(tΛ\sqrt d+\sqrt d\log(2/ε)\right) \] sparse-oracle queries. This removes the subpolynomial overhead in Low's algorithm [STOC 2019], replacing it with an additive logarithmic precision term. For $d>1$ and $tΛ\ge\log(2/ε)$, the bound matches the worst-case lower bound. A known spectral-norm upper bound may also be used in place of $Λ$. The number of 1- and 2-qubit gates is linear in the query scale, up to oracle costs and polynomial overhead in the input bit lengths and logarithmic precision parameters. As applications, we obtain $O(κ\sqrt d\,\mathrm{polylog}(κ/ε))$ queries for solving $d$-sparse quantum linear systems with $\|A\|\le1$ and $\|A^{-1}\|\leκ$, under standard sparse and state-preparation access. We also give a gate-efficient implementation of black-box unitaries with at most $d$ nonzero entries per row and column using $O(\sqrt d\log(2/ε))$ queries, given sparse access to the unitary and its adjoint. At constant error, the query bound is optimal and yields $Θ(\sqrt N)$ queries for arbitrary $N\times N$ unitaries, resolving the open question on black-box unitary implementation posed by Berry and Childs [QIC 2012].
- Abstract（参考訳）: 我々は、最大列のユークリッドノルム $\|H\|_{1\to2}$ 上で既知の上限ドルを仮定して、$d$-sparse Hermitian Hamiltonian $H$ をシミュレートする量子アルゴリズムを与える。
演算子-ノルム誤差の$ε$ は \[O\!
sparse-oracle クエリは、sparse-oracle クエリである。
これにより、ローアルゴリズム(STOC 2019)のサブポリノミカルオーバーヘッドを除去し、加算対数精度項に置き換える。
$d>1$と$t>\ge\log(2/ε)$の場合、バウンダリは最悪のケースの低いバウンダリと一致する。
既知のスペクトル-ノルム上界は、$$の代わりにも用いられる。
1ビットと2ビットのゲートの数は、入力ビット長および対数精度パラメータにおけるオラクルコストと多項式オーバーヘッドまで、クエリスケールで線形である。
応用として、$O(κ\sqrt d\,\mathrm{polylog}(κ/ε))$ query for solve $d$-sparse quantum linear systems with $\|A\|\le1$ and $\|A^{-1}\|\leκ$, under standard sparse and state-preparation access。
O(\sqrt d\log(2/ε))$クエリを使って、行あたりの最大$d$非ゼロエントリと列あたり$O(\sqrt d\log(2/ε))のクエリを使ってブラックボックスのユニタリをゲート効率よく実装する。
一定のエラーでは、クエリバウンダリは最適であり、任意の$N\times N$ユニタリーに対して$(\sqrt N)$クエリを出力し、Berry and Childs (QIC 2012) が提案したブラックボックスのユニタリー実装に関するオープンな問題を解決する。
関連論文リスト
- Optimal query complexity for fractional quantum evolution [0.0]
分数クエリ問題に対する最適なクエリ複雑性は、$_!left(frac1logfrac1varepsilonright)$である。
論文 参考訳（メタデータ） (2026-10-01T16:08:16Z) - Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳（メタデータ） (2026-09-30T17:51:21Z) - Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding [26.296743455346604]
多くの量子アルゴリズムは古典的なデータへのコヒーレントなアクセスを必要とし、しばしば量子読み取り専用メモリ(QROM)によってモデル化される。
スパースQROMの$T$数を調べ、$2n$アドレスの$s$だけが非ゼロデータを格納している。
我々の上界はマルチレベルハッシュ方式を使用し、下界はスパースQROMを減らし、適応的なClifford+$T$回路のカウント引数を使用する。
論文 参考訳（メタデータ） (2026-07-30T14:18:29Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳（メタデータ） (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。