  Problems based on the structure of graphs -- for example finding cliques,
independent sets, or colourings -- are of fundamental importance in classical
complexity. It is well motivated to consider similar problems about quantum
graphs, which are an operator system generalisation of graphs. Defining
well-formulated decision problems for quantum graphs faces several technical
challenges, and consequently the connections between quantum graphs and
complexity have been underexplored.
  In this work, we introduce and study the clique problem for quantum graphs.
Our approach utilizes a well-known connection between quantum graphs and
quantum channels. The inputs for our problems are presented as quantum channels
induced by circuits, which implicitly determine a corresponding quantum graph.
We also use this approach to reimagine the clique and independent set problems
for classical graphs, by taking the inputs to be circuits of deterministic or
noisy channels which implicitly determine confusability graphs. We show that,
by varying the collection of channels in the language, these give rise to
complete problems for the classes $\textsf{NP}$, $\textsf{MA}$, $\textsf{QMA}$,
and $\textsf{QMA}(2)$. In this way, we exhibit a classical complexity problem
whose natural quantisation is $\textsf{QMA}(2)$, rather than $\textsf{QMA}$,
which is commonly assumed.
  To prove the results in the quantum case, we make use of methods inspired by
self-testing. To illustrate the utility of our techniques, we include a new
proof of the reduction of $\textsf{QMA}(k)$ to $\textsf{QMA}(2)$ via cliques
for quantum graphs. We also study the complexity of a version of the
independent set problem for quantum graphs, and provide preliminary evidence
that it may be in general weaker in complexity, contrasting to the classical
case where the clique and independent set problems are equivalent.
