論文の概要: Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs
- arxiv url: http://arxiv.org/abs/2606.28775v1
- Date: Sat, 27 Jun 2026 06:59:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-30 18:07:15.68495
- Title: Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs
- Title（参考訳）: 有向グラフにおけるハミルトニアンサイクルに対するバイパルタイトガウスボソンサンプリング
- Abstract要約: 有向グラフ最適化のためのBipartiteGBSベースのフレームワークを提案する。
我々は、有名なハミルトンサイクル問題に対する遺伝的アルゴリズムを誘導するために、BipartiteGBSサンプルを使用する。
- 参考スコア（独自算出の注目度）: 11.39278258068721
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bipartite Gaussian boson sampling (BipartiteGBS) produces output probabilities governed by squared permanents of submatrices of arbitrary complex matrices, matching the nonsymmetric structure of directed graphs. Most GBS-based graph algorithms, however, rely on symmetric hafnian structure and are formulated for undirected problems. Here we propose a BipartiteGBS-based framework for directed-graph heuristic optimization. We introduce Max-Perm as a canonical optimization task for BipartiteGBS and derive a closed-form sampling enhancement factor relative to uniform classical sampling in this idealized setting. We then use permanent-biased BipartiteGBS samples to guide a genetic algorithm for the celebrated directed Hamiltonian cycle problem. Numerical experiments on Erdős--Rényi random directed graphs show that the resulting BipartiteGBS-enhanced algorithms improve success rates over a standard genetic algorithm and yield longer valid paths when no Hamiltonian cycle is found, while ablation tests indicate that BipartiteGBS-guided initialization is the dominant contributor. These results show how permanent-based photonic sampling can provide useful algorithmic guidance for asymmetric combinatorial search.
- Abstract（参考訳）: Bipartite Gaussian boson sample (BipartiteGBS) は任意の複素行列の部分行列の正方行列によって支配される出力確率を生成し、有向グラフの非対称構造と一致する。
しかし、ほとんどのGBSベースのグラフアルゴリズムは対称ハフニアン構造に依存し、無向問題に対して定式化されている。
本稿では、有向グラフヒューリスティック最適化のためのBipartiteGBSベースのフレームワークを提案する。
そこで我々は,BipartiteGBSの標準最適化タスクとしてMax-Permを導入し,この理想化された環境での一様古典サンプリングに対する閉形式サンプリング強化係数を導出する。
次に、永久バイアスのBipartiteGBSサンプルを用いて、ハミルトン周期問題に対する遺伝的アルゴリズムを導出する。
Erdés--Rényiランダム有向グラフの数値実験により、結果として得られるBipartiteGBSによるアルゴリズムは、標準的な遺伝的アルゴリズムよりも成功率を向上し、ハミルトンのサイクルが見つからない場合にはより長い有効経路が得られることが示され、一方アブレーション試験はBipartiteGBS誘導初期化が支配的な寄与であることを示している。
これらの結果は,非対称な組合せ探索において,恒久的なフォトニックサンプリングが有用なアルゴリズム的ガイダンスを提供することを示す。
関連論文リスト
- Bregman geometry-aware split Gibbs sampling for Bayesian Poisson inverse problems [8.115032818930457]
モンテカルロサンプリングアルゴリズムを用いて,逆問題の解法を提案する。
本手法は, 復元品質の点で競争性能が向上することを示す。
論文 参考訳（メタデータ） (2025-11-15T15:27:31Z) - Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs [31.937752933240674]
我々はマルコフ連鎖モンテカルロに基づくアルゴリズムを提案し、無向非重み付きグラフ上のGBS分布をサンプリングする。
我々の主な貢献はグラウバー力学の二重ループ変種であり、その定常分布はGBS分布と一致する。
提案手法は,非重み付きグラフ上のGBS分布からの効率的な古典的サンプリングのための理論的保証と実用的優位性の両方を提供する。
論文 参考訳（メタデータ） (2025-05-05T08:13:57Z) - Gaussian boson sampling for binary optimization [0.0]
本稿では,2値最適化問題に対処するために,しきい値検出器を備えたパラメトリゼーションガウスボソンサンプリング(GBS)を提案する。
3SATおよびグラフ問題に関する数値実験は、ランダムな推測よりも顕著な性能向上を示した。
論文 参考訳（メタデータ） (2024-12-19T12:12:22Z) - A Discrete Particle Swarm Optimizer for the Design of Cryptographic
Boolean Functions [1.6574413179773761]
このアルゴリズムはHu, Eberhart, Shiによる置換PSOの修正版である。
PSO速度方程式のパラメータは2つのメタ最適化手法を用いて調整される。
論文 参考訳（メタデータ） (2024-01-09T14:08:42Z) - Boost clustering with Gaussian Boson Sampling: a full quantum approach [0.09437521840642138]
ガウスボソンサンプリング(GBS)に基づく新しいクラスタリング手法を提案する。
2つの有名な古典的クラスタリングアルゴリズムを用いて、我々のアプローチをベンチマークする。
その結果,提案手法は,選択した3つの指標のうち2つにおいて,従来の2つのアルゴリズムよりも優れていた。
論文 参考訳（メタデータ） (2023-07-25T09:05:24Z) - Accelerated Discovery of Machine-Learned Symmetries: Deriving the
Exceptional Lie Groups G2, F4 and E6 [55.41644538483948]
このレターでは、対称性変換の発見を著しく高速化する2つの改良されたアルゴリズムを紹介している。
例外的リー群の複雑性を考えると,この機械学習手法は完全に汎用的であり,多種多様なラベル付きデータセットに適用可能であることを示す。
論文 参考訳（メタデータ） (2023-07-10T20:25:44Z) - NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
2つの重要な要素に依存した、新しく、堅牢で、加速された反復を提案する。
NAG-GSと呼ばれる手法の収束と安定性は、まず広範に研究されている。
我々は、NAG-arityが、重量減衰を伴う運動量SGDや機械学習モデルのトレーニングのためのAdamWといった最先端の手法と競合していることを示す。
論文 参考訳（メタデータ） (2022-09-29T16:54:53Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Orbital MCMC [82.54438698903775]
任意の微分同相写像から周期軌道を構築するための2つの実用的なアルゴリズムを提案する。
また,両カーネルの実用的メリットを実証した実証的研究を行った。
論文 参考訳（メタデータ） (2020-10-15T22:25:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。