New Approaches to Complexity via Quantum Graphs

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.