Abo
  • Services:
Anzeige
Versuchsanordnung mit grünem Laser, mit der Wiener Forscher das optische Quanten-Computing verbessert haben
Versuchsanordnung mit grünem Laser, mit der Wiener Forscher das optische Quanten-Computing verbessert haben (Bild: IQOQI Wien)

Was der Quantencomputer kann - und was nicht

Die einfachsten Aufgaben gehören dabei zu den P-Problemen. Das P steht für Polynomialzeit. Die nötige 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 von klassischen Computern effizient lösbar.

Anzeige

Formuliert man letztere Aufgabe aber etwas um, erreicht man schon die nächsthöhere Komplexitätsstufe: Gesucht sei eine Route, mit der ein Vertreter alle x 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 x der Städte - die Problemklasse nennt sich NP (nichtdeterministisch polynomial). Etwas einfacher ist bei NP-Problemen die Prüfung, ob ein Lösungsvorschlag tatsächlich korrekt ist: Dazu ist nur Polynomialzeit nötig, also genügt ein klassischer Computer.

Das Vertreter-Problem gehört, ebenso wie die beliebten Sudoku-Rätsel, zu einer speziellen Abteilung der NP-Probleme: Es ist "NP-vollständig". Solche Probleme haben die interessante Eigenschaft, dass jeder effiziente Algorithmus für eine dieser Aufgaben auch auf alle anderen übertragbar wäre. Schade nur, dass bisher kein einziger solcher Rechenweg bekannt ist... Gäbe es ihn, wäre das allerdings auch eine Revolution in der Mathematik.

Computer auf Zeitreise

Quantencomputer können einige, aber nicht alle NP-Probleme lösen. Vermutlich jedenfalls: Bisher konnte trotz eines Preisgelds von einer Million Dollar noch niemand streng mathematisch widerlegen, dass es nicht vielleicht doch einen effizienten, in Polynomialzeit einzusetzenden Algorithmus für NP-Probleme geben könnte, dass also P nicht gleich NP ist.

Eine weitere Problemklasse nennt sich PSPACE. Dazu gehören zum Beispiel vollständige Lösungen der Spiele Schach und Go. Sie enthält Probleme, zu deren Lösung man eine polynomial wachsende Speichermenge und exponentiell wachsende Rechenzeit benötigt. Aufgaben aus dem PSPACE sind klassischen Computern nicht zugänglich. Bei Quantencomputern ist man sich da nicht sicher. Bisher ist aber kein dazu fähiger Algorithmus bekannt.

Könnte es einen Computertyp geben, der dem Quantencomputer überlegen ist? Dazu bräuchte man neue physikalische Prinzipien, von denen heute noch nichts bekannt ist. Forscher schlagen zum Beispiel vor, den Computer auf eine Zeitreise zu schicken. Das Prinzip: Man schickt den Computer einfach so lange und so oft in die Vergangenheit, bis das Problem zum heutigen Zeitpunkt gelöst ist. Dazu bräuchte man die Existenz sogenannter geschlossener zeitartiger Kurven (closed timelike curves, CTCs), die sich als mögliche Lösung der Allgemeinen Relativitätstheorie ergeben. Damit arbeitende Computer könnten sogar Probleme der Klasse PSPACE effizient lösen. Physiker vermuten allerdings, dass CTCs von einer künftigen Vereinigung von Quanten- und Relativitätstheorie wieder ausgeschlossen werden.

Das E-Book "Die faszinierende Welt der Quanten" des Autors ist bei Beam-eBooks (DRM-frei, ePub, PDF, Mobi), bei Amazon (Mobi) und Apple (iPad-Version mit Videos und Fotos) erhältlich.

 Topologische Quantencomputer

eye home zur Startseite
Zeitvertreib 15. Aug 2014

Sorry ich glaube soweit bist du noch nicht ;) Nicht böse gemeint aber um Einstein weiter...

