English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We show that quantum graph parameters for finite, simple, undirected graphsencode winning strategies for all possible synchronous non-local games. Given asynchronous game $\mathcal{G}=(I,O,\lambda)$ with $|I|=n$ and $|O|=k$, wedemonstrate what we call a weak $*$-equivalence between $\mathcal{G}$ and a$3$-coloring game on a graph with at most $3+n+9n(k-2)+6|\lambda^{-1}(\{0\})|$vertices, strengthening and simplifying work implied by Z. Ji (arXiv:1310.3794)for winning quantum strategies for synchronous non-local games. As anapplication, we obtain a quantum version of L. Lov\'{a}sz's reduction (Proc.4th SE Conf. on Comb., Graph Theory & Computing, 1973) of the $k$-coloringproblem for a graph $G$ with $n$ vertices and $m$ edges to the $3$-coloringproblem for a graph with $3+n+9n(k-2)+6mk$ vertices. Moreover, winningstrategies for a synchronous game $\mathcal{G}$ can be transformed into winningstrategies for an associated graph coloring game, where the strategies exhibitperfect zero knowledge for an honest verifier. We also show that, for ``graphof the game" $X(\mathcal{G})$ associated to $\mathcal{G}$ from A. Atserias etal (J. Comb. Theory Series B, Vol. 136, 2019), the independence number game$\text{Hom}(K_{|I|},\overline{X(\mathcal{G})})$ is hereditarily $*$-equivalentto $\mathcal{G}$, so that the possibility of winning strategies is the same inboth games for all models, except the game algebra. Thus, the quantum versionsof the chromatic number, independence number and clique number encode winningstrategies for all synchronous games in all quantum models.

Universality of graph homomorphism games and the quantum coloring problem