論文の概要: Quantum Algorithms for Triangle Cut Sparsification

• arxiv url: http://arxiv.org/abs/2606.06287v2
• Date: Fri, 05 Jun 2026 03:00:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-08 12:21:17.580139
• Title: Quantum Algorithms for Triangle Cut Sparsification
• Title（参考訳）: 三角切断スカラー化のための量子アルゴリズム
• Authors: Shan Jiang, Pan Peng,
• Abstract要約: 本稿では,各カットにまたがる三角形数を保存しながら,グラフサイズを小さくすることを目的とした三角形カットスペーシフィケーションの問題について検討する。 三角形を列挙する量子アルゴリズムを提案し, 頂点が$n$, 辺が$m$, 三角形が$t$のグラフが時間内に実行される。 三角関係測度に基づくクラスタリングアルゴリズムの応用を実証し、任意の$varepsilon$-triangle cutスペーサーのサイズの低い境界を証明した。
• 参考スコア（独自算出の注目度）: 5.700173588723832
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale, we study the problem of triangle cut sparsification, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate quantum algorithms for this problem, using triangle listing as our main technical ingredient. In particular, we present a quantum algorithm for triangle listing that, for a graph with $n$ vertices, $m$ edges, and $t$ triangles, runs in time $T_{\mathrm{q\text{-}list}} =$ $\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},$ $n^{3/2}t^{1/2})\bigr)$, improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy-light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing $\varepsilon$-triangle cut sparsifiers of size $\widetilde{O}(n/\varepsilon^2)$ in time $\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)$. Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of $Ω(n/\varepsilon^2)$ on the size of any $\varepsilon$-triangle cut sparsifiers.
• Abstract（参考訳）: 三角形はグラフの高次構造を捉え、クラスタリングやネットワーク解析などのアプリケーションに基本となる。 このような構造を大規模に効果的に活用するために,各切断の三角形数を概ね保存しつつ,グラフサイズを小さくすることを目的とした三角形切断スペーシフィケーションの問題について検討した。 本稿では,この問題に対する量子アルゴリズムを,主成分として三角形リストを用いて検討する。 特に、$n$の頂点、$m$の辺、$t$の三角形を持つグラフの場合、時間で$T_{\mathrm{q\text{-}list}} =$$\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},$ $n^{3/2}t^{1/2})\bigr)$ が成り立つ。 本アルゴリズムは、重軽めの頂点分割と、量子ウォークとグロバー探索による三角形検出の拡張に基づく。 この結果を利用して、$\widetilde{O}(n/\varepsilon^2)$ in time $\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)$を構成する量子アルゴリズムを設計する。 最後に、三角関係測度に基づくクラスタリングアルゴリズムの応用を実証し、任意の$\varepsilon$-三角形カットスペーサーのサイズで$Ω(n/\varepsilon^2)$の低い境界を証明した。

関連論文リスト

• Quantum search algorithm for similar subgraph identification under fixed edge removal [2.1098915638533446]
  ラプラシアン $boldsymbolB'$ の重み付き参照グラフが与えられた場合、このアルゴリズムは同じ集合上のラプラシアン $boldsymbolB'$ を特徴付ける部分グラフを決定する。 本稿では,電力グリッドを表す標準的なテストケースに対する本手法の適用例を示す。
  論文  参考訳（メタデータ） (2026-04-02T13:34:42Z)
• Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs [2.9123921488295768]
  そこで本稿では,デジェネリティーに縛られた入力グラフに対して,局所的な差分プライバシーの下でサイクル数をカウントするアルゴリズムを提案する。 我々のアルゴリズムは、退化性有界グラフに対して、$O(d_max0.5 n0.5) = O(n)$の予測$ell$-errorを達成する。
  論文  参考訳（メタデータ） (2024-09-25T07:23:58Z)
• Quantum Algorithms and Lower Bounds for Finite-Sum Optimization [22.076317220348145]
  我々は、複雑性 $tildeObig(n+sqrtd+sqrtell/mubig)$ の量子アルゴリズムを与え、古典的なタイト境界 $tildeThetabig(n+sqrtnell/mubig)$ を改善する。 また、$d$が十分大きいとき、量子下界$tildeOmega(n+n3/4(ell/mu)1/4)$を証明します。
  論文  参考訳（メタデータ） (2024-06-05T07:13:52Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Quantum machine learning with subspace states [8.22379888383833]
  量子部分空間状態に基づく量子線型代数の新しいアプローチを導入し,新しい3つの量子機械学習アルゴリズムを提案する。 1つ目は、分布 $Pr[S]= det(X_SX_ST)$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(dlog n)$である。 2つ目は、複素行列に対して$mathcalAk$の量子特異値推定アルゴリズムであり、このアルゴリズムの高速化は指数関数的である。
  論文  参考訳（メタデータ） (2022-01-31T19:34:47Z)
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
  グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。 この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-10-29T07:35:46Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)

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

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