Colloquium   RSS

02/10/2001, 17:00 — 18:00 — Amphitheatre Qa2, South Tower, IST
, CWI and University of Amsterdam

The Quantum Computing Challenge

New computation devices increasingly depend on particular physical properties rather than on logical organization alone as used to be the case in conventional technologies. The laws of physics impose limits on increases in computing power. Two of these limits are interconnect wires in multicomputers and thermodynamic limits to energy dissipation in all computers. Quantum computing is a novel computational paradigm and technology that promises to eliminate problems of latency and wiring associated with parallel computers and the rapidly approaching ultimate limits to computing power imposed by the fundamental thermodynamics. The prospect of quantum computing has created excitement both among researchers and in the popular press by its algorithmic improvements over classical computing: integer factorization in square time (Shor), searching unstructured lists in square root time (Grover), improved communication complexity (Buhrman, Cleve). For some other problems (like binary search) quantum computation gives no super-linear speed-up over classical computing. While fast factoring will break almost all public key cryptosystems in use today, compromizing almost all secure (financial, government, commerce) e-transactions, quantum cryptography (Bennett, Brassard) may possibly come to the rescue. Superiority of quantum computing over classical probabilistic computing are due to the exploitation of interference in parallel quantum superposition and quantum entanglement. The actual realization of quantum computers is a formidable technological and theoretical challenge. Part of this challenge involves quantum information and communication theory (compression, fault-tolerance and error-correcting codes). The great algorithmic challenge is to find more quantum algorithms that improve classical ones (or show that none exist), and to more precisely determine the complexity of quantum computations compared to the classical complexity classes.

The Mathematics Colloquium is a series of monthly talks organized by the Department of Mathematics of IST, aiming to be a forum for the presentation of mathematical ideas or ideas about Mathematics. The Colloquium welcomes the participation of faculty, researchers and undergraduate or graduate students, of IST or other institutions, and is seen as an opportunity of bringing together and fostering the building up of ideas in an informal atmosphere.

Organizers: Conceição Amado, Lina Oliveira e Maria João Borges.