This presentation will discuss the use of the resource of quantum entanglement in communication complexity, focusing, in particular, on whether the type of shared entangled state used can affect the communication complexity of a function. I will present joint work with Aram Harrow, in which we prove that the bounded-error entanglement-assisted communication complexity of a function cannot be improved by more than a constant factor by replacing the resource of maximally entangled states with the greater resource of arbitrary entangled states. This conclusion is opposite of the common wisdom in the study of non-local games. I will explain the relevance of this result to the possibility of proving an analog of Newman's Theorem for the resource of shared entanglement in communication complexity rather than for shared randomness. The extent to which quantum entanglement impacts established complexity measures can be a valuable litmus test used to seek out computational problems which may exhibit a quantum advantage. As a further example of this, time permitting, I will overview joint work with Jalex Stark and Thomas Vidick on improving separations at constant-depth between quantum and classical circuits.
Matthew Coudron is a postdoctoral researcher at the Institute for Quantum Computing. He received his PhD in Computer Science at MIT, where he was advised by Peter Shor. His research focuses on Quantum Algorithms and Complexity as well as verifying the behavior of quantum devices. Of particular interest is the task of identifying computational problems for which quantum algorithms, suitable to near-term quantum hardware, can significantly outperform the classical state-of-the-art.