論文の概要: Towards a Hybrid Quantum Enhanced Solution for Densest k-Subgraph Problem

• arxiv url: http://arxiv.org/abs/2606.03196v1
• Date: Tue, 02 Jun 2026 05:55:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-03 22:00:04.789452
• Title: Towards a Hybrid Quantum Enhanced Solution for Densest k-Subgraph Problem
• Title（参考訳）: 密度k-サブグラフ問題に対するハイブリッド量子拡張解を目指して
• Authors: Ravi Sangwan, Prabhat Anand, M Girish Chandra,
• Abstract要約: ガウスボソンサンプリング(GBS)の高密度k-グラフ問題(DkSP)への応用について検討する。 提案手法では, ほぼkに近いサンプルを, 実現可能なソリューションに変換し, 破棄する, 有効な古典的後処理戦略を導入する。
• 参考スコア（独自算出の注目度）: 0.6649512409446104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the application of Gaussian Boson Sampling (GBS) to the densest k-subgraph problem (DkSP). GBS with hard post-selection suffers from poor sampling efficiency due to strict cardinality constraints. To address this limitation, we introduce effective classical post-processing strategies that transform, otherwise discarded, near-k samples into feasible solutions. A comprehensive set of simulations is carried out, demonstrating that these approaches achieve near-optimal solution quality while improving sampling efficiency by approximately 4X compared to post-selection on community-structured graphs, and also post-selection often fails to reach the optimal solution on sparse random graphs even with large number of samples. Furthermore, the proposed methods perform on par with, and in some cases outperform, established classical approaches for graphs up to moderate size. Overall, the results indicate that while GBS with post-selection alone is insufficient, its combination with lightweight classical refinement can be highly effective. This underscores the potential of hybrid quantum-classical frameworks and positions GBS as a promising sampling primitive for combinatorial graph optimization.
• Abstract（参考訳）: ガウスボソンサンプリング(GBS)の高密度k-グラフ問題(DkSP)への応用について検討する。 選択後の厳しいGBSは、厳格な濃度制約のためにサンプリング効率の低下に悩まされる。 この制限に対処するため、我々は従来のポストプロセッシング戦略を効果的に導入し、それ以外は捨てられ、ほぼkに近いサンプルを実現可能なソリューションに変換する。 群集構造グラフのポストセレクションと比較して, サンプリング効率を約4倍改善し, サンプル数が多い場合でも, スパースランダムグラフの最適解に到達できない場合が多い。 さらに、提案手法は同等に動作し、場合によっては、適度な大きさのグラフに対して古典的なアプローチを確立した。 以上の結果から,選択後のみのGBSは不十分であるが,軽量な古典リファインメントとの併用は極めて効果的であることが示唆された。 このことは、ハイブリッド量子古典フレームワークの可能性を強調し、組合せグラフ最適化のための有望なサンプリングプリミティブとしてGBSを位置づけている。

関連論文リスト

• A Quantum Photonic Approach to Graph Coloring [0.688204255655161]
  ガウスボソンサンプリング(英: Gaussian Boson Sampling、GBS)は、線形光学を利用してサンプリング問題を解決する量子計算モデルである。 最近の実験的ブレークスルーは、GBSを用いた量子優位性を示し、実世界の最適化問題への応用を動機付けている。
  論文  参考訳（メタデータ） (2026-01-28T05:18:27Z)
• Gauging practical computational advantage using a classical, threshold-based Gaussian boson sampler [0.10923877073891444]
  量子光の古典的な記述と単光子検出器の決定論的モデルに基づいて,効率よくスケーラブルなガウスボソンサンプリングを行う。 NP-Compeグラフ理論問題を等価なガウスボソンサンプリング問題にマッピングし,本手法の有効性を数値的に検討する。
  論文  参考訳（メタデータ） (2025-07-23T14:58:18Z)
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs [31.937752933240674]
  我々はマルコフ連鎖モンテカルロに基づくアルゴリズムを提案し、無向非重み付きグラフ上のGBS分布をサンプリングする。 我々の主な貢献はグラウバー力学の二重ループ変種であり、その定常分布はGBS分布と一致する。 提案手法は,非重み付きグラフ上のGBS分布からの効率的な古典的サンプリングのための理論的保証と実用的優位性の両方を提供する。
  論文  参考訳（メタデータ） (2025-05-05T08:13:57Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Proximal Oracles for Optimization and Sampling [18.77973093341588]
  非滑らかな目的関数による凸最適化と非滑らかなポテンシャルによる対数凹型サンプリングについて検討する。 非滑らか性による課題を克服するため、アルゴリズムは最適化とサンプリングに2つの強力な近位フレームワークを用いる。
  論文  参考訳（メタデータ） (2024-04-02T18:52:28Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
  Bin Packing Problem (BPP) は、ロジスティクスにおけるパラダイム最適化問題として際立っている。 我々は最近,一次元BPPに対するハイブリッドアプローチを提案している。 他の古典的手法と比較する。
  論文  参考訳（メタデータ） (2022-07-15T13:09:12Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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