  We study quantum versions of the Shannon capacity of graphs and
non-commutative graphs. We introduce the asymptotic spectrum of graphs with
respect to quantum and entanglement-assisted homomorphisms, and we introduce
the asymptotic spectrum of non-commutative graphs with respect to
entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J.
Reine Angew. Math., 1988) in order to obtain dual characterizations of the
corresponding Shannon capacities and asymptotic preorders in terms of their
asymptotic spectra. This work extends the study of the asymptotic spectrum of
graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain.
  We then exhibit spectral points in the new quantum asymptotic spectra and
discuss their relations with the asymptotic spectrum of graphs. In particular,
we prove that the (fractional) real and complex Haemers bounds upper bound the
quantum Shannon capacity, which is defined as the regularization of the quantum
independence number (Man\v{c}inska and Roberson, J. Combin. Theory Ser. B,
2016), and that the fractional real and complex Haemers bounds are elements in
the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers
bounds defined over certain finite fields, which can be strictly smaller than
the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly
smaller than the Lov\'asz theta function (Haemers, IEEE Trans. Inf. Theory,
1979), we find that the quantum Shannon capacity and the Lov\'asz theta
function do not coincide. As a consequence, two well-known conjectures in
quantum information theory cannot both be true.
