Capital Area Theory Seminar

The new paradigm of quantum computing makes use of quantum mechanical effects to speed up computation. It has been shown by Shor that factorization of a number M can be done in polynomial time on a quantum computer. In comparison the best known classical algorithms take close to exponential time. Whereas classical computers operate on bits, quantum algorithms make essential use of bits in superposition: qubits.

Qubits can - just as classical bits - be used to code information. A fundamental result in quantum information theory by Kholevo (1973) shows that k qubits can not contain more information than k classical bits. Nevertheless it can be shown that communication via qubits can drastically reduce the communication cost in the setting of communication complexity.

We will give an overview of recent results obtained in this area as well as a short introduction to quantum computing.

Contact: Vincenzo Liberatore (liberato@umiacs.umd.edu)