Quantencomputing-Kurs – Mathematik und Theorie für Anfänger

1. Einführung in die Quantencomputer-Grundlagen und Kursstruktur [0]

1. Quantencomputing nutzt Quantenmechanik zur schnellen Informationsverarbeitung [0].
2. Dieser Kurs bietet eine solide Grundlage von den Grundlagen bis zu Quantenalgorithmen [1].
3. Die Struktur umfasst zwei Hauptteile: Mathematik und Mechanik von Quantencomputern [2].
4. Der Kurs erklärt die Leistungsfähigkeit und den technologischen Wandel durch Quantencomputer [3].
5. Der Ersteller ist Michael von Quantum Source [4].
6. Der Kurs vermeidet Analogien (wie Q-Bits, die gleichzeitig 0 und 1 sind) [5].
7. Ziel ist es, zu lehren, wie Quantencomputer tatsächlich funktionieren [7].

1.1. Kursstruktur im Detail [9]

1. Erster Abschnitt: Grundlegende Mathematik für das Verständnis [9].
   1. Beinhaltet Einführung in komplexe Zahlen und lineare Algebra [9].
2. Nächster Abschnitt: Erforschung des Qubits und seiner mathematischen Darstellung [10].
   1. Es werden Qubit-Operationen und deren Eigenschaften untersucht [11].
3. Dritter Abschnitt: Mathematische Darstellung mehrerer Qubits und deren Operationen [12].
   1. Dieser Abschnitt endet mit Quantenverschränkung und Phase Kickback [13].
4. Letzter Abschnitt: Analyse von Quantenalgorithmen [14].
   1. Dieser Teil zeigt die revolutionäre Technologie der Quantencomputer [15].

2. Grundlagen der Mathematik: Komplexe Zahlen [16]

2.1. Quadratwurzeln und Imaginäre Zahlen [16]

1. Betrachte die Gleichung $x^2=4$, was $x=\pm 2$ ergibt [17].
2. Bei $x^2=-4$ kommen Imaginärzahlen ins Spiel [18].
3. Sei $i$ die Quadratwurzel von -1 [19].
4. Die Wurzel von -4 ist dann $\pm 2i$ [19].
5. Eine Imaginärzahl enthält einen Faktor von $\sqrt{-1}$ [20].
6. Nun wird zu Komplexen Zahlen übergegangen [21].

2.2. Definition und Operationen Komplexer Zahlen [22]

1. Eine komplexe Zahl ist eine Summe aus einer reellen und einer Imaginärzahl [22].
2. Die Standardform ist $a+iB$, wobei $A$ der Realteil und $B$ der Imaginärteil ist [23].
3. Komplexe Zahlen können einfach addiert und subtrahiert werden [25].
4. Multiplikation erfordert die Erinnerung, dass $i^2=-1$ ist [27].
5. Das Komplex Konjugierte erhält man durch Negation des Imaginärteils [28].
6. Dies wird durch einen Sternchen-Index (*) gekennzeichnet [29].
7. Wichtige Eigenschaft: Multiplikation einer komplexen Zahl mit ihrem Konjugierten ergibt immer eine reelle Zahl [31].

2.3. Darstellung Komplexer Zahlen in der Ebene [33]

1. Komplexe Zahlen können als Vektor im Koordinatensystem dargestellt werden [33].
   1. Die horizontale Achse ist die Reelle Achse [33].
   2. Die vertikale Achse ist die Imaginäre Achse [33].
2. Die Magnitude (Abstand vom Ursprung) wird mit Pythagoras berechnet [35].
   1. $|A+iB|=\sqrt{a^2+b^2}$ [36].
3. Eine alternative Darstellung nutzt Magnitude ($r$) und Winkel ($\theta$) [38].
   1. Dies ist die Polardarstellung: $r(\cos \theta +i\sin \theta )$ [41].
   2. $\theta$ wird über $\arctan (b/a)$ gefunden [40].
4. Es gibt auch die Exponentialform: $r{e}^{i\theta }$ [42].
5. In der Quantenberechnung wird fast ausschließlich die Exponentialform verwendet [44].
6. Diese Form ist nützlich, da die Änderung von $\theta$ eine Rotation darstellt [45].

3. Matrizen und ihre Eigenschaften [47]

3.1. Definition und Grundoperationen [47]

1. Eine Matrix ist eine zweidimensionale Anordnung von Zahlen [47].
2. Eine $M\times N$ Matrix hat $M$ Zeilen und $N$ Spalten [49].
3. Addition und Subtraktion erfolgen elementweise [51].
   1. Matrizen müssen die gleichen Dimensionen haben, um addiert zu werden [53].
