Colloquium 

02/10/2001, 17:00 — 18:00 — Amphitheatre Qa2, South Tower, IST
Paul Vitanyi, 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.