Seminario Interdipartimentale di Algoritmica
 
 

Monday, October 11, 2004  12:00 noon
Algorithms and Complexity for Continuous Problems on Quantum Computers
Joseph F. Traub
Columbia University

DI - Department of Computer Science, via Salaria 113
Seminar Room, third floor

Abstract:

For four decades advances in computation have been made possible by Moore's Law. It is generally believed that Moore's Law using current technologies will end in one to two decades because of both physical and economic limits. One candidate for the future is quantum computation. To date there have been two major algorithms for discrete problems on quantum computers that are significantly better than on classical computers: Shor's factorization and Grover's data search algorithms. But numerous problems in science and engineering have continuous mathematical models. Examples of such models include high dimensional integrals, path integrals, partial differential and integral equations, and continuous optimization. We use classical continuous complexity to:

We are developing algorithms for solving important continuous models which are difficult to solve on classical computers and which have large theoretical speedups on quantum computers. We seek quantum algorithms which require only a modest number of qubits. Future research directions will be indicated.