4. Multiplikation mit einem Skalar multipliziert jedes Element mit dem Skalar [55].
5. Matrixmultiplikation erfordert das Skalarprodukt (Dot Product) [57].
   1. Das Element in Zeile $i$, Spalte $j$ wird durch die Multiplikation der $i$-ten Zeile der linken Matrix mit der $j$-ten Spalte der rechten Matrix berechnet [57].

3.2. Multiplikationsbedingungen und Vektoren [60]

1. Matrixmultiplikation ist nur möglich, wenn die Spaltenanzahl der ersten gleich der Zeilenanzahl der zweiten ist [61].
2. Eine $N\times 1$ Matrix wird als Spaltenvektor bezeichnet [63].
3. Spaltenvektoren können einen Quantenzustand darstellen [65].
4. Die Multiplikation einer Matrix mit einem Spaltenvektor ergibt einen neuen Spaltenvektor [66].
5. Intuitiv wird der Vektor durch die Matrix transformiert [67].
6. Matrizen dienen als Transformationen auf Vektoren [69].

3.3. Spezielle Matrizen und Konjugationen [70]

1. Die Identitätsmatrix (Einsen auf der Hauptdiagonale) lässt Matrizen unverändert [70].
2. Matrizen besitzen eine Inverse ($A^{-1}$), die mit $A$ die Identitätsmatrix ergibt [74].
   1. Grafisch bedeutet dies, dass die Anwendung von $A$ und dann $A^{-1}$ den Vektor am Ursprungsort belässt [77].
3. Das Komplex Konjugierte einer Matrix (*-Index) negiert alle Imaginärteile der Elemente [78].
4. Die Transponierte ($T$) tauscht Zeilen und Spalten aus [82].
5. Die Kombination aus Konjugiertem und Transponiertem ergibt den Dagger ($†$) [84].
6. In der Quantenberechnung werden zwei Matrixtypen verwendet [85]:
   1. Unitäre Matrizen ($U$): $U{U}^{†}=I$ (Die Dagger-Matrix ist die Inverse) [86].
      • Geometrisch bleibt die Länge des Vektors erhalten; er wird nur rotiert oder gespiegelt [88].
   2. Hermitesche Matrizen ($H$): $H=H^{†}$ [90].
7. Eigenvektoren bleiben bei Transformation in dieselbe Richtung gestreckt oder gestaucht [93].
   1. Der Skalierungsfaktor ist der Eigenwert [94].
   2. Beispiel: Matrix $\left(\begin{array}{cc}2& 0\\ 1& 2\end{array}\right)$ mit Vektor $\left(\begin{array}{c}0\\ 3\end{array}\right)$ ergibt Eigenwert 2 [96].

4. Qubits und Quantenzustände [99]

4.1. Qubits vs. Klassische Bits [99]

1. Klassische Computer nutzen binäre Nullen und Einsen [99].
2. Quantencomputer nutzen Qubits (Quanten-Bits) [100].
3. Ein Qubit kann ein Quantenteilchen in zwei Zuständen sein (z.B. Polarisation) [104].
4. Die Zustände 0 und 1 werden mathematisch als Spaltenvektoren definiert [105]:
   1. $|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$ und $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$ [105].
5. Die Klammern sind Dirac-Notation (Kets) [106].
6. Superposition bedeutet, dass ein Teilchen gleichzeitig in zwei Zuständen existiert [107].
   1. Ein Qubit in Superposition ist gleichzeitig 0 und 1 [109].
7. Mathematisch ist ein Qubit ein Spaltenvektor mit zwei Elementen [111].
   1. Das obere Element ist die Amplitude des 0-Zustands [112].
   2. Das untere Element ist die Amplitude des 1-Zustands [112].
8. Wenn beide Amplituden ungleich Null sind, liegt Superposition vor [116].

4.2. Messung und Wahrscheinlichkeiten [117]

1. Die Messung eines Quantensystems ändert dessen Zustand auf das Messergebnis [117].
2. Ein Qubit kollabiert beim Messen zu entweder 0 oder 1 [122].
3. Man misst nicht die Amplituden, sondern nur 0 oder 1 [124].
4. Die Amplituden geben die Wahrscheinlichkeit der Messung an [126].
   1. $P(0)$ ist das Quadrat der Magnitude der 0-Amplitude [127].
   2. $P(1)$ ist das Quadrat der Magnitude der 1-Amplitude [127].
5. Die Wahrscheinlichkeiten müssen sich zu Eins addieren (gültiger Qubit-Zustand) [131].
6. Nach der Messung kollabiert der Zustand permanent in den gemessenen Zustand [132].

