Infinite Quantum-Classical Separations

Wednesday, May 14, 2014, 3:30pm – 4:15pm
Presented by Chris Perry
Located in LAK 2.06

How much of an advantage can quantum mechanics give over its classical counterpart? This very much depends on the task and measure under consideration. Take, for example, communication protocols where two players are given inputs x and y respectively and are tasked with evaluating a function f(x,y). Here, the communication complexity measures the amount of communication they need to exchange in order to achieve their goal and sending qubits rather than bits provides at best an exponential separation.

In this talk we introduce a two player game motivated by the argument of Pusey, Barrett and Rudolph against $\psi$-epistemic ontological models. With respect to two measures, the amount of information a player must reveal about their input and the communication complexity with or without entanglement, we find that here quantum strategies can drastically outperform classical ones.