論文の概要: QuACS: Variational Quantum Algorithm for Coalition Structure Generation
in Induced Subgraph Games
- arxiv url: http://arxiv.org/abs/2304.07218v1
- Date: Fri, 14 Apr 2023 16:01:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-17 13:10:29.845386
- Title: QuACS: Variational Quantum Algorithm for Coalition Structure Generation
in Induced Subgraph Games
- Title（参考訳）: quacs:変分量子アルゴリズムによるサブグラフゲームにおける連立構造生成
- Authors: Supreeth Mysore Venkatesh, Antonio Macaluso, Matthias Klusch
- Abstract要約: 我々は、ISGにおける結合構造生成のための新しいハイブリッド量子古典アルゴリズムを提案する。
提案アルゴリズムは既存の近似古典解法よりも$mathcalO(n2)$,予測近似比$92%$で優れていることを示す。
量子ビットの数は大幅に少なく、既存の量子解と比較して中規模の問題の実験が可能である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Coalition Structure Generation (CSG) is an NP-Hard problem in which agents
are partitioned into mutually exclusive groups to maximize their social
welfare. In this work, we propose QuACS, a novel hybrid quantum classical
algorithm for Coalition Structure Generation in Induced Subgraph Games (ISGs).
Starting from a coalition structure where all the agents belong to a single
coalition, QuACS recursively identifies the optimal partition into two disjoint
subsets. This problem is reformulated as a QUBO and then solved using QAOA.
Given an $n$-agent ISG, we show that the proposed algorithm outperforms
existing approximate classical solvers with a runtime of $\mathcal{O}(n^2)$ and
an expected approximation ratio of $92\%$. Furthermore, it requires a
significantly lower number of qubits and allows experiments on medium-sized
problems compared to existing quantum solutions. To show the effectiveness of
QuACS we perform experiments on standard benchmark datasets using quantum
simulation.
- Abstract（参考訳）: CSG(Coalition Structure Generation)はNP-Hardの問題であり、エージェントは相互排他的なグループに分けられ、社会的福祉を最大化する。
本研究では,誘導部分グラフゲーム(isgs)における結合構造生成のためのハイブリッド量子古典アルゴリズムquacsを提案する。
すべてのエージェントが単一の連立に属する連立構造から始まり、QuACSは最適分割を2つの非結合部分集合に再帰的に特定する。
この問題はQUBOとして再編成され、QAOAを用いて解決される。
n$-agent ISG が与えられた場合、提案アルゴリズムは既存の近似古典的解法よりも$\mathcal{O}(n^2)$ と 92\%$ の近似比が優れていることを示す。
さらに、量子ビットの数が大幅に少なくなり、既存の量子解と比較して中規模の問題の実験が可能である。
QuACSの有効性を示すために、量子シミュレーションを用いて標準ベンチマークデータセットで実験を行う。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳（メタデータ） (2025-02-14T15:21:27Z) - A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Quantum Approximate Optimisation Applied to Graph Similarity [0.0]
本稿では,QAOAのすべての構成成分の探索を容易にする新しい量子最適化シミュレーションパッケージを提案する。
6段階の分解レベルで8つの古典的最適化手法について検討する。
QAOAとエッジの重複によるグラフ類似性のような置換に基づく問題の符号化は、量子メモリの大幅な節約を可能にする。
論文 参考訳（メタデータ） (2024-12-23T06:04:08Z) - Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
論文 参考訳（メタデータ） (2024-07-22T23:24:03Z) - Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。
IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - GCS-Q: Quantum Graph Coalition Structure Generation [0.0]
本稿では、連立構造生成における誘導サブグラフゲーム(ISG)のための新しい量子支援ソリューションGCS-Qを提案する。
我々はGCS-Qが、現在最も優れた古典的ソルバを、n2$の順で実行し、予想最悪の近似比が標準ベンチマークデータセットで93%の順で上回っていることを示す。
論文 参考訳（メタデータ） (2022-12-21T21:22:06Z) - BILP-Q: Quantum Coalition Structure Generation [0.0]
我々は、結合構造生成問題(CSGP)を解決するための最初の一般量子アプローチであるBILP-Qを提案する。
実量子アニール(D-Wave)を用いた中規模問題に対するBILP-Qの実行
論文 参考訳（メタデータ） (2022-04-28T22:19:50Z) - Adaptive shot allocation for fast convergence in variational quantum
algorithms [0.0]
本稿では,gCANS法 (Global Coupled Adaptive Number of Shots) と呼ばれる,各ステップに適応するショット数を用いた勾配降下法を提案する。
これらの改善により、現在のクラウドプラットフォーム上でVQAを実行するのに必要な時間と費用が削減される。
論文 参考訳（メタデータ） (2021-08-23T22:29:44Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳（メタデータ） (2021-06-30T18:32:46Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。