GCS-Q: Quantum Graph Coalition Structure Generation

• URL: http://arxiv.org/abs/2212.11372v1
• Date: Wed, 21 Dec 2022 21:22:06 GMT
• Title: GCS-Q: Quantum Graph Coalition Structure Generation
• Abstract summary: This paper proposes GCS-Q, a novel quantum-supported solution for Induced Subgraph Games (ISGs) in coalition structure generation. We show that GCS-Q outperforms the currently best classical solvers with its runtime in the order of $n2$ and an expected worst-case approximation ratio of $93%$ on standard benchmark datasets.
• Score: 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.

Related papers

• Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations [11.62669179647184]
  We study coalition structure generation (CSG) when coalition values are not given but must be learned from episodic observations.<n>We model each episode as a sparse linear regression problem, where the realised payoff (Y_t) is a noisy linear combination of a small number of coalition contributions.<n>This yields a probabilistic CSG framework in which the planner first estimates a sparse value function from (T) episodes, then runs a CSG solver on the inferred coalition set.
  arXiv  Detail & Related papers  (2026-01-01T12:50:56Z)
• Bayesian Recovery for Probabilistic Coalition Structures [11.62669179647184]
  Probabilistic Coalition Structure Generation (PCSG) is NP-hard and can be recast as an $l_0$-type sparse recovery problem.<n>We show that the answer is negative in a PCSG-inspired regime where overlapping coalitions generate highly coherent, near-duplicate columns.<n>We prove that Sparse Bayesian Learning with a Gaussian-Gamma hierarchy is support consistent under the same structural assumptions.
  arXiv  Detail & Related papers  (2025-12-25T13:03:07Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Quantum-Assisted Correlation Clustering [3.8448698053186843]
  This work introduces a hybrid quantum-classical method to correlation clustering, a graph-based unsupervised learning task.<n>We adapt GCS-Q, a quantum-assisted solver originally designed for coalition structure generation, to maximize intra-cluster agreement in signed graphs.<n> Empirical evaluations on synthetic signed graphs and real-world hyperspectral imaging data demonstrate that, when adapted for correlation clustering, GCS-Q outperforms classical algorithms in robustness and clustering quality.
  arXiv  Detail & Related papers  (2025-09-03T12:14:35Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters. GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
  We present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. Our techniques bring a new way of approaching the problem and a new level of precision to the field.
  arXiv  Detail & Related papers  (2024-07-22T23:24:03Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
  Graph condensation is a data-centric solution to replace the large graph with a small yet informative condensed graph. Existing GC methods suffer from intricate optimization processes, necessitating excessive computing resources. We propose a training-free GC framework termed Class-partitioned Graph Condensation (CGC) CGC achieves state-of-the-art performance with a more efficient condensation process.
  arXiv  Detail & Related papers  (2024-05-22T14:57:09Z)
• Evaluating Ground State Energies of Chemical Systems with Low-Depth Quantum Circuits and High Accuracy [6.81054341190257]
  We develop an enhanced Variational Quantum Eigensolver (VQE) ansatz based on the Qubit Coupled Cluster (QCC) approach. We evaluate our enhanced QCC ansatz on two distinct quantum hardware, IBM Kolkata and Quantinuum H1-1.
  arXiv  Detail & Related papers  (2024-02-21T17:45:03Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  We prove that the recently proposed Quantum Hamiltonian (QHD) algorithm is able to solve any $d$dimensional queries from this family. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical algorithms/solvers would require a superpolynomial time to solve such queries.
  arXiv  Detail & Related papers  (2023-11-01T19:51:00Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability. IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• QuACS: Variational Quantum Algorithm for Coalition Structure Generation in Induced Subgraph Games [0.0]
  We propose a novel hybrid quantum classical algorithm for Coalition Structure Generation in Induced Subgraph Games (ISGs) We show that the proposed algorithm outperforms existing approximate classical solvers with a runtime of $mathcalO(n2)$ and an expected approximation ratio of $92%$. It requires a significantly lower number of qubits and allows experiments on medium-sized problems compared to existing quantum solutions.
  arXiv  Detail & Related papers  (2023-04-14T16:01:27Z)
• BILP-Q: Quantum Coalition Structure Generation [0.0]
  We propose BILP-Q, the first-ever general quantum approach for solving the Coalition Structure Generation problem (CSGP) We run BILP-Q on medium-size problems using a real quantum annealer (D-Wave)
  arXiv  Detail & Related papers  (2022-04-28T22:19:50Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.