Vieweg+Teubner eBooks

Vom Bit zum Quantenregister

Published Feb 11, 2009• 0 citations

Abstract

Dieses Kapitel ist das Fundament für alle weiteren. Wir studieren Quantenbits und die Rechenschritte eines Quantencomputers und erfahren, was Messen und Verschränkung bedeuten. Dabei wenden wir diese Begriffe sofort an und lernen die ersten Algorithmen kennen, und zwar für Probleme, bei denen der Quantencomputer klassischen Rechnern überlegen ist. Als klassisch bezeichnen wir alles, was sich verhält, wie wir es aus unserer Alltagswelt gewohnt sind. Davon unterscheiden wir die nichtklassischen Phänomene der Quantenwelt.

DOI: 10.1007/978-3-8348-9241-6_2

Related papers

Hilfsmittel aus der Theoretischen Informatik

AuszugBei welchen Aufgaben sind Quantencomputer klassischen Rechnern überlegen? Gibt es Probleme, die für letztere schwer, für erstere aber einfach sind? Dieses Kapitel führt in aller Kürze in die Komplexitätstheorie ein, die danach fragt, welche Probleme effizient lösbar sind. Diese Theorie hilft uns auch dabei, über die Grenzen des Quantencomputers nachzudenken. Die Betrachtung schließt direkt an die Abschnitte 3.1 und 3.2 an.

Vieweg+Teubner eBooksFeb 11, 20090 citations

Quantencomputer

David Deutsch

Vermutlich ist der Begriff Quantencomputer für viele Leser noch sehr neu. Man könnte dabei an eine neue Technologie denken — vielleicht die jüngste und modernste in der bemerkenswerten Folge, zu der die Berechnung mit Transistoren, integrierten Schaltkreisen oder Siliziumchips gehört. Und es stimmt, auch die schon vorhandene Computertechnologie beruht weitgehend auf mikrophysikalischen quantenmechanischen Prozessen. Wenn sich der Hang zu immer schnellerer, kompakterer Computer-Hardware fortsetzen soll, muß die Technologie immer «quantenmechanischer» werden, weil quantenmechanische Effekte in allen kleinen Systemen überwiegen. Aber wenn das alles wäre, würden Quantencomputer bei grundlegenden Erklärungen in diesem Zusammenhang kaum eine Rolle spielen. Unabhängig davon, welche quantenmechanischen Vorgänge heutige Computer zur Durchführung der Berechnungen nutzen, sie sind alle technologische Verwirklichungen desselben klassischen Grundgedankens, nämlich der universellen Turingmaschine. Deshalb können alle existierenden Computer im wesentlichen dieselben Berechnungen ausführen. Sie unterscheiden sich lediglich in bezug auf die Geschwindigkeit, Speicherfähigkeit und die Modi der Verarbeitung der Eingaben. Selbst ein langsamer Computer mit wenig Speicherplatz läßt sich so programmieren, daß er jedes Problem genausogut lösen und jede Umwelt genausogut simulieren kann wie unsere leistungsfähigsten Computer, wenn nur der Speicherplatz reicht, er lange genug laufen kann und ihm die Hardware zur Verfügung steht, auf der er die Ergebnisse darstellen kann.

Birkhäuser Basel eBooksJan 1, 19960 citations

Zur Lösung von zahlentheoretischen Problemen mit klassischen und Quantencomputern

Schmidt, Arthur

