論文の概要: Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs

• arxiv url: http://arxiv.org/abs/2505.02445v2
• Date: Wed, 17 Sep 2025 14:26:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-18 14:28:51.694548
• Title: Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• Title（参考訳）: 非重み付きグラフ上のガウスボソンサンプリング分布からの効率的な古典サンプリング
• Authors: Yexin Zhang, Shuo Zhou, Xinzhao Wang, Ziruo Wang, Ziyi Yang, Rui Yang, Yecheng Xue, Tongyang Li,
• Abstract要約: 我々はマルコフ連鎖モンテカルロに基づくアルゴリズムを提案し、無向非重み付きグラフ上のGBS分布をサンプリングする。 我々の主な貢献はグラウバー力学の二重ループ変種であり、その定常分布はGBS分布と一致する。 提案手法は,非重み付きグラフ上のGBS分布からの効率的な古典的サンプリングのための理論的保証と実用的優位性の両方を提供する。
• 参考スコア（独自算出の注目度）: 31.937752933240674
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gaussian Boson Sampling (GBS) is a promising candidate for demonstrating quantum computational advantage and can be applied to solving graph-related problems. In this work, we propose Markov chain Monte Carlo-based algorithms to sample from GBS distributions on undirected, unweighted graphs. Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution. We further prove that it mixes in polynomial time for dense graphs using a refined canonical path argument. Numerically, we conduct experiments on unweighted graphs with 256 vertices, larger than the scales in former GBS experiments as well as classical simulations. In particular, we show that both the single-loop and double-loop Glauber dynamics improve the performance of original random search and simulated annealing algorithms for the max-Hafnian and densest $k$-subgraph problems up to 10$\times$. Overall, our approach offers both theoretical guarantees and practical advantages for efficient classical sampling from GBS distributions on unweighted graphs.
• Abstract（参考訳）: ガウスボソンサンプリング(英: Gaussian Boson Sampling、GBS)は、量子計算の優位性を示すための有望な候補であり、グラフ関連問題の解法に適用できる。 本研究では,無向非重み付きグラフ上のGBS分布をサンプリングするマルコフ連鎖モンテカルロアルゴリズムを提案する。 我々の主な貢献はグラウバー力学の二重ループ変種であり、その定常分布はGBS分布と一致する。 さらに、洗練された正準経路論を用いて、高密度グラフに対して多項式時間で混合することが証明される。 数値的には、従来のGBS実験や古典シミュレーションのスケールよりも大きい256頂点の非重み付きグラフ上で実験を行う。 特に、単一ループと二重ループグラウバーのダイナミクスは、最大Hafnianおよび最も高密度な$k$-subgraph問題に対して、元のランダム探索と擬似アニーリングアルゴリズムの性能を最大10$\times$まで向上させることを示した。 全体として、本手法は、非重み付きグラフ上のGBS分布からの効率的な古典的サンプリングのための理論的保証と実用的優位性の両方を提供する。

関連論文リスト

• Gauging practical computational advantage using a classical, threshold-based Gaussian boson sampler [0.10923877073891444]
  量子光の古典的な記述と単光子検出器の決定論的モデルに基づいて,効率よくスケーラブルなガウスボソンサンプリングを行う。 NP-Compeグラフ理論問題を等価なガウスボソンサンプリング問題にマッピングし,本手法の有効性を数値的に検討する。
  論文  参考訳（メタデータ） (2025-07-23T14:58:18Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  この研究はMRGNN(Multi resolution Reservoir Graph Neural Network)における貯留層の定義を再考する。 コンピュータグラフィックスにおける表面設計の分野で最初に導入されたフェアリングアルゴリズムに基づく変種を提案する。 この論文の中核的な貢献は、ランダムウォークの観点からのアルゴリズムの理論解析にある。
  論文  参考訳（メタデータ） (2025-07-17T10:02:57Z)
• Gaussian boson sampling for binary optimization [0.0]
  本稿では,2値最適化問題に対処するために,しきい値検出器を備えたパラメトリゼーションガウスボソンサンプリング(GBS)を提案する。 3SATおよびグラフ問題に関する数値実験は、ランダムな推測よりも顕著な性能向上を示した。
  論文  参考訳（メタデータ） (2024-12-19T12:12:22Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGGSDを提案する。 合成グラフと実世界のグラフの両方に関する広範な実験は、最先端の代替品に対する我々のモデルの強みを実証している。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph Classification [0.9935277311162707]
  2つのグラフが互いに小さいかどうかを決定するNP完全問題に対するハイブリッド量子古典アルゴリズムを提案する。 ワンショット分類精度と入力スクイーズ量とのトレーディングが可能なグラフ埋め込みを見つける。 本稿では,グラフスペクトルに基づく新しい古典的アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-05T21:24:11Z)
• Boost clustering with Gaussian Boson Sampling: a full quantum approach [0.09437521840642138]
  ガウスボソンサンプリング(GBS)に基づく新しいクラスタリング手法を提案する。 2つの有名な古典的クラスタリングアルゴリズムを用いて、我々のアプローチをベンチマークする。 その結果,提案手法は,選択した3つの指標のうち2つにおいて,従来の2つのアルゴリズムよりも優れていた。
  論文  参考訳（メタデータ） (2023-07-25T09:05:24Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling [2.5496329090462626]
  グラフ理論問題に応用可能な量子インスピレーション付き古典アルゴリズムを提案する。 ガウスボソンサンプリング器で符号化されるグラフの隣接行列は非負であり、量子干渉を必要としない。
  論文  参考訳（メタデータ） (2023-02-01T16:02:31Z)
• NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
  2つの重要な要素に依存した、新しく、堅牢で、加速された反復を提案する。 NAG-GSと呼ばれる手法の収束と安定性は、まず広範に研究されている。 我々は、NAG-arityが、重量減衰を伴う運動量SGDや機械学習モデルのトレーニングのためのAdamWといった最先端の手法と競合していることを示す。
  論文  参考訳（メタデータ） (2022-09-29T16:54:53Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。 我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。 数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2020-11-18T16:40:45Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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