4.3. Dirac-Notation und Bloch-Kugel [135]

1. Die Dirac-Notation wird zur Darstellung von Quantenzuständen verwendet [135].
2. Ein Matrixzustand $\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)$ wird zu $\alpha |0⟩+\beta |1⟩$ konvertiert [136].
3. Die Klammern $⟨\cdot |$ und $|\cdot ⟩$ sind Kets und Bras [140].
4. Die Matrixdarstellung wird bei vielen Qubits unhandlich [143].
5. Ein Qubit kann grafisch auf der Bloch-Kugel dargestellt werden [144].
   1. Oben ist der 0-Zustand (Nordpol) [145].
   2. Unten ist der 1-Zustand (Südpol) [145].
6. Die Höhe des Qubits bestimmt die Messwahrscheinlichkeit [148].
   1. Höher oben bedeutet höhere Wahrscheinlichkeit, 0 zu messen [148].
7. Die Rotation um die Kugel wird als Phase bezeichnet [151].

5. Einzel-Qubit-Gatter und Phase [155]

5.1. Einzel-Qubit-Gatter: X, Y, Z [155]

1. Quantencomputer nutzen Gatter zur Zustandsänderung [157].
2. Die häufigsten Einzel-Qubit-Gatter sind X, Y und Z [158].
3. Das X-Gatter (NOT) kehrt den Zustand um (0 wird zu 1) [160].
   1. Grafisch rotiert es um 180° ($\pi$ Radiant) um die X-Achse [164].
4. Das Y-Gatter rotiert den Zustand um 180° um die Y-Achse [167].
5. Das Z-Gatter rotiert den Zustand um 180° um die Z-Achse [168].
6. Da diese Gatter um $\pi$ rotieren, sind sie ihre eigenen Inversen [169].
7. Die Gatter werden durch Matrizen dargestellt [171].
   1. Die Y-Gatter-Matrix enthält komplexe Zahlen, die später erklärt werden [172].

5.2. Anwendung von Gattern und Lineare Abhängigkeit [174]

1. Die Anwendung eines Gatters erfolgt durch Matrixmultiplikation mit dem Qubit-Vektor [174].
2. Bei der Anwendung in Dirac-Notation zeigt die erste Spalte der Matrix, wohin $|0⟩$ geht [177].
3. Die zweite Spalte zeigt, wohin $|1⟩$ geht [177].
4. Da Quantengatter linear sind, wirken sie individuell auf Superpositionszustände [179].
5. Beispiel: Anwendung des Z-Gatters auf $\alpha |0⟩+\beta |1⟩$ ergibt $\alpha |0⟩-\beta |1⟩$ [183].

5.3. Die Bedeutung der Phase [184]

1. Das Z-Gatter ändert die Wahrscheinlichkeiten nicht (Amplitude ${\alpha }^2$ bleibt gleich) [184].
2. Die Phase ist entscheidend für die Leistungsfähigkeit von Quantencomputern [187].
3. Die Phase wird mathematisch durch komplexe Zahlen in Exponentialform dargestellt [189].
4. Das Z-Gatter multipliziert $|1⟩$ mit dem Faktor $-1$, was $e^{i\pi }$ entspricht [194].
5. $i$ entspricht einer Rotation von $\pi /2$ Radiant um die Z-Achse ($e^{i\pi /2}$) [200].
6. Die Multiplikation des $|1⟩$-Zustands mit $e^{i\theta }$ rotiert das Qubit um die Z-Achse [201].
7. Es gibt zwei Arten von Phase [202]:
   1. Global Phase: Multipliziert den gesamten Qubit-Zustand; ist physikalisch irrelevant [203].
   2. Relative Phase: Multipliziert nur die Amplitude des $|1⟩$-Zustands; ist extrem wichtig [205].
8. Wenn beide Amplituden komplexe Faktoren haben, wird die Global Phase entfernt [208].
9. Phase ändert die Wahrscheinlichkeit nicht, da $|e^{i\varphi }{|}^2=1$ [209].

6. Spezielle Zustände und Hadamard-Gatter [214]

6.1. Zustände auf dem Äquator der Bloch-Kugel [214]

1. Zustände auf dem Äquator (Plus, Minus, $i$, $-i$) haben gleiche Messwahrscheinlichkeiten [215].
2. Sie unterscheiden sich nur durch ihre Relative Phase [218].
3. Der Plus-Zustand ist $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$ [219].
4. Der Minus-Zustand ist der Plus-Zustand mit relativer Phase $-1$ [220].
5. Der $i$-Zustand hat eine relative Phase von $i$ [222].
6. Der negative $i$-Zustand hat eine relative Phase von $-i$ [222].