In dieser Arbeit werden Algorithmen zur Lösung zahlentheoretischer Probleme für klassische Computer und Quantencomputer entwickelt und analysiert sowie ihre Auswirkungen auf Public-Key-Kryptosysteme untersucht. Im Jahr 1994 veröffentliche Shor einen Quantenalgorithmus [Shor, 1994], der das Periodengitter einer gegebenen Funktion in Quanten-Polynomzeit bestimmt. Mit diesem Algorithmus läßt sich das Faktorisierungs- und das Diskreter-Logarithmus-Problems in endlichen abelschen Gruppen in Quanten-Polynomzeit lösen. Dadurch werden die meisten heutzutage verwendeten Public-Key-Kryptoverfahren unsicher, sollten hinreichend große Quantencomputer eines Tages gebaut werden können. Der erste Quantencomputer wurde 1998 gebaut [Chuang/Vandersypen/Zhou/Leung/Lloyd, 1998]. Er bestand aus zwei Qubits. Der größte Quantencomputer, der bis heute gebaut wurde, besteht aus nur sieben Qubits [Vandersypen/Steffen/Breyta/Yannoni/Sherwood/Chuang, 2001]. Es hat sich herausgestellt, daß das Bauen von großen Quantencomputern ein extrem schwieriges Problem ist. Aus diesem Grund kann davon ausgegangen werden, daß die Größe der Quantencomputer, d.h. die Anzahl der Qubits, aus denen ein Quantencomputer besteht, nur langsam wachsen wird. Deshalb ist es von Interesse, Shors Quantenalgorithmus an verschiedene abelsche Gruppen sowie gruppenähnliche Strukturen zu adaptieren und ihre genaue Komplexität zu untersuchen, um daraus die Bedrohungen für die betroffenen Kryptosysteme genau zu bestimmen. In dieser Arbeit werden Quantenalgorithmen zur Lösung des Ordnungsproblems und des DL-Problems in der Klassengruppe der Ideale eines imaginär-quadratischen Zahlkörpers angegeben und ihre Komplexität, d.h. die Anzahl der Qubits und der elementaren Quantenoperationen, bestimmt. Darüberhinaus werden Algorithmen zur Bestimmung des Regulators und zur Lösung des Hauptidealproblems und des erweiterten Diskreter-Logarithmus-Problems in reell-quadratischen Zahlkörpern präsentiert. Shors Algorithmus wird dabei auf Funktionen angewendet, die nicht injektiv innerhalb einer Periode sind. Auch in diesem Fall wird die Komplexität der Algorithmen genau bestimmt. Im Falle von Zahlkörpern eines beliebigen Grades wird eine weitere Modifikation von Shors Algorithmus entwickelt: Es wird das Periodengitter einer Funktion bestimmt, deren Periodengitter irrational ist. Dieser Algorithmus wird benutzt, um die Einheitengruppe eines beliebigen endlich-dimensionalen Zahlkörpers zu berechnen. Als nächstes werden die Auswirkungen von Quantenalgorithmen auf die Sicherheit von Public-Key-Kryptosystemen untersucht. Es wird ein neuer Sicherheitsbegriff eingeführt. Die Sicherheit zweier Kryptosysteme wird als gleich definiert, wenn die Anzahl der Qubits zum Brechen dieser Kryptosysteme gleich ist. Basierend auf der neuen Sicherheitsdefinition wird die Geschwindigkeit und die Schlüsselgröße von einigen Kryptosystemen verglichen. Im letzten Kapitel wird ein deterministischer klassischer Algorithmus zur Berechnung der Struktur einer endlichen abelschen Gruppe aus einem Erzeugendensystem präsentiert, dessen Laufzeit nur linear von der Anzahl der gegebenen Erzeuger abhängt und dessen Speicherplatzkomplexität unabhängig von der Anzahl der gegebenen Erzeuger ist. Das stellt eine exponentielle Verbesserung zu früheren Algorithmen dar, bei denen sowohl die Laufzeit als auch die Speicherplatzkomplexität exponentiell von der Anzahl der Erzeuger im gegebenen Erzeugendensystem abhängt [Buchmann/Jacobson/Teske, 1997].

Jan 1, 20081 citation

Robert‐Wichard‐Pohl‐Preis: Licht — ein Fenster in die Quantenwelt: Experimente mit Photonen gewähren Einblick in Komplementarität und Nichtlokalität in der Quantenphysik

Wolfgang Tittel, W. Martienssen

Abstract Licht ist das Elixier unseres Lebens: Das Licht der Sonne spendet uns Energie; Licht gibt uns die Möglichkeit zu sehen und über den Lichtsinn mit unserer Umgebung zu kommunizieren; Licht, das vom Himmel kommt, gibt uns wegen seiner endlichen Ausbreitungsgeschwindigkeit Einblicke in die Frühzeit und in die Evolution unseres Universums. Was ist aber das Wesen des Lichtes, wie verhält sich das Licht, wenn wir es auf Photonen‐Ebene betrachten, was vermag uns das Licht über die Quantenwelt und ihre Phänomene erkennen zu geben und wie unterscheiden sich diese Phänomene von denen der klassischen Welt unserer alltäglichen Erfahrung? Hier wollen wir versuchen, mithilfe ausgewählter Experimente Antworten auf diese Fragen direkt aus der Beobachtung zu erschließen.

Physikalische BlätterJul 1, 20015 citations

Wie rechnen Quanten?

Vor einigen Jahren war viel von Quantencomputern zu hören, inzwischen ist es etwas stiller darum geworden. Das liegt daran, dass solche Computer zwar unglaubliche Leistungen vollbringen könnten, wenn man sie denn in der erforderlichen Komplexität bauen könnte, doch muss man zurzeit wohl pessimistisch sein, dass das jemals geschehen wird.

Vieweg eBooksJan 1, 20060 citations

Fernwirkung Fließen Gefühle und Gedanken in der Quantenwelt?

Joachim Müller-Jung

Nicht einmal Albert Einstein mochte die Welt für so verrückt halten. Für ihn war es Spuk, nicht mehr und nicht weniger, was sich die Quantenmechanik da ausgedacht hatte. »Verschränkte« Teilchen. Absolut getrennt und dennoch permanent verbunden. Egal, wie weit die Teilchen voneinander entfernt sind, wenn wir das eine messen, kennen wir den Wert des anderen. Verändern wir den Drehimpuls des einen oder dessen Polarisation, ändert sich die Eigenschaft des anderen Teilchens entsprechend. Und zwar augenblicklich und, wenn es sein muss, über tausende Kilometer Entfernung. Es fließt kein Strom, kein Licht, keine Information, nichts, was diese »spukhafte Fernwirkung« mit der klassischen Physik erklären oder messen könnte. Fest steht nur: Sie ist inzwischen unabweisbar. Die Verschränkung der Quantenzustände von Teilchen ist in den letzten Jahrzehnten zu einem Thema mit geradezu soziokultureller Sprengkraft geworden; denn in dem Phänomen steckt womöglich der Schlüssel für prinzipiell abhörsichere superschnelle Quantencomputer, die von nichts und niemandem geknackt werden können. Was aber, wenn es das Phänomen — oder ein prinzipiell ähnliches — nicht nur in der Quantenwelt gibt, sondern es ein Teil der Evolution ist und ins Leben eingreift?

J.B. Metzler eBooksJan 1, 20150 citations