Hamburg 2009 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

Q: Fachverband Quantenoptik und Photonik

Q 9: Quanteninformation: Konzepte II

Q 9.8: Talk

Monday, March 2, 2009, 15:45–16:00, VMP 6 HS-D

Factorization with Gauss Sums — •Sabine Wölk, Wolfgang Merkel, and Wolfgang Schleich — Institute of Quantum Physics, Ulm, Germany

Factoring large numbers N is one of the problems, for which analogue computers need exponential time. Quantum computers on the other hand, can do this in polynomial time. In 1994 P. Shor introduced his famous quantum algorithm for this problem, but it is still difficult to realize it experimentally. As a consequence so far only the number N=15 was factored with this algorithm.

For this reason we study the alternative route to factorization using Gauss sums. Our previous results have led to experimental factorizations of numbers N with up to 17 digits. However, our algorithm is slow because it checks every prime number l<√N if it is a factor or not. Nevertheless there is still an enormous potential in Gauss sums for factoring numbers. In our talk we introduce some new ideainvolvingng entanglement.