NilsP 18. Jul 2014

Also, gaaanz genau sind es 3,12 Mio Kerne (16.000 Knoten je 2 Ivy Bridge Xeons (12C) + 3...

crmsnrzl 07. Jul 2014

Falsch, man kann nur nicht beides GLEICHZEITIG mit beliebiger Genauigkeit wissen.

Flö. 07. Jul 2014

Die Illuminaten natürlich! SCNR :D

Citadelle 07. Jul 2014

Hallo Ich finde das mit den Problemklassen sehr interessant. Also P und NP Problematiken...



Anzeige

Stellenmarkt
  1. Groz-Beckert KG, Albstadt
  2. LogPay Financial Services GmbH, Eschborn
  3. BG-Phoenics GmbH, München
  4. cyberTECHNOLOGIES über ACADEMIC WORK, München, Eching-Dietersheim


Anzeige
Top-Angebote
  1. 70,02€
  2. 99,90€ + 4,95€ Versand (Vergleichspreis 124€)
  3. 229,00€ zzgl. 5€ Versand (USK 18)

Folgen Sie uns
       


  1. Hauptversammlung

    Rocket Internet will eine Bank sein

  2. Alphabet

    Google-Chef verdient 200 Millionen US-Dollar

  3. Analysepapier

    Facebook berichtet offiziell von staatlicher Desinformation

  4. Apple

    Qualcomm reduziert Prognose wegen zurückgehaltener Zahlungen

  5. Underground Actually Free

    Amazon beendet Programm mit komplett kostenlosen Apps

  6. Onlinelexikon

    Türkische Behörden sperren Zugang zu Wikipedia

  7. Straßenverkehr

    Elon Musk baut U-Bahn für Autos

  8. Die Woche im Video

    Mr. Robot und Ms MINT

  9. Spülbohrverfahren

    Deutsche Telekom "spült" ihre Glasfaserkabel in die Erde

  10. Privacy Phone

    John McAfee stellt fragwürdiges Smartphone vor



Haben wir etwas übersehen?

E-Mail an news@golem.de


Anzeige
Elektromobilität: Wie kommt der Strom in die Tiefgarage?
Elektromobilität
Wie kommt der Strom in die Tiefgarage?
  1. e.GO Life Elektroauto aus Deutschland für 15.900 Euro
  2. Elektroauto VW testet E-Trucks
  3. Elektroauto Opel Ampera-E kostet inklusive Prämie ab 34.950 Euro

In eigener Sache: Die Quanten kommen!
In eigener Sache
Die Quanten kommen!
  1. In eigener Sache Golem.de führt kostenpflichtige Links ein
  2. In eigener Sache Golem.de sucht Marketing Manager (w/m)
  3. In eigener Sache Golem.de geht auf Jobmessen

Snap Spectacles im Test: Das Brillen-Spektakel für Snapchat-Fans
Snap Spectacles im Test
Das Brillen-Spektakel für Snapchat-Fans
  1. Kamera Facebook macht schicke Bilder und löscht sie dann wieder
  2. Snap Spectacles Snap verkauft Sonnenbrille mit Kamera für 130 US-Dollar
  3. Soziales Netzwerk Snapchat geht an die Börse - und Google profitiert

  1. Re: 40.000 EUR.

    Unix_Linux | 02:23

  2. Re: 1 Dollar Gehalt

    Sharra | 01:55

  3. Re: Mrs. ist verheiratet - korrekt wäre Ms oder Ms.

    PlonkPlonk | 01:54

  4. Re: Kein Mensch ist 200 Mio. Dollar/Euro Wert

    Sharra | 01:41

  5. Re: Lieber das U-Bahnnetz ausbauen!

    Luke321 | 01:10


  1. 13:08

  2. 12:21

  3. 15:07

  4. 14:32

  5. 13:35

  6. 12:56

  7. 12:15

  8. 09:01


  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