📡 Quantencomputer & Komplexitätsklassen
1. Basics
1. Was ist ein Quantencomputer?
Die Definition:
Computer basierend auf Quantenmechanischen Prinzipien (Superposition, Verschränkung, Interferenz) statt klassischen Bits!
Computer basierend auf Quantenmechanischen Prinzipien (Superposition, Verschränkung, Interferenz) statt klassischen Bits!
- Klassisch: Bit = 0 oder 1
- Quantenmechanisch: Qubit = beide gleichzeitig!
- Skalieren: n Qubits = 2ⁿ Zustände überlagert
- Potenzial: Exponentieller Vorteil möglich
- Problem: Dekoheränz zerstört Quanteneffekte
Warum nicht einfach? Qubits extrem fragil! Umwelt macht Messung!
2. Qubits
2. Qubits & Superposition: Die Magie
Der Superpositions-Effekt:
• Mathematik: |ψ⟩ = α|0⟩ + β|1⟩
• Interpretation: 0 UND 1 gleichzeitig!
• Messung: Kollaps zu 0 (prob. |α|²) oder 1 (prob. |β|²)
• Parallelism: n Qubits = 2ⁿ Rechenpfade parallel!
• Trick: Interferenz so designen dass falsche Wege weg, richtige bleiben
• Mathematik: |ψ⟩ = α|0⟩ + β|1⟩
• Interpretation: 0 UND 1 gleichzeitig!
• Messung: Kollaps zu 0 (prob. |α|²) oder 1 (prob. |β|²)
• Parallelism: n Qubits = 2ⁿ Rechenpfade parallel!
• Trick: Interferenz so designen dass falsche Wege weg, richtige bleiben
Implementierungen:
• Photonen: Polarisation (leicht zu verstauen, schwer zu speichern)
• Ionen: Elektronische Zustände (lange Kohärenz!)
• Supraleitend: Josephson Junctions (schnelle Gatter)
• NMR: Kernspins (einfach aber limitiert)
• Topologisch: Anyons? (Theoretisch exzellent, praktisch schwer)
• Photonen: Polarisation (leicht zu verstauen, schwer zu speichern)
• Ionen: Elektronische Zustände (lange Kohärenz!)
• Supraleitend: Josephson Junctions (schnelle Gatter)
• NMR: Kernspins (einfach aber limitiert)
• Topologisch: Anyons? (Theoretisch exzellent, praktisch schwer)
3. Complexity
3. Komplexitätsklassen: BQP vs. NP
P (Polynomial Time):
• Probleme: Lösbar in Poly-Zeit klassisch
• Beispiel: Sortieren, GCD
• Größe: Schnell
• Probleme: Lösbar in Poly-Zeit klassisch
• Beispiel: Sortieren, GCD
• Größe: Schnell
NP (Non-deterministic Poly):
• Probleme: Verifizierbar in Poly-Zeit
• Beispiel: SAT, TSP, Faktorisierung
• Challenge: Vielleicht exponentiell zum Lösen
• Mystery: P = NP? (Million Dollar Problem!)
• Probleme: Verifizierbar in Poly-Zeit
• Beispiel: SAT, TSP, Faktorisierung
• Challenge: Vielleicht exponentiell zum Lösen
• Mystery: P = NP? (Million Dollar Problem!)
BQP (Bounded Error Quantum Poly):
• Probleme: Lösbar in Poly-Zeit quantenmechanisch
• Beispiel: Faktorisierung, Discrete Log (Shor!)
• Beziehung: BQP ⊆ PSPACE (nicht bekannt ob P=NP=BQP)
• Hoffnung: Viele NP-Probleme in BQP?
• Realität: Nur wenige bekannt (nicht so viele wie gehofft)
• Probleme: Lösbar in Poly-Zeit quantenmechanisch
• Beispiel: Faktorisierung, Discrete Log (Shor!)
• Beziehung: BQP ⊆ PSPACE (nicht bekannt ob P=NP=BQP)
• Hoffnung: Viele NP-Probleme in BQP?
• Realität: Nur wenige bekannt (nicht so viele wie gehofft)
4. Algorithms
4. Die großen Quantenalgorithmen
① Shor's Algorithmus (Faktorisierung):
• Problem: Faktorisiere N = pq (klassisch hart!)
• Quantum: Poly-Zeit möglich!
• Speedup: Exponentiell (klassisch exponentiell hart)
• Impact: RSA-Kryptographie würde brechen!
• Status: Theoretisch korrekt, praktisch noch nicht gemacht (Qubits zu wenig)
• Problem: Faktorisiere N = pq (klassisch hart!)
• Quantum: Poly-Zeit möglich!
• Speedup: Exponentiell (klassisch exponentiell hart)
• Impact: RSA-Kryptographie würde brechen!
• Status: Theoretisch korrekt, praktisch noch nicht gemacht (Qubits zu wenig)
② Grover's Algorithmus (Suche):
• Problem: Finde Lösung in Datenbank (N Einträge)
• Klassisch: O(N) Zeit
• Quantum: O(√N) Zeit!
• Speedup: Quadratisch (nicht exponentiell)
• Anwendung: Breitere Nutzung als Shor
• Problem: Finde Lösung in Datenbank (N Einträge)
• Klassisch: O(N) Zeit
• Quantum: O(√N) Zeit!
• Speedup: Quadratisch (nicht exponentiell)
• Anwendung: Breitere Nutzung als Shor
③ Variational Quantum Eigensolvers (VQE):
• Ziel: Finde Grundzustand Energie
• Hybrid: Klassisch-Quantum iterativ
• Nutzung: Molecular Simulation (praktisch relevant!)
• Status: Funktioniert auf heute's NISQ Geräten
• Impact: Chemie + Material-Wissenschaft Revolution?
• Ziel: Finde Grundzustand Energie
• Hybrid: Klassisch-Quantum iterativ
• Nutzung: Molecular Simulation (praktisch relevant!)
• Status: Funktioniert auf heute's NISQ Geräten
• Impact: Chemie + Material-Wissenschaft Revolution?
5. Supremacy
5. Quantum Supremacy: Mythos oder Realität?
Die Behauptung (Google, 2019):
• Sycamore: 53-Qubit Chip
• Problem: Random Circuit Sampling (künstlich!)
• Klassisch: 10,000 Jahre (IBM sagte: 2.6 Tage)
• Quantum: 200 Sekunden!
• Kritik: Praktisch nutzlos (nur Random Samples)
• Sycamore: 53-Qubit Chip
• Problem: Random Circuit Sampling (künstlich!)
• Klassisch: 10,000 Jahre (IBM sagte: 2.6 Tage)
• Quantum: 200 Sekunden!
• Kritik: Praktisch nutzlos (nur Random Samples)
Status 2025:
• Definitionen: "Quantum Advantage" besser
• Mehrere Claims: Google, China (Jiuzhang), IonQ
• Problem: Noch für künstliche Probleme
• Wirklich nützlich: Noch nicht demonstriert
• Hoffnung: VQE könnte nächste Milestone sein
• Definitionen: "Quantum Advantage" besser
• Mehrere Claims: Google, China (Jiuzhang), IonQ
• Problem: Noch für künstliche Probleme
• Wirklich nützlich: Noch nicht demonstriert
• Hoffnung: VQE könnte nächste Milestone sein
6. Future
6. 2025-2050: Quantencomputer-Roadmap
2025-2030: NISQ Era
• Qubits: 100-1000 (heute: max ~1000)
• Problem: Dekoheränz! Error Rates ~0.1-1%
• Use: Molecular Simulation, Optimization
• Reality: Nützlich aber begrenzt
• Ziel: Quantum Error Correction Anfang
• Qubits: 100-1000 (heute: max ~1000)
• Problem: Dekoheränz! Error Rates ~0.1-1%
• Use: Molecular Simulation, Optimization
• Reality: Nützlich aber begrenzt
• Ziel: Quantum Error Correction Anfang
2030-2040: Fault-Tolerant Era
• Qubits: 1 Million+ (mit Fehlerkorrektur)
• Quality: Error Rates < 10⁻⁶
• Anwendung: Echte praktische Probleme
• Shor: Endlich RSA-Faktorisierung möglich
• Revolution: Cyber-Security müsste neu werden
• Qubits: 1 Million+ (mit Fehlerkorrektur)
• Quality: Error Rates < 10⁻⁶
• Anwendung: Echte praktische Probleme
• Shor: Endlich RSA-Faktorisierung möglich
• Revolution: Cyber-Security müsste neu werden
2040-2050: Practical Quantum Advantage
• Breite Anwendung: Industrie überall
• Drug Discovery: Schnelle Molecular Design
• Optimization: Portfolio-Optimierung, etc
• Impact: Massiv für Forschung + Business
• Wahrscheinlich: 70% dass Realität
• Breite Anwendung: Industrie überall
• Drug Discovery: Schnelle Molecular Design
• Optimization: Portfolio-Optimierung, etc
• Impact: Massiv für Forschung + Business
• Wahrscheinlich: 70% dass Realität