Dresden 2011 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

Q: Fachverband Quantenoptik und Photonik

Q 61: Quantum Information: Concepts and Methods 4

Q 61.2: Vortrag

Freitag, 18. März 2011, 10:45–11:00, SCH A118

Shor’s algorithm and the factorization with Gauss sums — •Sabine Wölk and Wolfgang Schleich — Institut für Quantenphysik, Universität Ulm, D-89069 Ulm, Germany

Shor’s algorithm is one of the famous algorithms which scales polynomial whereas analog computers need exponential time to solve the same problem. However, Shor’s algorithm does not factor numbers, it just find periods.

On the other side, there exist functions other than a^ℓ mod N used in Shor’s algorithm whose period also contains information about the factors of N. One of these functions is the standard Gauss sum.

In our talk, we will discuss the problems and improvements which emerge when we replace in Shor’s algorithm the function a^ℓ mod N by the standard Gauss sum. Furthermore, we show that the periodicity must not occur in the states itself, but can also appear in the probability amplitudes.