Funktionsweise

Superpositionen

  • Quantenteilchen existieren in allen ihren möglichen Zuständen gleichzeitig - Es befindet sich in Superposition
  • Das Ergebnis der Messung einer Eigenschaft ist über eine Wahrscheinlichkeitsverteilung gegeben: Ort, Geschwindigkeit, ...
  • Messung "zwingt" Teilchen in einen möglichen Zustand

Qubits

Ein Qubit kann, wie normale Bits auch, die Zustände $0$ und $1$ haben.
Aber ein Qubit kann auch in Superposition beider Zustände sein.
Die Messung ergibt immer entweder $0$ oder $1$.

Auf ein Qubit können, analog zu klassischen Bits, Operationen angewendet werden. Die Operationen werden durch unitäre Matrizen dargestellt.

Analog zu normalen Registern aus normalen Bits gibt es Quantenregistern aus Qubits. Der theoretische Informationsgehalt eines Quantenregisters wächst exponentiell mit der Anzahl der Bits.

Quantenschaltkreise

Eine Operation auf einem Quantenregister wird als Quantenschaltkreis bezeichnet. Die Operation wird in Form einer unitären Matrix auf das Quantenregister angewendet.

Die Operationen können auch auf einer Superposition eines Quantenregisters angewendet werden.

Beispiel: Die Hadamard-Transformation

Die Qubits befinden sich nach der Transformation in einer Superposition der möglichen Zustände, in welchem beide Zustände gleich wahrscheinlich sind.

Quantenverschränkung

  • Zwei oder mehr Quantenteilchen können verschränkt sein.
  • Verschränkung drückt eine Zusammengehörigkeit aus
  • Die einzelnen Teilchen können nicht mehr einzeln beschrieben werden, sondern nur das verschränkte Teilchensystem als ganzes
  • Änderungen an einem der Teilchen wirken sich auf alle anderen Teilchen des verschränkten Systems aus

Grovers Algorithmus

Grovers Algorithmus ist ein Suchalgorithmus für unsortierte Datenmengen. Anwendung auf andere Probleme bei entsprechender Formulierung des Problem möglich.

Grundidee: Starte mit einer Superposition aller Elemente des Suchraums und verstärke iterativ die Amplitude des gesuchten Elements ("amplitude amplification")

Shors Algorithmus

Es gibt keinen Algorithmus, der ganze Zahlen auf einem klassischen Computer effizient faktorisiert, aber ...
- Shors Algorithmus faktorisiert eine ganze Zahl auf einem Quantencomputer effizient, d.h. in polynomieller Laufzeit - Shors Algorithmus löst nicht die Faktorisierung im eigentlichen Sinne, sondern ein Ersatzproblem, auf das die Faktorisierung zurückgeführt werden kann.

Ablauf:

  1. Wähle eine Zahl $a < N$

  2. Prüfe, ob $a$ zufällig ein Teiler von $N$ ist

  3. Berechne die Periode $r$ vom Quantenteil des Algorithmus

  4. Wenn $r$ alle Anforderungen erfüllt, berechne einen Primfaktor von $N$, ansonsten fahre mit Schritt 1 fort

  5. Der größte gemeinsame Teiler von $x^{r/2}$ und $N$ ist sehr wahrscheinlich ein Primfaktor von $N$, in seltenen Fällen allerdings selbst wieder eine zusammengesetzte Zahl (z.B. für RSA nicht relevant)