論文の概要: Efficient Classical Algorithms for Simulating Gaussian Boson Sampling on Graphs

• arxiv url: http://arxiv.org/abs/2505.02445v1
• Date: Mon, 05 May 2025 08:13:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-06 18:49:35.59884
• Title: Efficient Classical Algorithms for Simulating Gaussian Boson Sampling on Graphs
• Title（参考訳）: グラフ上のガウスボソンサンプリングの効率的な古典的アルゴリズム
• Authors: Yexin Zhang, Shuo Zhou, Xinzhao Wang, Ziruo Wang, Ziyi Yang, Rui Yang, Yecheng Xue, Tongyang Li,
• Abstract要約: 我々は,無向非重み付きグラフ上でGBSをシミュレートするマルコフ連鎖モンテカルロアルゴリズムを提案する。 我々の主な貢献はグラウバー力学の二重ループ変種であり、その定常分布はGBS分布と一致する。 数値計算では,従来の GBS 実験や古典シミュレーションのスケールよりも 256 のグラフ上で実験を行う。
• 参考スコア（独自算出の注目度）: 23.446540440518444
• 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 simulate GBS 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 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 10x. Overall, our approach offers both theoretical guarantees and practical advantages for classical simulations of GBS on graphs.
• Abstract（参考訳）: ガウスボソンサンプリング(英: Gaussian Boson Sampling、GBS)は、量子計算の優位性を示すための有望な候補であり、グラフ関連問題の解法に適用できる。 本研究では,無向非重み付きグラフ上でGBSをシミュレートするマルコフ連鎖モンテカルロアルゴリズムを提案する。 我々の主な貢献はグラウバー力学の二重ループ変種であり、その定常分布はGBS分布と一致する。 さらに、洗練された正準経路論を用いて、高密度グラフに対して多項式時間で混合することが証明される。 数値的には、従来のGBS実験や古典シミュレーションのスケールよりも大きい256頂点のグラフ上で実験を行う。 特に、単一ループと二重ループグラウバーのダイナミクスは、最大Hafnianおよび最も高密度な$k$-subgraph問題に対して、元のランダム探索とシミュレートされたアニーリングアルゴリズムの性能を最大10倍に向上させることを示した。 提案手法は,グラフ上のGBSの古典的シミュレーションにおいて,理論的保証と実用的優位性の両方を提供する。

関連論文リスト

• 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)

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

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