Abo
  • Services:
Anzeige
Quantencomputer von IBM: Sind Quantencomputer herkömmlichen überlegen?
Quantencomputer von IBM: Sind Quantencomputer herkömmlichen überlegen? (Bild: IBM/CC-BY 2.0)

Was kann ein Quantencomputer? Was nicht?

Bei allen Schwierigkeiten handelt es sich um eine Technologie, die man beherrscht, in die Abermilliarden an Investitionen geflossen sind. Bis ein Quantencomputer wirklich mal auch in der Praxis leistungsfähiger als ein gleich teurer (!) klassischer Rechner ist, dürften noch einige Jahre vergehen. Deshalb leisten sich derzeit vor allem die Forschungsabteilungen großer IT-Unternehmen Quantencomputer, um daran mögliche Zukunftskonzepte zu studieren.

Anzeige

Die prinzipiellen Grenzen

Der Quantencomputer ist ganz sicher kein Wundermittel, das ist den Forschern heute klar. Es gibt Probleme, bei denen er theoretisch jeden klassischen Computer schlägt, etwa bei der Primzahlfaktorisierung oder Suchalgorithmen. Mathematisch lässt sich zeigen, dass der Quantencomputer schneller ist als ein klassischer Rechner bei all den Problemen, die sich durch Ausprobieren lösen lassen, wobei es keinerlei Hinweise darauf gibt, mit welcher Wahrscheinlichkeit eine bestimmte Lösung auftritt. Das perfekte Beispiel dafür ist das Erraten eines Passworts.

Es gibt aber auch Verschlüsselungsverfahren, gegen die man einen Quantencomputer nicht besonders erfolgreich einsetzen kann. So wurde etwa bereits nachgewiesen, dass er beim AES-Protokoll lediglich die Schlüssellänge effektiv halbiert. Ein aus 256 Bit bestehender Schlüssel ist gegen einen Angriff mit einem Quantencomputer also genauso effizient wie ein 128 Bit langer Schlüssel gegen einen klassischen Computer.

Welche Probleme ein Quantencomputer prinzipiell lösen kann, lässt sich mit Hilfe eines Teilgebiets der Mathematik diskutieren, der Komplexitätstheorie. Die Frage ist: Wie lange braucht der Rechner für die Lösung - einerseits - und für das Nachprüfen der Lösung - andererseits.

P-Probleme kann auch ein normaler Computer lösen

Die einfachsten Aufgaben gehören dabei zu den P-Problemen ("Polynomialzeit"). Die Rechenzeit wächst hier proportional zu einer festen Potenz der Problemgröße. Die Frage, ob eine Zahl eine Primzahl ist, gehört ebenso zu dieser Klasse wie der Check, ob auf einer Straßenkarte jede von x Städten von jeder anderen aus zu erreichen ist. Aufgaben dieser Komplexität sind schon von klassischen Computern effizient lösbar, Quantencomputer werden hier nicht benötigt.

Formuliert man die Aufgabe um, erreicht man die nächsthöhere Komplexitätsstufe "nichtdeterministisch polynomial" oder "NP": Gesucht sei eine Route, mit der ein Vertreter alle Städte auf kürzestem Weg abklappern kann, ohne einen Ort zweimal zu besuchen. Die zur Lösung dieses Problems nötige Rechenzeit wächst exponentiell mit der Zahl der Städte. Einfacher ist bei NP-Problemen die Prüfung, ob ein Lösungsvorschlag korrekt ist: Dazu ist nur Polynomialzeit nötig. Quantencomputer können einige, aber nicht alle NP-Probleme lösen. Welche genau? Das ist noch offen, genau wie die Frage, ob es nicht doch einen in Polynomialzeit funktionierenden Algorithmus für NP-Probleme gibt. Falls Sie die Antwort beweisen können, egal wie sie lautet, bringt Ihnen das eine Million Dollar Preisgeld ein. Falls Sie den Algorithmus finden, machen Sie sich all die Hersteller zum Feind, die auf Quantencomputer setzen, denn die würden dann nicht mehr gebraucht.

Denn bei Problemen noch höherer Komplexität versagen wahrscheinlich auch sie, wobei "versagen" nicht das richtige Wort ist - sie kennen dann nur keine Abkürzung zum Ziel. Dazu gehören zum Beispiel vollständige Lösungen der Spiele Schach und Go, die man in die Klasse PSPACE einordnet: Probleme, für deren Lösung man zum einen eine polynomial wachsende Speichermenge und zum anderen exponentiell wachsende Rechenzeit braucht. Bei Aufgaben dieser Stufe stoßen klassische Computer schnell an Grenzen. Wie es sich bei Quantencomputern verhält, ist unbekannt - jedenfalls hat noch niemand einen Quantenalgorithmus dafür gefunden.

