Quantenalgorithmus zur Ordnungsfindung

Die Ordnung von modulo bezeichnet die kleinste ganze Zahl , so daß . Falls und teilerfremd sind, ist die Funktion periodisch in mit Periode , d.h. falls ein Vielfaches von ist. Der unten beschriebene Quantenalgorithmus berechnet die Ordnung, indem er durch inverse FOURIER-Transformation die Periode der Funktion ermittelt.

Es werden hierfür zwei Quantenregister mit jeweils bzw. Qubits benötigt, wobei , so daß das zweite Register Zahlen von 0 bis darstellen kann, während mit (siehe unten). Außerdem benötigt man einen Quantenschaltkreis, der folgende Operation auf den beiden Registern durchführt:

und während des folgenden Algorithmus nur einmal durchlaufen werden muß.

Der in nachfolgender Schaltkreis gezeigte Algorithmus verläuft wie folgt:

1. Initialisiere die Register im Zustand
2. Wende auf Register 1 an. Dies erzeugt den Zustand

   
   

3. Wende die Operation an. Dies erzeugt den Zustand

   
   

   wobei die gesuchte Ordnung von modulo ist, und

   
   

4. Wende die inverse Quanten-FOURIER-Transformation auf Register 1 an. Dies erzeugt den Zustand

   
   

   Zu tragen nur Zustände signifikant bei, für die gilt.
5. Lies den Zustand des ersten Registers aus. Mit Wahrscheinlichkeit größer als gilt nun:

   
   

   wobei eine durch den Meßprozeß zufällig ausgewählte Zahl zwischen 0 und ist. Hierdurch ist der Bruch mit eindeutig bestimmt.
6. Bestimme den Nenner durch Darstellung von als Kettenbruch.

Zum Schluß wird geprüft, ob wirklich gilt. Ist dies der Fall, dann war der Algorithmus erfolgreich. Der Algorithmus kann aber aus folgenden zwei Gründen auch fehlschlagen:

• Erstens könnte eine schlechte Näherung an sein. Dies geschieht mit der Wahrscheinlichkeit kleiner als , die durch Wahl eines genügend großen (siehe oben) vernachlässigt werden kann.
  
• Zweitens könnten und einen gemeinsamen Teiler besitzen. In diesem Fall liefert die Kettenbruchdarstellung den Nenner anstelle von . Die gewünschte Ordnung kann dann durch mehrmaliges Wiederholen des obigen Algorithmus ermittelt werden [23.4].