論文の概要: Quantum Speedup for Hypergraph Sparsification

• arxiv url: http://arxiv.org/abs/2505.01763v1
• Date: Sat, 03 May 2025 09:33:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-06 18:49:35.260127
• Title: Quantum Speedup for Hypergraph Sparsification
• Title（参考訳）: ハイパーグラフスカラー化のための量子スピードアップ
• Authors: Chenghua Liu, Minbo Gao, Zhengfeng Ji, Mingsheng Ying,
• Abstract要約: Apers and de Wolf(FOCS'20)によるオープン問題に対処する,ハイパーグラフスカラー化のための最初の量子アルゴリズムを提案する。 n$頂点、$m$ハイパーエッジ、およびランク$r$の重み付きハイパーグラフに対して、我々のアルゴリズムは、時間$widetilde O(rsqrtmn/varepsilon)$で、ほぼ直線サイズの$varepsilon$-spectral sparsifierを出力する。 このアルゴリズムは定数$r$の量子ローバウンドと一致し、状態と比較した場合の量子スピードアップを示す。
• 参考スコア（独自算出の注目度）: 3.5293335880819483
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hypergraph sparsification has recently gained increasing attention, with broad applications in graph machine learning and other areas. In this work, we propose the first quantum algorithm for hypergraph sparsification, addressing an open problem proposed by Apers and de Wolf (FOCS'20). For a weighted hypergraph with $n$ vertices, $m$ hyperedges, and rank $r$, our algorithm outputs a near-linear size $\varepsilon$-spectral sparsifier in time $\widetilde O(r\sqrt{mn}/\varepsilon)$. This algorithm matches the quantum lower bound for constant $r$ and demonstrates quantum speedup when compared with the state-of-the-art $\widetilde O(mr)$-time classical algorithm. As applications, our algorithm implies quantum speedups for computing hypergraph cut sparsifiers, approximating hypergraph mincuts and hypergraph $s$-$t$ mincuts.
• Abstract（参考訳）: グラフスカラー化は、グラフカットの近似アルゴリズムやラプラシア系の解法など、多くのアルゴリズムの基礎となっている。 グラフの自然な一般化に伴い、ハイパーグラフのスパーシフィケーションは近年注目され、グラフ機械学習やその他の分野にも広く応用されている。 本研究では,Apers and de Wolf (FOCS'20) が提案するオープンな問題に対処する,ハイパーグラフスカラー化のための最初の量子アルゴリズムを提案する。 n$Vertices, $m$hyperedges, rank $r$の重み付きハイパーグラフの場合、我々のアルゴリズムは、ほぼ直線サイズの$\varepsilon$-spectral sparsifier in time $\widetilde O(r\sqrt{mn}/\varepsilon$を出力する。 このアルゴリズムは定数$r$の量子ローバウンドと一致し、最先端の$\widetilde O(mr)$-timeの古典的アルゴリズムと比較して量子スピードアップを示す。 応用として、ハイパーグラフカットスペーサーの計算、ハイパーグラフミンカットの近似、ハイパーグラフ$s$-$t$ミンカットの量子スピードアップを提案する。

関連論文リスト

• Quantum Speedup for Sampling Random Spanning Trees [2.356162747014486]
  我々は、$widetildeO(sqrtmn)$ timeの重み付きグラフからランダムスパンニング木をサンプリングする量子アルゴリズムを提案する。 我々のアルゴリズムは、高密度グラフのサブ線形ランタイムを持ち、よく知られた古典的アルゴリズムの量子スピードアップを実現する。
  論文  参考訳（メタデータ） (2025-04-22T05:45:04Z)
• Quantum algorithms for hypergraph simplex finding [0.0]
  ハイパーグラフへの三角形探索の一般化である, 単純度探索のための量子クエリアルゴリズムについて検討する。 この問題は階数還元性を満たす:ランク-r$ハイパーグラフの単純さを見つける量子クエリアルゴリズムは、ランク-(r-1)$ハイパーグラフの単純さを見つけるためのより高速なアルゴリズムに変換できる。
  論文  参考訳（メタデータ） (2024-08-30T20:12:45Z)
• Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
  Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。 この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
  論文  参考訳（メタデータ） (2023-12-05T21:15:09Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving [1.0660480034605238]
  スペクトルスペーシフィケーション」は、ノード数でエッジの数をほぼ直線に減らす。 スペクトルスカラー化のための量子スピードアップとその多くの応用について述べる。 我々のアルゴリズムはラプラシア系を解くための量子スピードアップを意味する。
  論文  参考訳（メタデータ） (2019-11-17T17:29:40Z)

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

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