論文の概要: GCS-Q: Quantum Graph Coalition Structure Generation
- arxiv url: http://arxiv.org/abs/2212.11372v1
- Date: Wed, 21 Dec 2022 21:22:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-23 15:23:22.444469
- Title: GCS-Q: Quantum Graph Coalition Structure Generation
- Title（参考訳）: GCS-Q:量子グラフ結合構造生成
- Authors: Supreeth Mysore Venkatesh, Antonio Macaluso, Matthias Klusch
- Abstract要約: 本稿では、連立構造生成における誘導サブグラフゲーム(ISG)のための新しい量子支援ソリューションGCS-Qを提案する。
我々はGCS-Qが、現在最も優れた古典的ソルバを、n2$の順で実行し、予想最悪の近似比が標準ベンチマークデータセットで93%の順で上回っていることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of generating an optimal coalition structure for a given
coalition game of rational agents is to find a partition that maximizes their
social welfare and is known to be NP-hard. This paper proposes GCS-Q, a novel
quantum-supported solution for Induced Subgraph Games (ISGs) in coalition
structure generation. GCS-Q starts by considering the grand coalition as
initial coalition structure and proceeds by iteratively splitting the
coalitions into two nonempty subsets to obtain a coalition structure with a
higher coalition value. In particular, given an $n$-agent ISG, the GCS-Q solves
the optimal split problem $\mathcal{O} (n)$ times using a quantum annealing
device, exploring $\mathcal{O}(2^n)$ partitions at each step. We show that
GCS-Q outperforms the currently best classical solvers with its runtime in the
order of $n^2$ and an expected worst-case approximation ratio of $93\%$ on
standard benchmark datasets.
- Abstract（参考訳）: 合理的エージェントによる所定の連立ゲームのための最適な連立構造を生成する問題は、彼らの社会的福祉を最大化し、NPハードであることが知られている分割を見つけることである。
本稿では、連立構造生成における誘導サブグラフゲーム(ISG)のための新しい量子支援ソリューションGCS-Qを提案する。
GCS-Qは、大連立を初期連立構造として考慮し、連立を2つの空でないサブセットに反復的に分割して、より高い連立価値の連立構造を得る。
特に、$n$-agent ISG が与えられたとき、GCS-Q は量子アニールデバイスを用いて最適な分割問題を $\mathcal{O} (n)$ times で解き、各ステップで $\mathcal{O}(2^n)$パーティションを探索する。
我々はGCS-Qが現在最も優れた古典的ソルバのランタイムを$n^2$で上回り、予想最悪の近似比が標準ベンチマークデータセットで9,3\%であることを示す。
関連論文リスト
- Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
論文 参考訳（メタデータ） (2024-07-22T23:24:03Z) - Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。
既存のGCメソッドは複雑な最適化プロセスに悩まされており、過剰な計算資源を必要とする。
我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。
CGCはより効率的な凝縮プロセスで最先端の性能を達成する。
論文 参考訳（メタデータ） (2024-05-22T14:57:09Z) - Evaluating Ground State Energies of Chemical Systems with Low-Depth
Quantum Circuits and High Accuracy [6.81054341190257]
我々は,Qubit Coupled Cluster (QCC) に基づく拡張型変分量子固有解器 (VQE) アンサッツを開発した。
我々は、IBM KolkataとQuantinuum H1-1の2つの異なる量子ハードウェア上で、拡張QCCアンサッツを評価する。
論文 参考訳（メタデータ） (2024-02-21T17:45:03Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。
一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
論文 参考訳（メタデータ） (2023-11-01T19:51:00Z) - QuACS: Variational Quantum Algorithm for Coalition Structure Generation
in Induced Subgraph Games [0.0]
我々は、ISGにおける結合構造生成のための新しいハイブリッド量子古典アルゴリズムを提案する。
提案アルゴリズムは既存の近似古典解法よりも$mathcalO(n2)$,予測近似比$92%$で優れていることを示す。
量子ビットの数は大幅に少なく、既存の量子解と比較して中規模の問題の実験が可能である。
論文 参考訳（メタデータ） (2023-04-14T16:01:27Z) - BILP-Q: Quantum Coalition Structure Generation [0.0]
我々は、結合構造生成問題(CSGP)を解決するための最初の一般量子アプローチであるBILP-Qを提案する。
実量子アニール(D-Wave)を用いた中規模問題に対するBILP-Qの実行
論文 参考訳（メタデータ） (2022-04-28T22:19:50Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。