論文の概要: A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers

• arxiv url: http://arxiv.org/abs/2609.22445v1
• Date: Fri, 18 Sep 2026 18:02:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:00.40494
• Title: A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers
• Title（参考訳）: スパース量子線形システム解法における近接最適継手下界
• Abstract要約: 量子線形システム解法は、量子コンピューティングにおいて中心となるアルゴリズムプリミティブの1つを形成する。 $と$varepsilonへの依存はすでによく理解されています。 スパースアクセスモデルにおいて、完全関節下界$(sqrts)$を証明します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum linear system solvers form one of the central algorithmic primitives in quantum computing, with applications ranging from differential equations and optimization to machine learning. Their cost is commonly measured through query complexity, which counts the number of oracle calls needed to access the input matrix. In the sparse-access model, this complexity is governed by three parameters: the condition number $κ$, the sparsity $s$ of the input matrix, and the target precision $\varepsilon$. The dependence on $κ$ and $\varepsilon$ is already well understood through the lower bound $Ω(κ\log(1/\varepsilon))$, which matches the best known scaling in these parameters. Once the sparsity $s$ is included, however, the expected lower bound has long been conjectured to be $Ω(κ\sqrt{s}\log(1/\varepsilon))$. Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound $Ω(κ\sqrt{s})$ for constant error $\varepsilon$. In this work, we complete the picture and prove the full joint lower bound $Ω(κ\sqrt{s}\log(1/\varepsilon))$ in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
• Abstract（参考訳）: 量子線形システムソルバは、微分方程式や最適化から機械学習まで、量子コンピューティングにおいて中心的なアルゴリズムプリミティブの1つを形成する。 それらのコストは通常、クエリの複雑さによって測定され、入力行列にアクセスするのに必要なオラクル呼び出しの数をカウントする。 スパースアクセスモデルでは、この複雑さは条件番号$κ$、入力行列のスパーシティ$s$、ターゲット精度$\varepsilon$の3つのパラメータで制御される。 κ$と$\varepsilon$への依存は、これらのパラメータの最もよく知られたスケーリングと一致する、下界の$Ω(κ\log(1/\varepsilon)$を通じて既によく理解されている。 しかし、スパーシティ$s$が含まれると、予想される下界は、長い間$Ω(κ\sqrt{s}\log(1/\varepsilon))$と推測されてきた。 Mori ら (Quantum Sci. Tech. 11 035063 (2026)) による最近の研究は、定数誤差 $\varepsilon$ に対して下界 $Ω(κ\sqrt{s})$ を確立することで、この目標に向かって重要な一歩を踏み出した。 本研究では、この図を完成し、スパースアクセスモデルにおいて完全関節下界$Ω(κ\sqrt{s}\log(1/\varepsilon))$を証明し、3つのパラメータに同時に依存することを期待する。

関連論文リスト

• Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
  メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。 まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。 決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
  論文  参考訳（メタデータ） (2026-07-21T00:40:59Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。 格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
  論文  参考訳（メタデータ） (2026-04-27T10:23:24Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations [0.0]
  本稿では,Kaczmarz法に基づく量子線形システム解法を提案する。 その単純さとメモリコストの低さにより、データ回帰、トモグラフィー再構成、最適化にまたがる実用的な選択肢となっている。
  論文  参考訳（メタデータ） (2026-01-04T03:13:36Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。 我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。 アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
  論文  参考訳（メタデータ） (2022-12-19T09:36:33Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Calculable lower bounds on the efficiency of universal sets of quantum gates [0.0]
  現在利用可能な量子コンピュータ、いわゆるNoisy Intermediate-Scale Quantum (NISQ) は、比較的少ない量子ビットと適度なゲートフィデリティによって特徴づけられる。 本稿では、$mathrmgap_r(mathcalS)$ 上の下界を導出し、その結果、$d$次元量子ゲートの普遍集合の効率について述べる。
  論文  参考訳（メタデータ） (2022-01-27T19:38:13Z)

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

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