Institute for Quantum Computing, Waterloo
4pm Monday, 20th of April, 2009
Room 4.31/4.33, Informatics Forum
The locker puzzle is a game played by multiple players against a referee. It has been previously shown that the best strategy that exists cannot succeed with probability greater than 0.31, no matter how many players are involved. Our contribution is to show that quantum players can do much better--they can succeed with probability 1. By making the rules of the game significantly stricter, we show a scenario where the quantum players still succeed perfectly, while the classical players win with vanishing probability. Other variants of the locker puzzle are considered, as well as a cheating referee.
Based on joint work with David Avis.