6.2. Das Hadamard-Gatter (H) [223]

1. Das Hadamard-Gatter wird durch eine spezifische Matrix dargestellt [224].
2. Es transformiert $|0⟩$ in den Plus-Zustand und $|1⟩$ in den Minus-Zustand [225].
3. Das Hadamard-Gatter ist sein eigenes Inverses [227].
4. Anwendung auf Plus/Minus kehrt die Zustände zu 0/1 zurück [226].
5. Das Hadamard-Gatter zeigt, dass Phase wichtig ist [229].
   1. Zustände, die sich nur durch relative Phase unterscheiden, werden nach H unterschiedlich [231].

7. Weitere Gatter und Mehr-Qubit-Systeme [234]

7.1. S- und T-Gatter [234]

1. Das S-Gatter fügt eine relative Phase von $\pi /2$ hinzu [235].
2. Das T-Gatter fügt eine relative Phase von $\pi /4$ hinzu [236].
3. Die konjugierte Transponierte der Gattermatrizen ergibt deren Inverse [237].
   1. $S^{†}$ fügt $-\pi /2$ hinzu und ist das Inverse von $S$ [238].
   2. $T^{†}$ fügt $-\pi /4$ hinzu und ist das Inverse von $T$ [240].

7.2. Mehrere Qubits und Tensorprodukt [241]

1. Mehrere Qubits werden durch das Tensorprodukt ($\otimes$) dargestellt [241].
2. Zwei Qubits im Zustand $|0⟩$ werden als $\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)$ dargestellt [242].
3. Dies wird oft zu $|00⟩$ verkürzt [243].
4. Zwei Qubits in Superposition ergeben vier Zustände ($|00⟩,|01⟩,|10⟩,|11⟩$) [245].
5. Die Messwahrscheinlichkeit ist das Quadrat der Magnitude des jeweiligen Koeffizienten [247].
6. Weitere Qubits werden einfach hinten an das System getensort [249].
7. Es gibt Kurzschreibweisen, z.B. für $n$ Nullen: $|0^{\otimes n}⟩$ [251].

7.3. Quantenschaltkreise [252]

1. Die Darstellung von Schaltungen erfolgt durch Quantenschaltkreise [252].
2. Vertikal sind die Qubits dargestellt (jede Linie ein Qubit) [254].
3. Links stehen die Anfangszustände [255].
4. Boxen repräsentieren Quantengatter (z.B. X-Gatter) [255].
5. Messungen werden durch Messsymbole dargestellt [257].
6. Die Gates werden von links nach rechts angewendet (zeitlicher Ablauf) [258].
7. Zustandsanzeigen im Schaltkreis zeigen den Systemzustand zu bestimmten Zeitpunkten [259].
8. Beispiel: Anwendung von X auf Qubit 2, dann H auf Qubit 2, dann X auf Qubits 1 und 3 [260].

8. Mehr-Qubit-Gatter und Verschränkung [264]

8.1. Kontrollierte Gatter: CNOT und Toffoli [264]

1. Das häufigste Multi-Qubit-Gatter ist das CNOT (Controlled-X) [265].
2. Es wirkt auf ein Kontroll-Qubit und ein Ziel-Qubit [268].
3. Das CNOT wendet ein X-Gatter auf das Ziel an, nur wenn das Kontroll-Qubit eine 1 ist [269].
4. Das Toffoli-Gatter ist ähnlich, hat aber zwei Kontroll-Qubits [272].
5. Man kann kontrollierte Versionen anderer Einzel-Qubit-Gatter erstellen (z.B. Kontrolliert-Y) [276].
   1. Dies wird durch eine Linie vom Kontroll-Qubit zum Gatter dargestellt [277].

8.2. Messung und Kollaps bei mehreren Qubits [279]

1. Die Wahrscheinlichkeit, ein einzelnes Qubit in einem Mehr-Qubit-System zu messen, wird summiert [279].
2. Wenn ein Qubit gemessen wird, kollabiert die gesamte Superposition [282].
3. Alle Zustände, bei denen das gemessene Qubit nicht dem Ergebnis entspricht, werden eliminiert [284].
4. Die verbleibenden Wahrscheinlichkeiten müssen durch einen Normalisierungskonstanten ($A$) korrigiert werden [285].
5. Beispiel: Messung des ersten Qubits als 1 führt zu einem neuen, normalisierten Zustand [288].

8.3. Verschränkung (Entanglement) [298]

