Nicht lösbare Probleme/Quantencomputer?
Hallo,
ich habe kürzlich gelernt, dass „nicht lösbare Probleme“ in der theoretischen Informatik nicht von der aktuellen Rechnergeneration abhängig sind, sondern prinzipiell unlösbar.
Nun zu meiner Frage: Werden die unlösbaren Probleme auch weiterhin „zeitlos gültig“ sein im Hinblick auf die kommenden Quantencomputer?
Ich selbst bin nur oberflächlich mit der Thematik vertraut, aber ich hoffe hier einen Experten zu treffen.
3 Antworten
Die Tatsache, dass Quantencomputer durch Turing-Maschinen simulierbar sind, ist Beweis dafür, dass mit Hilfe von Quantencomputern auch nicht mehr berechenbar ist als mit Hilfe klassischer Computer.
Es ist einfach nur so, dass Quantencomputer zahlreiche Rechenaufgaben deutlich schneller erledigen können als es Computern mit klassischer Architektur möglich sein kann.
|
Informatiker gehen davon aus, dass berechenbar ist, was durch Turing-Maschinen berechenbar ist.
Man konnte beweisen: Es gibt mindestens eine universelle Turingmaschine (d.h. eine, die alles berechnen kann, was irgend eine Turingmaschine berechnen kann).
Quantencomputer sind aus theoretischer Sicht gar nicht soo weltbewegend, wie es manchmal den Anschein machen würde. Sie bieten keine neuen theoretischen Möglichkeiten, die nicht auch auf normalen Computern möglich wären. Berechnungen auf Quantencomputern lassen sich durch einfache Matritzenrechnung darstellen/simulieren. Der Trick ist nur, dass die Berechnungen nicht umständlich ausgeführt werden müssen, sondern die Quanten von sich aus einfach den Ergebniszustand annehmen.
Manche Dinge werden durch Quantencomputer sehr viel schneller gehen, für andere Probleme wird ein Quantencomputer keinen oder nur kaum einen Vorteil bringen. Und mathematisch unlösbare Probleme bleiben unlösbar. ;)
Quantencomputer können nichts anderes als aktuelle Computer auch. Sie können es nur schneller.
Relevant ist dies vor allem beim knacken von Verschlüsselungen da Verschlüsselungen darauf basieren dass die Zeit zum brute forcen astronomisch wäre.
Danke, also bleiben auch mit Quantencomputer die „nicht lösbaren“ Probleme nicht lösbar.