[QIP-Sem] MIT Quantum Information Processing Special Seminar Announcement

[QIP-Sem Mailing List]

This week's Theory of Computation seminar should be of interest to 
subscribers to this list:


Quantum Encodings and Applications to Communication Complexity and 
Locally Decodable Codes

by Iordanis Kerenidis (Postdoctoral Associate, MIT Math Dept.)
Tuesday, October 5, 2004 at 4:00 PM in Room 32-G449 (Kiva)

ABSTRACT

Quantum computation and information has become a central research 
area in theoretical computer science. It studies how information is 
encoded in nature according to the laws of quantum mechanics and what 
this means for its computational power. The ability of a quantum 
system to be in a superposition of states enables us to store an 
exponential amount of information in a quantum system. However, this 
information is accessible only indirectly via measurements. Our goal 
is precisely to investigate the fundamental question of how 
information is encoded and processed in quantum mechanical systems.

We investigate their power relative to classical encodings in the 
model of one-way communication complexity and show that they can be 
exponentially more efficient, answering a long-standing open question 
in the area of quantum communication complexity. Furthermore, we show 
how the theory developed for the study of quantum information can be 
employed in order to answer questions about classical coding theory 
and complexity by proving an exponential lower bound for 2-query 
Locally Decodable Codes. This is the first example where quantum 
techniques are essential in resolving a purely classical question.

No previous knowledge of quantum computing is assumed.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.mit.edu/pipermail/qip-sem/attachments/20041002/2ccc094c/attachment.htm