1. Wenn das Messen eines Qubits den Zustand des anderen sofort bestimmt, liegt Verschränkung vor [299].
2. Ein Zustand ist verschränkt, wenn er nicht als Tensorprodukt einzelner Qubit-Zustände faktorisiert werden kann [302].
3. Verschränkte Qubits hängen voneinander ab [304].
4. Es gibt zwei Typen verschränkter Zustände [305]:
   1. Maximal verschränkte Zustände: Messung eines Qubits bestimmt den Zustand der anderen [306].
      • Die häufigsten sind die Bell-Zustände ($\Phi ,\Psi$) [308].
   2. Teilweise verschränkte Zustände: Messung beeinflusst die Wahrscheinlichkeiten oder Phase der anderen Qubits [310].

8.4. Phase Kickback [313]

1. Phase Kickback tritt auf, wenn das Ziel-Qubit ein Eigenzustand des angewendeten kontrollierten Gates ist [314].
2. Wenn $V$ ein Eigenzustand von $U$ ist ($UV=e^{i\theta }V$), wird die Phase $e^{i\theta }$ auf das Kontroll-Qubit übertragen [316].
3. Das Ziel-Qubit ($V$) bleibt unverändert [321].
4. Dieses Phänomen wird in einigen Quantenalgorithmen genutzt [323].

9. Quantenprotokolle und Klassische Operationen [324]

9.1. Superdense Coding [324]

1. Dieses Protokoll erlaubt das Senden von zwei Bits klassischer Information mit nur einem Qubit [325].
2. Voraussetzung ist die maximale Verschränkung zweier Qubits (Bell-Zustand) [327].
3. Alice (Sender) und Bob (Empfänger) teilen sich die Qubits [330].
4. Alice führt Operationen auf ihrem Qubit basierend auf den zu sendenden 2 Bits durch [332]:
   • Sende 00: Nichts tun [333].
   • Sende 01: X-Gatter anwenden [334].
   • Sende 10: Z-Gatter anwenden [335].
   • Sende 11: X- und Z-Gatter anwenden [336].
5. Alice sendet ihr Qubit an Bob [337].
6. Bob wendet CNOT (Qubit 1 Kontrolle, Qubit 2 Ziel) an [339].
7. Dann wendet er ein Hadamard-Gatter auf das linke Qubit an [340].
8. Durch Messung der Qubits erhält Bob die ursprünglich von Alice gesendeten zwei Bits [341].

9.2. Klassische Logikgatter und Reversibilität [345]

1. Klassische Computer nutzen AND, OR, NOT und XOR (Exklusiv-Oder) [346].
2. NOT ist das einfachste Gatter (flippt 0 zu 1 und umgekehrt) [348].
3. AND gibt 1 nur zurück, wenn beide Eingänge 1 sind [351].
4. OR gibt 1 zurück, wenn mindestens ein Eingang 1 ist [354].
5. XOR gibt 1 zurück, wenn die Eingänge unterschiedlich sind [356].
6. XOR wird verwendet, um klassische Gatter reversibel zu machen [359].
7. Eine Funktion $f$ ist reversibel, wenn man aus $f(x)$ den Wert $x$ bestimmen kann [360].
   1. Die OR-Operation ist nicht reversibel (Output 1 kann von drei Inputs stammen) [361].
8. Um ein Gatter reversibel zu machen, fügt man ein zusätzliches Bit $C$ hinzu [363].
   1. Die Ausgabe wird $X$ und $C\oplus f(X)$ [363].
9. Wichtig: Alle Operationen in Quantencomputern (außer Messung) müssen reversibel sein [369].
   1. Dies liegt daran, dass alle Operationen unitär sein müssen [371].

10. Funktionen auf Quantencomputern [373]

10.1. Abfragen von Funktionen mittels Reversibilität [373]

1. Quantenfunktionen müssen reversibel sein, um sie auf einem Quantencomputer anzuwenden [375].
2. Eine reversible Funktion $f$ wird als $X,Y\to X,Y\oplus f(X)$ dargestellt [377].
3. Setzt man $Y=0$, wird die Ausgabe $0\oplus f(X)=f(X)$ [379].
4. Dies erlaubt das Abfragen der Funktion und Erhalt des Outputs [381].
5. Funktionen werden durch eine unitäre Matrix ($U_f$) kodiert [382].
6. Die Anwendung auf den Zustand $|x0⟩$ ergibt $|x,f(x)⟩$ [383].
7. Der Funktionsoutput wird durch Messung des zweiten Qubit-Registers erhalten [383].

10.2. Phasen-Orakel und Zustandsänderung [384]

