論文の概要: 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 Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。
現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。
本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
論文 参考訳（メタデータ） (2024-10-29T07:24:11Z) - Quantum Speedup for the Quadratic Assignment Problem [6.106029308649016]
そこで我々は,Dicke状態演算子を用いたGrover Adaptive Search (GAS)を用いて,二次代入問題の探索空間を小さくすることができることを示す。
また、GASの位相ゲートをZ軸の回転ゲートに置き換えることで、ペナルティを伴わずに量子回路を簡素化できることを示す。
論文 参考訳（メタデータ） (2024-10-16T03:00:37Z) - Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
論文 参考訳（メタデータ） (2024-07-22T23:24:03Z) - 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) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - 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) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。