Communication complexity is an area of classical computer science which studies how much communication is necessary to solve various distributed computational problems. Quantum information processing can be used to reduce the amount of communication required to carry out some distributed problems. We speak of pseudo-telepathy when it is able to completely eliminate the need for communication. The matching game is the newest member of the family of pseudo-telepathy games. After introducing a general model for pseudo-telepathy games, we focus on the question what the smallest size of inputs is for which the matching game is a pseudo-telepathy game.
A pseudo-telepathy game is a game for two or more players for which there is no classical winning strategy, but there is a winning strategy based on sharing quantum entanglement by the players. Since it is generally very hard to perfectly implement a quantum winning strategy for a pseudo-telepathy game, quantum players are almost certain to make errors even though they use a winning strategy. After introducing a model for pseudo-telepathy games, we investigate the impact of several basic noisy quantum channels on the quantum winning strategy for the Mermin-GHZ game. The question of how strong the noise can be so that quantum players would still be better than classical ones is also dealt with.