  Information-processing tasks modelled by homomorphisms between relational
structures can witness quantum advantage when entanglement is used as a
computational resource. We prove that the occurrence of quantum advantage is
determined by the same type of algebraic structure (known as a minion) that
captures the polymorphism identities of CSPs and, thus, CSP complexity. We
investigate the connection between the minion of quantum advantage and other
known minions controlling CSP tractability and width. In this way, we make use
of complexity results from the algebraic theory of CSPs to characterise the
occurrence of quantum advantage in the case of graphs, and to obtain new
necessary and sufficient conditions in the case of arbitrary relational
structures.
