Quantum Communication Complexity

Published: August 31, 2014   |   Read time:


I was a research assistant in Dr. Joseph Emerson’s lab at the Institute for Quantum Computing. At the time, Dr. Emerson was very interested in differences between classical and quantum systems in order to get at the heart of what really makes quantum mechanics “quantum”. For my 4 month research term, I focused on problems relating to quantum communication protocols, their associated information complexity, and how they related to bounds set by classical communication systems.

These types of problems are typically phrased in the form of a game (a theme commonly presented in mathematical and computer science problems to get at their key ideas), but the difference here is that we can design algorithms that take advantage of quantum teleportation.

The main problems I looked at in those few months were two main variants of problems presented by Raz in 19991.

A summary of my work can be seen in the report, below, that I wrote for the school for that work term2. You can also find the associated code for this project on GitHub3.

References & Footnotes