1. Wendet man $U_f$ auf den Zustand $\frac{1}{\sqrt{2}}(|x⟩|0⟩-|x⟩|1⟩)$ an, entsteht ein Phasen-Orakel [385].
2. Der Zustand wird zu $\frac{1}{\sqrt{2}}(|x⟩|f(x)⟩-|x⟩|1\oplus f(x)⟩)$ [389].
3. Wenn $f(x)=0$, wird der Zustand zu $\frac{1}{\sqrt{2}}(|x⟩|0⟩-|x⟩|1⟩)=\frac{1}{\sqrt{2}}(|x⟩|-⟩)$ [390].
4. Wenn $f(x)=1$, wird der Zustand zu $\frac{1}{\sqrt{2}}(|x⟩|1⟩-|x⟩|0⟩)=-\frac{1}{\sqrt{2}}(|x⟩|0⟩-|x⟩|1⟩)$ [391].
5. Dies kann zusammengefasst werden als: $-1^{f(x)}|x⟩|-⟩$ [397].
6. Wenn das Ausgabe-Qubit im Minus-Zustand ist, nennt man dies Phasen-Orakel [398].

10.3. Das No-Cloning-Theorem [400]

1. Auf klassischen Computern kann man Bits kopieren, indem man Werte liest und schreibt [401].
2. Bei Quantencomputern kann ein unbekannter Qubit-Zustand ($|\psi ⟩=\alpha |0⟩+\beta |1⟩$) nicht kopiert werden [401].
3. Man müsste $\alpha$ und $\beta$ kennen, um den Zustand zu kopieren [402].

11. Deutschs Algorithmus [405]

11.1. Problemstellung: Konstant oder Ausgeglichen [405]

1. Problem: Finde heraus, ob eine Funktion $f$ (1 Bit Input $\to$ 1 Bit Output) konstant oder ausgeglichen (balanced) ist [405].
   • Konstant: Gibt immer denselben Wert zurück (z.B. immer 0 oder immer 1) [411].
   • Ausgeglichen: Gibt für die Hälfte der Inputs 0 und für die andere Hälfte 1 zurück [413].
2. Klassisch benötigt man zwei Funktionsabfragen ($f(0)$ und $f(1)$) [417].

11.2. Deutschs Algorithmus (Eine Abfrage) [419]

1. Mit Quantencomputern und Deutschs Algorithmus ist eine einzige Abfrage nötig [420].
2. Schaltkreis-Schritte [422]:
   1. Anfangszustand: $|00⟩$ [423].
   2. Anwendung von Hadamard auf beide Qubits: $\frac{1}{2}(|0⟩+|1⟩)\otimes (|0⟩-|1⟩)=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)\otimes \frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ [425].
   3. Anwendung des Funktionsorakels $U_f$ [427].
   4. Die Zustände sind nun im Phasen-Orakel-Format [429].
3. Analyse der Ergebnisse [431]:
   • Wenn $f(0)=f(1)$ (Konstant): Der Zustand wird zum Plus-Zustand $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$ [432].
   • Wenn $f(0)\ne f(1)$ (Ausgeglichen): Der Zustand wird zum Minus-Zustand $\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ [433].
4. Abschluss [439]:
   • Anwendung von Hadamard auf das erste Qubit [439].
   • Wenn das Ergebnis 0 ist $\to$ Funktion ist konstant [441].
   • Wenn das Ergebnis 1 ist $\to$ Funktion ist ausgeglichen [441].

12. Deutsch-Jozsa-Algorithmus [443]

12.1. Verallgemeinerung des Problems [443]

1. Der Deutsch-Jozsa-Algorithmus löst dasselbe Problem für Funktionen mit $n$ Input-Bits [443].
2. Klassisch benötigt man im schlimmsten Fall $2^{n-1}+1$ Abfragen [451].
3. Quantencomputer benötigen nur eine einzige Funktionsabfrage [455].

12.2. Der Deutsch-Jozsa-Schaltkreis [456]

1. Schaltkreis-Schritte [457]:
   1. Anfangszustand: $n$ Qubits im Zustand $|0^{\otimes n}⟩$ [459].
   2. Anwendung von Hadamard auf alle $n$ Qubits [460].
      • Identität: Hadamard auf $|0^{\otimes n}⟩$ ergibt eine gleichmäßige Superposition aller $2^n$ Bitstrings $x$ [471].
   3. Anwendung des Oracle-Funktion $U_f$ [476].
      • Der Zustand wird zu $\frac{1}{2^{n/2}}{\sum }_x(-1{)}^{f(x)}|x⟩$ (Phasen-Orakel-Form) [479].
   4. Anwendung von Hadamard auf alle $n$ Qubits [481].
      • Es wird eine wichtige Identität für Hadamard auf beliebige Bitstrings verwendet [483].
2. Das Endergebnis ist ein Zustand, dessen Amplitude für den All-Null-Zustand ($|0^{\otimes n}⟩$) analysiert wird [496].

