論文の概要: Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection

• arxiv url: http://arxiv.org/abs/2510.12774v1
• Date: Tue, 14 Oct 2025 17:51:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-15 19:02:32.431743
• Title: Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
• Title（参考訳）: ガウスボソンサンプリングによる二分極傾斜検出の性能評価
• Authors: Yu-Zhen Janice Chen, Laurent Massoulié, Don Towsley,
• Abstract要約: ガウスボソンサンプリング (GBS) が, 植込み双立問題の解法に有効であるかどうかを考察する。 これは、植木構造が小さいとき、古典的に難しいと広く信じられているグラフ問題である。 本研究は, 植林した斜めの大きさが予想される硬質状態に収まると, ノード重みの自然変動がバイアス信号を支配することを示す。
• 参考スコア（独自算出の注目度）: 16.336658164004657
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We investigate whether Gaussian Boson Sampling (GBS) can provide a computational advantage for solving the planted biclique problem, which is a graph problem widely believed to be classically hard when the planted structure is small. Although GBS has been heuristically and experimentally observed to favor sampling dense subgraphs, its theoretical performance on this classically hard problem remains largely unexplored. We focus on a natural statistic derived from GBS output: the frequency with which a node appears in GBS samples, referred to as the node weight. We rigorously analyze whether this signal is strong enough to distinguish planted biclique nodes from background nodes. Our analysis characterizes the distribution of node weights under GBS and quantifies the bias introduced by the planted structure. The results reveal a sharp limitation: when the planted biclique size falls within the conjectured hard regime, the natural fluctuations in node weights dominate the bias signal, making detection unreliable using simple ranking strategies. These findings provide the first rigorous evidence that planted biclique detection may remain computationally hard even under GBS-based quantum computing, and they motivate further investigation into more advanced GBS-based algorithms or other quantum approaches for this problem.
• Abstract（参考訳）: ガウスボソンサンプリング (GBS) が, 植木構造が小さいとき, 古典的に難しいと広く信じられているグラフ問題である, 植木双立問題の解法に, 計算上の優位性をもたらすかどうかを考察する。 GBSは、高密度な部分グラフのサンプリングを好んで、ヒューリスティックかつ実験的に観察されてきたが、この古典的な難解な問題に対する理論的な性能は、まだ明らかにされていない。 我々は,GBS の出力から導かれる自然統計に注目する:ノードが GBS サンプルに現れる頻度は,ノード重みと呼ばれる。 我々は、この信号が背景ノードと植林された斜交ノードを区別するのに十分な強度であるかどうかを厳密に分析する。 本分析では, GBS 下でのノード重みの分布を特徴付けるとともに, 植木構造がもたらすバイアスを定量化する。 その結果, 植林した斜めの大きさが予想されるハードレジームに収まると, ノード重みの自然変動がバイアス信号を支配し, 単純なランキング戦略による検出が不可能になることがわかった。 これらの発見は、GBSベースの量子コンピューティングの下でも、双斜検出が計算的に難しいままであることを示す最初の厳密な証拠となり、より高度なGBSベースのアルゴリズムや他の量子アプローチに関するさらなる研究を動機付けている。

関連論文リスト

• Quartic quantum speedups for community detection [84.14713515477784]
  我々は,準量子スピードアップを実現するハイパーグラフコミュニティ検出のための量子アルゴリズムを開発した。 提案アルゴリズムは,従来検討されていた PCA や $p$XORSAT といった問題を超えて拡張した Kikuchi 法に基づいている。
  論文  参考訳（メタデータ） (2025-10-09T17:35:17Z)
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs [31.937752933240674]
  我々はマルコフ連鎖モンテカルロに基づくアルゴリズムを提案し、無向非重み付きグラフ上のGBS分布をサンプリングする。 我々の主な貢献はグラウバー力学の二重ループ変種であり、その定常分布はGBS分布と一致する。 提案手法は,非重み付きグラフ上のGBS分布からの効率的な古典的サンプリングのための理論的保証と実用的優位性の両方を提供する。
  論文  参考訳（メタデータ） (2025-05-05T08:13:57Z)
• Gaussian boson sampling validation via detector binning [0.0]
  本稿では,GBS実験を統計的に検証するに適した量として,双対検出器の確率分布を提案する。 それぞれの特性関数との接続を利用して,そのような分布の計算方法を示す。 また、すべての可能な干渉ネットワーク上でHaar平均化を行うとき、双対検出器の確率分布がどのように振る舞うかを示す。
  論文  参考訳（メタデータ） (2023-10-27T12:55:52Z)
• DynGFN: Towards Bayesian Inference of Gene Regulatory Networks with GFlowNets [81.75973217676986]
  遺伝子調節ネットワーク(GRN)は、遺伝子発現と細胞機能を制御する遺伝子とその産物間の相互作用を記述する。 既存の方法は、チャレンジ(1)、ダイナミックスから循環構造を識別すること、あるいはチャレンジ(2)、DAGよりも複雑なベイズ後部を学習することに焦点を当てるが、両方ではない。 本稿では、RNAベロシティ技術を用いて遺伝子発現の「速度」を推定できるという事実を活用し、両方の課題に対処するアプローチを開発する。
  論文  参考訳（メタデータ） (2023-02-08T16:36:40Z)
• Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
  ノイズの多い中間スケールの量子コンピュータを用いてグラフ問題を解く。 我々は,大きな光子クリック数を持つGBS増幅の存在と,特定の雑音下での強化を実験的に観察した。 我々の研究は、既存の中間スケール量子コンピュータを用いて現実の問題をテストするためのステップである。
  論文  参考訳（メタデータ） (2023-02-02T08:25:47Z)
• Gaussian-boson-sampling-enhanced dense subgraph finding shows limited advantage over efficient classical algorithms [0.0]
  本研究では,高密度サブグラフ探索アルゴリズムに適用したGBSに対する損失やスペクトル不純物を含む誤差源の影響について検討する。 これらのアルゴリズムの有効性は誤りに対して極めて堅牢であり、基礎となるGBSをシミュレートできる効率的な古典的アルゴリズムが存在することが判明した。
  論文  参考訳（メタデータ） (2023-01-30T19:00:03Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding [101.35070661471124]
  本研究では,観測データ分布に特徴的フットプリントが残っており,突発的・因果的影響を解消できることを示す。 汎用ソルバで実装し,高次元問題へのスケールアップが可能なスコアベース因果検出アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-28T11:07:59Z)

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

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