Department of Mathematics

Digital computers perform calculations on individual strings of bits. Quantum computers extend classical digital computers by making use of quantum phenomena to perform calculations on bits which are in a state of superposition. For some classes of problems, this allows for superpolynomial speedup over classical algorithms. In the first half of the talk we give an introduction to quantum computation and to the various classes of problems exhibiting superpolynomial speedup. In the second half, we propose generalizations of these problems to the domain of universal algebras and present some results for the quantum tractability of these generalizations. Tea at 3:30pm in SC 1425. (Contact person: Ralph McKenzie)