CEPI Seminar 10/10/04 Wim van Dam

Complexity, Entropy, and the Physics of Information Lecture Series
Wednesday, November 10, 2004, 5:00 PM. Refreshments 4:15 PM.
Robert N. Noyce Conference Room, Santa Fe Insitute
Wim van Dam
Computer Science Dept., University of California, Santa Barbara
Quantum Computing, Zeroes of Zeta Functions & Approximate Counting
Abstract:
In this talk I describe a possible connection between quantum computing and Zeta functions of finite field equations that is inspired by the ‘spectral approach’ to the Riemann conjecture. The assumption is that the zeroes of such Zeta functions correspond to the eigenvalues of finite dimensional unitary operators of natural quantum mechanical systems. To model the desired quantum systems I use the notion of universal, efficient quantum computation.
Using eigenvalue estimation, such quantum systems are able to approximately count the number of solutions of the specific finite field equations with an accuracy that does not appear to be feasible classically. For certain equations (Fermat hypersurfaces) I show that one can indeed model their Zeta functions with efficient quantum algorithms, which gives some evidence in favour of the proposal.