12.3. Analyse des All-Null-Zustands [499]

1. Wenn $f$ konstant ist: Die Amplitude des $|0^{\otimes n}⟩$-Zustands ist $\pm 1$ [500].
2. Wenn $f$ ausgeglichen ist: Die Summe der Amplituden ergibt Null [505].
3. Messung [509]:
   • Misst man $|0^{\otimes n}\rangle$, ist die Funktion konstant (Wahrscheinlichkeit 1) [511].
   • Misst man etwas anderes, ist die Funktion ausgeglichen (Wahrscheinlichkeit 0 für $|0^{\otimes n}⟩$) [512].
4. Schlüssel-Takeaway: Zwei zentrale Identitäten sind für viele Algorithmen wichtig [515].

13. Bernstein-Vazirani-Algorithmus [517]

13.1. Problemstellung und Klassische Lösung [517]

1. Problem: Finde einen geheimen Bitstring $S$ der Länge $n$ [518].
2. Die Funktion $f(X)$ ist das Dot Product von Input $X$ und $S$ modulo 2 ($X\cdot S(\mathrm{mod}2)$) [518].
3. Klassisch benötigt man $n$ Abfragen, um jedes Bit von $S$ einzeln zu ermitteln [520].

13.2. Quanten-Lösung (Eine Abfrage) [523]

1. Der Schaltkreis ähnelt dem von Deutschs Algorithmus [523].
2. Schritte [525]:
   1. Anfangszustand: $|0^{\otimes n}⟩$ [525].
   2. Hadamard auf alle Qubits $\to$ gleichmäßige Superposition [526].
   3. Anwendung des Phasen-Orakels $U_f$ (da das Ziel-Qubit im $|-⟩$-Zustand ist) [527].
      • $f(X)=X\cdot S(\mathrm{mod}2)$ wird in die Phase integriert [529].
   4. Erneute Anwendung von Hadamard auf alle Qubits [531].
3. Analyse [532]:
   • Nach der zweiten Hadamard-Transformation wird die Amplitude des Zustands $S$ untersucht [539].
   • Die Amplitude des Zustands $|S⟩$ ist 1 [544].
4. Ergebnis: Die Wahrscheinlichkeit, $S$ zu messen, ist eins [545].
5. Gemeinsamkeit: Viele Algorithmen nutzen die Struktur: Hadamard $\to$ Oracle $\to$ Hadamard [548].

14. Quanten-Fourier-Transformation (QFT) [549]

14.1. Intuition der QFT [550]

1. Die QFT wird zusammen mit der Quantenphasenschätzung in Shor's Algorithmus verwendet [549].
2. Die QFT transformiert Zustände, indem sie die Phase der Qubits kodiert [552].
3. Binäre Zahlen werden klassisch durch 0/1 dargestellt [553].
4. Nach QFT wird die Zahl durch die relative Phase der Qubits in gleichmäßiger Superposition kodiert [556].
5. Beispiel: Die Zahl 5 (binär 101) wird kodiert [561].
   • Das rechte Qubit wird um $5/8\cdot 2\pi$ (d.h. $5\pi /4$) rotiert [562].
   • Das nächste Qubit wird um $2\cdot 5\pi /4$ rotiert, usw. [563].

14.2. QFT-Schaltkreis und Formel [565]

1. Der QFT-Schaltkreis für $n$ Bits enthält zwei neue Gattertypen [566]:
   1. Kontrolliertes R-Gatter ($R_k$): Wendet eine Phase an, wenn das Kontroll-Qubit 1 ist [568].
   2. Swap-Gatter: Tauscht die Zustände zweier Qubits [573].
2. Beispiel mit drei Bits ($J=j_2{j}_1{j}_0$): Die Qubits werden einzeln transformiert und am Ende geswappt [574].
3. Die allgemeine Formel für die QFT eines Basis-Zustands $|J⟩$ ist [592]:

   $$\text{QFT}(|J⟩)=\frac{1}{2^{n/2}}\sum _{k=0}^{2^n-1}{e}^{2\pi ijk/2^n}|k⟩$$

4. Die Inverse QFT macht die Transformation rückgängig [593].

15. Quantenphasenschätzung (QPE) [595]

15.1. Ziel der QPE [595]

1. QPE findet den Eigenwert ($\lambda =e^{i\theta }$) eines Eigenvektors ($V$) einer Matrix ($U$) [595].
2. Der Algorithmus findet $e^{i\theta }$ mit einer bestimmten Genauigkeit [597].
3. QPE ist ein Schlüsselbestandteil von Shor's Algorithmus [598].

