論文の概要: Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

• arxiv url: http://arxiv.org/abs/2609.40302v1
• Date: Wed, 30 Sep 2026 17:51:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.265365
• Title: Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
• Title（参考訳）: 線形時間におけるスパースSDPの解法:量子OR補題による古典的アルゴリズム
• Abstract要約: 有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
• 参考スコア（独自算出の注目度）: 70.99943094379263
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.
• Abstract（参考訳）: 低ランクな仮定やフロベニウスノルムを制約行列に依存させることなく、有界ラディウス系におけるスパース半定プログラムに対する最初の線形時間古典的解法を与える。 定数精度と有界原始および双対半径に対して、Brandão et al (2019) と van Apeldoorn and Gilyén (2019) の先行量子アルゴリズムは、行列次元 $n$ と制約数 $m$ に依存する$\widetilde{O}(\sqrt{n}+\sqrt{m})$を達成した。 既存の古典的メソッドのランタイム $\widetilde{O}(mn)$ と比較すると、$m \approx n$ のときのクォート量子スピードアップが示唆される。 通常のグローバーのスピードアップ以外にも、この分離は、サンプル再利用機構がギブス状態の準備コストを制約探索から切り離したQuantum OR lemmaに依存している。 この再利用機構は,スパースSDPに対して古典的に実現可能であることを示す。 我々の主な技術的貢献は、スパースハミルトニアンのギブス状態に関して多くの期待値を同時に推定する古典的な手続きである。 これはランダム化されたランツォスフィルタと効率的なサンプリングベース推定器を組み合わせたものである。 また、SDP問題解決のための確率的オンライン学習フレームワークを導入し、標準的なオラクルベースのMMWUアプローチよりも精度依存性を大幅に改善した。 $s$ は入力行列の間隔を表し、$γ:=Rr/\varepsilon$ はプリマル $(R)$ と双対 $(r)$ radii とターゲット精度 $(\varepsilon)$ に依存する。 $γ^2\leq\min\{m,n/s\}$ とすると、解法は時間 $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$ で実行される。 γ=O(1)$ の場合、$\widetilde{O}\left((n+m)s\right)$ であり、$O(mns)$ 入力サイズのサブ線形である。 量子アルゴリズムと同様に、これは既知の下界を$m$と$n$で、対数係数まで一致させる。 これは、次元 $m$ と $n$ に関して、ジェネリックスパース SDP 解決の超四進量子優位性は存在しないことを意味する。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Dequantization and Hardness of Spectral Sum Estimation [1.0323063834827415]
  対数行列式などの行列のスペクトル和を推定するための新しい定式化と硬度結果を与える。 古典的な上界を$mathsfDQC1$-completenessで補い、特定のスペクトル和を推定する。
  論文  参考訳（メタデータ） (2025-09-24T14:44:53Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• 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)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)

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

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