  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.
