Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Research Seminar

Manuel Noll: Proof of a Running Time Bound for Simulating a Quantum Machine on a Classical one via Jones Polynomi

Nov. 20, 2008, 10:15 a.m.
E 1 3, Room 415

This thesis states a new proof as well as a bound for the simulation of a quantum machine on a classical, everywhere at hand, computer. Since quantum machines are able to solve certain presumably hard problems in polynomial time, it is obvious that such a bound cannot be a polynomial one. Our proof uses the Jones polynomial as well as theory from fixed parameter tractability.