ABSTRACT

Quantum Computing: The End of Computer Science as we know it?

Dr. A. Narayanan, Dept. of Computer Science, University of Exeter

Trends towards increasing miniaturisation, in line with Moore's Law, means that the number of transistors integrated onto a single chip increases exponentially with time. In the 1950s and 1960s, several thousands of electrons were required to store one bit or to switch gates. Currently, only a few hundred electrons are required to do the same. By 2010, only 10 or so electrons will be required to store a bit and switch FETs. But, at this level, quantum physics takes over. Particles at the quantum level take on wave-particle duality, meaning that when an electron reaches a switch which is off it will jump across the switch by becoming a wave (like a radio signal). All possible routes through the circuit will be active at the same time. The implication for computer science, given that all software is ultimately realised in logic gates, is that all routes through a program will be active at the same time. This will result in chaos for current program design as well as chaos for current boolean logic and everything that rests on it (circuit design, logic gates, programming languages).

The aim of this talk is to propose that computer science, with its current dependence on discrete mathematics, classical physics and classical logic, faces a major challenge over the next 10 years on two fronts. First, computer science will have to revise its axiom that hardware doesn't matter when it comes to program design and development. Second, pioneering work by Shor indicates that quantum algorithms, because of their ability to make the most of 'wave computation', or computation in parallel universes, outperform their classical counterparts in ways that raise serious questions about the correctness and appropriateness of the class NP. Work at Exeter involving quantum algorithms for route finding will also be described. The conclusion of the talk will be that, unless computer scientists address the issue of advances in hardware determining future software design, there is a danger that computer science may become a historical subject, with quantum physicists becoming the computer scientists of the future.

Maintained by rbennett@cs.ucl.ac.uk