Die Quanten kommen: spannende Expertenvorträge und Paneldiskussionen rund um Quantencomputer, Quantennetzwerke, Quanten - und Postquantenverschlüsselung auf der ersten eigenen Golem.de-Konferenz am 23. Juni 2017 in Berlin. Jetzt Ticket sichern!

 So ein Quantencomputer ist anders

eye home zur Startseite
Apfelbrot 26. Apr 2017

Oder als Bild abspeichern!

Apfelbrot 26. Apr 2017

Es gibt maximal 21 Millionen, richtig. Alle 210.000 Coins wird die Belohnung für einen...

Prinzeumel 26. Apr 2017

Nicht so arg viel.

chithanh 25. Apr 2017

Einige der Aussagen im Artikel zu Krypto- und Komplexitätsthemen sind etwas ungenau...

DerSchildkröten... 25. Apr 2017

Mit dem Gefühl überfordert zu sein bezogen auf die Komplexitätstheorie sind sie nicht...



Anzeige

Stellenmarkt
  1. Oemus Media AG, Leipzig
  2. MVV EnergySolutions GmbH, Mannheim
  3. über Nash Direct GmbH, München/Ismaning
  4. item Industrietechnik GmbH, Solingen


Anzeige
Blu-ray-Angebote
  1. Einzelne Folge für 2,99€ oder ganze Staffel für 19,99€ kaufen (Amazon Video)
  2. 29,99€ (Vorbesteller-Preisgarantie)
  3. (u. a. Reign, Person of Interest, Gossip Girl, The Clone Wars)

Folgen Sie uns
       


  1. Smartphones

    Broadpwn-Lücke könnte drahtlosen Wurm ermöglichen

  2. Docsis 3.0

    Huawei erreicht 1,6 GBit/s mit altem Kabelnetzstandard

  3. Tasty One Top

    Buzzfeed stellt vernetzte Kochplatte vor

  4. Automated Valet Parking

    Lass das Parkhaus das Auto parken!

  5. Log-in-Allianz

    Prosieben, GMX und Zalando starten Single-Sign-on-Dienst

  6. Andreas Kaufmann

    Leica-Chef träumt vom eigenen Kamera-Smartphone

  7. Elektromobilität

    Porsche kommt in die Formel E

  8. Keylogger

    Arbeitgeber dürfen Mitarbeiter nicht generell ausspähen

  9. Schulden

    Toshiba-Partner und Geldgeber wollen Insolvenzverfahren

  10. Sysadmin Day 2017

    Zum Admin-Sein fehlen mir die Superkräfte!



Haben wir etwas übersehen?

E-Mail an news@golem.de


Anzeige
Shipito: Mit wenigen Mausklicks zur US-Postadresse
Shipito
Mit wenigen Mausklicks zur US-Postadresse
  1. Kartellamt Mundt kritisiert individuelle Preise im Onlinehandel
  2. Automatisierte Lagerhäuser Ein riesiger Nerd-Traum
  3. Onlineshopping Ebay bringt bedingte Tiefpreisgarantie nach Deutschland

Indiegames Rundschau: Meisterdiebe, Anti- und Arcadehelden
Indiegames Rundschau
Meisterdiebe, Anti- und Arcadehelden
  1. Jump So was wie Netflix für Indiegames
  2. Indiegames-Rundschau Weltraumabenteuer und Strandurlaub
  3. Indiegames-Rundschau Familienflüche, Albträume und Nostalgie

Mercedes-Benz: "In einer perfekten Zukunft brauchen wir keine VR-Gehhilfen"
Mercedes-Benz
"In einer perfekten Zukunft brauchen wir keine VR-Gehhilfen"
  1. Remote Control Serienklassiker Das Boot wird VR-Antikriegsspiel
  2. Digility VR kann helfen, Vorurteile abzubauen
  3. Würfel Google zeigt experimentelles Werbeformat für Virtual Reality

  1. Re: iPod Touch ist kein Ersatz

    feierabend | 12:42

  2. Re: Preis/Leistungsverhältnis ähnlich zum G4560...

    windbeutel | 12:41

  3. Re: Gut gebrüllt Löwe!

    Richy-Holly | 12:41

  4. Re: Da sind die Admins selbst dran schuld

    rldml | 12:40

  5. Re: Sicherheit für Fußgänger?

    .02 Cents | 12:40


  1. 13:00

  2. 12:45

  3. 12:29

  4. 11:58

  5. 11:47

  6. 11:34

  7. 11:20

  8. 11:06


  1. Themen
  2. A
  3. B
  4. C
  5. D
  6. E
  7. F
  8. G
  9. H
  10. I
  11. J
  12. K
  13. L
  14. M
  15. N
  16. O
  17. P
  18. Q
  19. R
  20. S
  21. T
  22. U
  23. V
  24. W
  25. X
  26. Y
  27. Z
  28. #
 
    •  / 
    Zum Artikel