論文の概要: A Quantum Photonic Approach to Graph Coloring

• arxiv url: http://arxiv.org/abs/2601.20263v1
• Date: Wed, 28 Jan 2026 05:18:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:06.779936
• Title: A Quantum Photonic Approach to Graph Coloring
• Title（参考訳）: グラフカラー化への量子フォトニックアプローチ
• Authors: Jesua Epequin, Pascale Bendotti, Joseph Mikael,
• Abstract要約: ガウスボソンサンプリング(英: Gaussian Boson Sampling、GBS)は、線形光学を利用してサンプリング問題を解決する量子計算モデルである。 最近の実験的ブレークスルーは、GBSを用いた量子優位性を示し、実世界の最適化問題への応用を動機付けている。
• 参考スコア（独自算出の注目度）: 0.688204255655161
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gaussian Boson Sampling (GBS) is a quantum computational model that leverages linear optics to solve sampling problems believed to be classically intractable. Recent experimental breakthroughs have demonstrated quantum advantage using GBS, motivating its application to real-world combinatorial optimization problems. In this work, we reformulate the graph coloring problem as an integer programming problem using the independent set formulation. This enables the use of GBS to identify cliques in the complement graph, which correspond to independent sets in the original graph. Our method is benchmarked against classical heuristics and exact algorithms on two sets of instances: Erdős-Rényi random graphs and graphs derived from a smart-charging use case. The results demonstrate that GBS can provide competitive solutions, highlighting its potential as a quantum-enhanced heuristic for graph-based optimization.
• Abstract（参考訳）: ガウスボソンサンプリング(英: Gaussian Boson Sampling、GBS)は、線形光学を利用する量子計算モデルである。 最近の実験的なブレークスルーは、GBSを用いた量子優位性を示し、実世界の組合せ最適化問題への応用を動機付けている。 本研究では,独立集合の定式化を用いた整数計画問題としてグラフ彩色問題を再構成する。 これにより、GBSを使用して、元のグラフの独立集合に対応する補グラフ内のcliqueを識別できる。 提案手法は,エルデシュ=レーニ・ランダムグラフと,スマートチャージユースケースから導出したグラフの2つの例に対して,古典的ヒューリスティックスと正確なアルゴリズムに対してベンチマークを行う。 その結果、GBSは、グラフベースの最適化のための量子エンハンスなヒューリスティックとしての可能性を強調しながら、競争力のあるソリューションを提供できることを示した。

関連論文リスト

• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  この研究はMRGNN(Multi resolution Reservoir Graph Neural Network)における貯留層の定義を再考する。 コンピュータグラフィックスにおける表面設計の分野で最初に導入されたフェアリングアルゴリズムに基づく変種を提案する。 この論文の中核的な貢献は、ランダムウォークの観点からのアルゴリズムの理論解析にある。
  論文  参考訳（メタデータ） (2025-07-17T10:02:57Z)
• 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)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGGSDを提案する。 合成グラフと実世界のグラフの両方に関する広範な実験は、最先端の代替品に対する我々のモデルの強みを実証している。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
  ノイズの多い中間スケールの量子コンピュータを用いてグラフ問題を解く。 我々は,大きな光子クリック数を持つGBS増幅の存在と,特定の雑音下での強化を実験的に観察した。 我々の研究は、既存の中間スケール量子コンピュータを用いて現実の問題をテストするためのステップである。
  論文  参考訳（メタデータ） (2023-02-02T08:25:47Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。 本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。 今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
  論文  参考訳（メタデータ） (2022-02-19T02:56:47Z)
• Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach [47.19265172105025]
  グラフ構造化データのための新しいハイブリッド量子古典アルゴリズムを提案し、これをEgo-graph based Quantum Graph Neural Network (egoQGNN)と呼ぶ。 egoQGNNはテンソル積とユニティ行列表現を用いてGNN理論フレームワークを実装し、必要なモデルパラメータの数を大幅に削減する。 このアーキテクチャは、現実世界のデータからヒルベルト空間への新しいマッピングに基づいている。
  論文  参考訳（メタデータ） (2022-01-13T16:35:45Z)
• Graph Coloring with Quantum Annealing [0.0]
  そこで我々は,D-Wave 2X を独立セットサンプリングとして用いたグラフカラー化近似アルゴリズムを開発した。 ランダムに生成された小さなグラフインスタンスのセットは、テストセットとして役立ちます。 我々の性能分析は、ハイブリッド量子古典アルゴリズムにおける量子優位性に限界があることを示唆している。
  論文  参考訳（メタデータ） (2020-12-08T15:08:22Z)

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

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