Speaker: Graeme Smith, IBM TJ Watson Research Center
Abstract: Physical information carriers obey quantum laws. Taking proper account of this fact has led over the past few decades to profound generalizations of both communication and computation theory. I first give an overview of the quantum theory of communication, which retains many features from Shannon's classical theory but is substantially richer, involving new concepts such as entanglement, separate quantum and classical capacities, and new capabilities such as unconditionally secure cryptographic key agreement, classically impossible kinds of synergy between independent channels, and the possibility of using entangled codewords to boost classical communication rates. Next I discuss the race to build a quantum computer, and the associated problem of characterizing and certifying the "quantumness" of candidate machines. For machines large enough to be interesting, this amounts to an inference problem based on limited measurements, and also involves questions of a computational complexity. As examples, I consider how to give a legitimate implementation of ShoraEuroTMs algorithm and how to decide whether the D-wave device performs meaningful quantum computation.