Department of
Applied
Mathematics

Some examples of exponential advantage in quantum communication

Dmitry Gavinsky

Abstract

Arguably, the strongest currently known evidences that quantum computers have qualitative superiority over classical computers are exponential separations between quantum and classical communication classes. This talk aims to survey such separations, somewhat categorise them and discuss possible approaches to further research.