Quantum phenomena offer the possibility of more efficient computation in
a host of information processing scenarios. At the same time, their unusual
properties also make it challenging for us to characterize potential gains
in efficiency. In this talk, we will review recent results in a few different
settings: the streaming model, distributed computation, and learning theory.
All of these results are based on the information-theoretic method, which
provides an intuitive approach for understanding highly