Analyzing pseudotelepathy graph games, we propose a way to build contextuality scenarios exhibiting the quantum supremacy using graph states. We consider the combinatorial structures generating equivalent scenarios. We investigate which scenarios are more multipartite and show that there exists graphs generating scenarios with a linear multipartiteness width.

This is based on a joint work with Peter Hoyer and Simon Perdrix.