Übersicht

Zur Bestimmung der Ordnung werden durch einen Quantencomputer folgende Schritte durchgeführt ($q$ sei 2er-Potenz mit $n^2 \leq q < 2n^2$):

• Herstellung der Gleichverteilung der Funktionsargumente ( $a = 0, \ldots, q-1$ in Superposition)
• Berechnung des Funktionsgraphen $a \mapsto x^a \bmod n$ (Quantenparallelismus)
• Anwendung der diskreten Fouriertransformation auf $\mathbbm{Z}_q$
• Messung

Der entsprechende Quantenschaltkreis sieht dabei schematisch wie folgt aus, wobei H die bekannte Hadamard-Matrix darstellt, E die modulare Exponentation, DFT die diskrete Fouriertransformation auf $\mathbbm{Z}_q$ und B die Messung zur Standardbasis symbolisieren.

Abbildung 2: Schema des Quantenschaltkreises