Abstract:

Analyzing pseudo-telepathy 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 introduce a new tool called multipartiteness width to investigate which scenarios are hard to decompose and show that there exist graphs generating scenarios with a linear multipartiteness width.