15.2. QPE-Schaltkreis und Ablauf [599]

1. Der Schaltkreis hat zwei Register [599]:
   1. Das erste Register ($M$ Nullen) speichert die geschätzte Phase [600].
   2. Das zweite Register ($V$) ist der Eigenvektor [600].
2. Schritte [604]:
   1. Anfangszustand: $M$ Nullen und der Eigenvektor $V$ [605].
   2. Hadamard auf das erste Register [607].
   3. Anwendung von $U^{2^k}$ (kontrolliert durch das $k$-te Qubit des ersten Registers) auf $V$ [608].
   4. Phase Kickback tritt auf und addiert die Phase $e^{i{2}^k\theta }$ zum Kontroll-Qubit [608].
3. Phasenschätzung [612]:
   • Wenn $\theta =2\pi J$ gesetzt wird, wird der Zustand des ersten Registers zu einer Form, die der QFT auf $|J\rangle$ entspricht [613].
4. Durch Anwendung der Inversen QFT auf das erste Register und anschließende Messung wird $J$ mit $M$ Bits approximiert [622].
5. Mit $J$ kann $\theta$ und somit der Eigenwert $e^{i\theta }$ gefunden werden [624].

16. Shor's Algorithmus zur Faktorisierung [625]

16.1. Ziel und Klassische Reduktion [625]

1. Shor's Algorithmus findet die Primfaktoren $P$ und $Q$ einer Zahl $N=PQ$ [626].
2. Dies ist die Grundlage zur Knackung von RSA-Verschlüsselung [628].
3. Erfordert einen fehlertoleranten Quantencomputer mit Millionen logischer Qubits [629].
4. Klassischer Schritt 1: Wähle $A$ so, dass $\text{GCD}(A,N)=1$ [631].
5. Reduktion: Das Problem wird auf die Periodenfindung der modularen Exponentiation reduziert [633].
   • Man sucht die Periode $R$ der Folge $A^x(\mathrm{mod}N)$ [638].
6. Zahlentheorie: Wenn $R$ bekannt ist, können die Faktoren $P$ und $Q$ gefunden werden [642].
   • Man berechnet $\text{GCD}(A^{R/2}-1,N)$ und $\text{GCD}(A^{R/2}+1,N)$ [642].

16.2. Quantenschritt: Periodenfindung [644]

1. Es wird ein Quantengatter $U$ benötigt, das $|x⟩\to |xA(\mathrm{mod}N)⟩$ transformiert [644].
2. Der Zustand $|1⟩$ wird wiederholt mit $U$ angewendet, um Potenzen von $A$ zu erzeugen [645].
3. Der Zustand $|1⟩$ ist ein Eigenvektor von $U$ mit Eigenwert $e^{2\pi iS/R}$ [652].
   • $S$ ist eine unbekannte Zahl, $R$ ist die gesuchte Periode [652].
4. Es ist einfacher, die Superposition aller $U_S$-Zustände zu konstruieren [655].
   • Dies wird durch Anwendung von $K$ Gattern auf $|1⟩$ erreicht, was $|1(\mathrm{mod}N)⟩$ ergibt [657].
5. QPE-Anwendung: Der QPE-Algorithmus wird auf diesen Zustand angewendet [661].
   • Er schätzt den Eigenwert $e^{2\pi iS/R}$ [663].
6. Das Ergebnis ist eine Dezimalzahl $J\approx S/R$ [665].

16.3. Klassische Nachbearbeitung [666]

1. $S$ und $R$ werden aus dem geschätzten Wert $J$ mittels Kettenbrüchen geschätzt [666].
2. Man wählt eine Näherung für $S/R$, deren Nenner kleiner als $N$ ist (da $R<N$) [672].
3. Wenn $R$ ungerade ist, wird der Algorithmus wiederholt [673].
4. Faktorisierung [674]:
   • Mit dem gefundenen $R$ gilt $A^R\equiv 1(\mathrm{mod}N)$ [675].
   • Dies führt zu $(A^{R/2}-1)(A^{R/2}+1)\equiv 0(\mathrm{mod}N)$ [677].
   • Die Faktoren von $N$ werden durch $\text{GCD}(A^{R/2}-1,N)$ und $\text{GCD}(A^{R/2}+1,N)$ gefunden [678].
5. Beispiel $N=15$: Wähle $A=7$. Periode $R=4$ [680].
   • $\text{GCD}(7^{4/2}-1,15)=\text{GCD}(48,15)=3$ [686].
   • $\text{GCD}(7^{4/2}+1,15)=\text{GCD}(50,15)=5$ [687].
   • Die Faktoren sind 3 und 5 [688].