Kategorie: Theoretische Informatik

vollständiger graph

Eine vollständige Graph ist ein Begriff auf dem Gebiet der Graphentheorie und stellt ein einfaches Diagramm, in dem alle Knotenpaaren mit einer Kante verbunden sind. Diese Diagramme spielen eine wichtige Rolle in der Graphentheorie.

Ein vollständiger Graph K n ist eine nicht orientierte Graph mit n Scheitelpunkten und{\ Anzeigeart {n \ wählen 2} = {\ frac {n (n-1)} {2}}} Kanten.

Beispiele

Die folgende Tabelle zeigt Diagramme von kompletten Graphen , K n für n zwischen 1 und 8, sowie der Anzahl der Kanten in jedem.

Gerichtete azyklische Graph

Ein gerichteter azyklischer Graph (Eng. Gerichteter azyklischer Graph , bekannt heute oder DAG ), ist in der Informatik und die Mathematik einen gerichteter Graphen ohne Flügel Kreise . Das heißt, für jeden Knoten v , gibt es keine nicht leere -orientierten Pfad , der beide beginnt und endet in v .

Terminologie

Eine Quelle (Source) ist ein Knoten ohne ankommende Kanten , während eine Senke ein Knoten ohne ausgehenden Kanten ist. Eine abschließende DAG mindestens eine Quelle und mindestens ein Waschbecken.

Die Länge eines letzten Tag, die Länge (Anzahl der Kanten) des längsten orientierten Pfad.

Seven Bridges von Königsberg

Seven Bridges von Königsberg oder Königs broproblem ist ein berühmtes mathematisches Problem, das von der Realität inspiriert ist. Der Fluss Pregel geht durch die Stadt Königsberg (heute Kaliningrad ) und insgesamt sieben Brücken , die die beiden Seiten der Stadt zusammen und mit zwei Inseln in der Mitte des Flusses. Die Frage ist , ob es möglich ist , einen Spaziergang durch die Stadt zu nehmen, so dass Sie genau einmal jede Brücke gehen.

Eulers Lösung

Euler bewies 1736 , dass es nicht getan werden könnte. Als er es bewiesen, neu formuliert er das Problem auf ein Diagramm teoretisk Problem. Er erkannte , dass Land und die Brücken Form hatte keine Wirkung und ersetzt die ländlichen Gebiete mit Punkten und verbanden sie mit Linien (auch genannt Kanten). repräsentiert die Brücken.

Die Form eines Diagramms kann geändert werden, wie Sie möchten, ohne die grafische Darstellung ändern, solange die Kanten zwischen den Knoten gleich sind. Dabei spielt es keine Rolle, ob die Kanten zwischen den Punkten gleich sind, oder wenn ein Hub nach rechts oder links von einem anderen befindet.

Euler erkannte , dass das Problem durch lediglich betrachten gelöst werden könnte die Wertigkeit des Knoten, das heißt die Anzahl der Kanten , die in einem Knoten Endpunkt haben. In der graphischen Darstellung der Königs Brücken hat drei Knoten Wertigkeit 3, während ein Knoten Wertigkeit hat 5. Euler bewiesen , dass es ein Weg ist , die nur einmal über alle Kanten geht, wenn und nur wenn der Graph ist konsistent , und nur zwei oder gar keine Knoten hat ungeradee Wertigkeit. Solch eine Strecke heute eine genannter Euler – Tour . Es gilt auch , dass , wenn es zwei Knoten mit ungerader Wertigkeit sind, dann diese beiden Punkte zu beginnen und Endknoten der Euler – Tour. Wie der Graph von Brücken Königs vier Knoten ungerader Wertigkeit enthält, gibt es keine Euler – Tour von Königsberg Brücken.

Dies kann mit einem konkreten Beispiel erläutert werden: Die östliche Insel verfügt über drei Brücken. Wenn Sie auf die Insel über eine Brücke kommen, müssen Sie es über die zweite oder dritte Brücke verlassen. Wenn Sie die zweite wählen, können Sie später Rückkehr des dritten, aber wie bekommt man so weit? Wir haben nun über die drei Brücken genau einmal jede und sind nun auf der Insel weg, aber ist nicht das Ziel. Um zum Ziel zu bewegen auf, ist es daher notwendig, die entlang einem der drei Brücken fortzusetzen, aber so überquert zweimal die gegebene Brücke, die gerade nicht wollte. Muss Wunsch erfüllt ist eine vierte untrodden Brücke notwendig, aber eine solche nicht existiert.

Auswirkungen auf die Geschichte der Mathematik

Eulers Lösung Königs broproblem gilt als der erste Satz in der Graphentheorie sein. Darüber hinaus ist es interessant , dass Euler erkannte , dass es nicht die Brücken genaue Lage war, aber was sie zugeordnet ist , war wichtig. Das erinnert nämlich an den Gedanken hinter Topologie , die später erfunden wurde.

Die Brücken heute

Die westlichen O`s zwei Brücken mit dem Festland wurde während einer britischen Bombardierung von Konigsberg während zerstört dem Zweiten Weltkrieg , während die Russen später die beiden westlichen mit einem modernen højgade ersetzt. Die drei anderen Brücken noch existieren, obwohl man von den Deutschen im Jahr 1935. Insgesamt wieder aufgebaut wurde gibt es nun fünf Brücken von Königsberg.

Konvertierte Grafik verfügt über zwei Punkte (Flußufer) jetzt Wertigkeit 2 und die beiden anderen (die Inseln) Wertigkeit 3. Es ist nun möglich , einen Spaziergang zu machen, wo man jede Brücke genau einmal eintritt. Doch die , egal was immer auf einer Insel beginnen und auf der anderen Seite zu beenden. Eine Tour ist noch nicht möglich. [1]

Schaltung (Grafik)

Eine Schaltung (Eng. Zyklus ) in einem Graphen ist eine Liste des n verschiedene Ecken v 1 , v 2 , v 3 , …, v n-1 , V n , wobei jeder Knoten v in der Liste durch angeschlossen ist. eine Kante mit dem benachbarten Knoten v i + 1 und wird weiter Knoten V nRand verbunden V 1 . Die Länge eines Kreises ist die Anzahl der Knoten in der Liste, wobei jede Schaltung Länge ≥ 3 . Graphs Schaltung der Länge N wird oft bezeichnet C n . Auf der Figur wird Zeichnungen des ersten gesehen C n Diagramme:

Knud Färbung

Knud Coloring ein Graph bezieht sich auf die Zuweisung von Farben für die Graph – Knoten derart , dass zwei beliebige Kante verbundenen Knoten haben unterschiedliche Farben – dies wird als eine richtige Knoten Färbung. Es ist klar , dass für einen beliebigen Graph tatsächliche knudefarvninger sind, nämlich von jedem Knoten eine separate Farbe zugewiesen wird . Die Farben specifieres bei einer Ansicht φ: V → F , wobei F , beispielsweise einen Teil der sein kann natürlichen Zahlen . φ (v) ist v ∈ V gegebene Farbe in dem V von Knoten in dem Graph mænden wird. Die minimale Anzahl von Farben in einer aktuellen Knoten Färbung eines Graphen G wird , um die genannte chromatische Zahl oder die knudekromatiske Zahlen , für die G und es wird bezeichnet χ (G) .

Beispiele für die Knotenfärbung für verschiedene grafische Darstellungen

  • Die vollständigen Graphen K n haben alle chromatischen Figuren χ (K n ) = n , wobei n eine natürliche Zahl ist. Wenn beliebiger unterschiedlicher Knoten in K n Rand verbunden ist, damit jeder Knoten seine eigene Farbe hat.
  • Ein Graph G hat einen leeren Kantenbetrag nur dann , wenn der Knoten mit einer einzigen Farbe gefärbt werden kann; d.h. χ (G) = 1 . Ein solches besteht ein Graph nur eines Knotens.
  • Eine Gruppe C n eines aus gleicher Anzahl von Knoten (und Kanten), die chromatische Abbildung 2. Die Anfärbung des 2 , indem die Farben wechseln sich entlang der Schaltung erhalten Graph, d.h. Verwenden Sie die Farben abwechselnd (siehe Abbildung). Während eine Gruppe C n einer ungeraden Anzahl von Knoten (und Kanten) chromatische Zahl hat 3. Wenn Sie versuchen , das Diagramm , um Farbe durch die zwei Farben wechseln sich entlang der Rennstrecke zu lassen, werden Sie feststellen , dass der letzte Knoten werden mit zwei Kanten farbig verbunden sind , Endknoten haben verschiedene Farben. Dass dieser Knoten mit einer dritten Farbe entsprechend die Definition einer geeigneten Kantenfärbung gefärbt werden.

Kante Coloring

Kantenfärbung ein Graph bezieht sich auf die Zuweisung von Farben zu den Graphkanten in einer solchen Weise , dass alle Kanten mit gemeinsamen Endknoten verschiedenen Farben zugeordnet ist – dies ist ein aufgerufen wird richtige Kantenfärbung . Es gibt immer solche Farbzuweisungen an die Kanten eines Graphen, zum Beispiel. mit einer getrennten Farbe zu jeder Kante. Eine Farbzuordnung kann durch angegeben werden Mapping E →: φ F für eine geeignete Farbmenge F , zum Beispiel. ein Teil der natürlichen Zahlen , wobei e von Kanten in dem Graphen mænden.

Es kantkromatiske Nummer eines Graphen G die minimale Anzahl von Farben in einer geeigneten Kantenfärbung ist G . Diese Größe ist bezeichnet & khgr; ‚(G) (χ ist ein griechisches wenig KHI) Es gibt mindestens Δ (G) verschiedene Farben in einem tatsächlichen Kante Färben enthalten, wobei Δ (G) , um die repräsentiert maximale Knoten Valenz von G . Dies ist offensichtlich, da die Kanten an den Knoten mit maximaler Wertigkeit verbunden ist , müssen verschiedene Farben haben.

Ein Hauptergebnis der Kanten Färben – Vizings Satz sagt , daß jeder Graph G gefärbt Kante Δ (G) + 1 Kante Farben. Dieses Ergebnis zeigt daher , daß die dargestellte Graph entweder Kante mit Δ (G) oder Δ (G) + 1 Kante Farben gefärbt werden kann.

Euler-Tour

Eine Fahrt in einem Diagramm namens eine Euler – Tour , wenn sie alle Kanten in dem Diagramm enthält. (Die Kanten einer Reise ist voneinander verschieden.)

Ein Diagramm, in dem eine Euler-Tour geschlossen ist ein Euler Graph bezeichnet.

Das Konzept der Euler – Tour ist mit zugehörigem Leonhard Euler , den Berichten zufolge untersucht , ob es möglich war , eine Wanderung von Königsberg / zu organisieren Kaliningrad , die die Stadt Brücken bestand genau einmal jeder. Dieses Problem wird genannt Königs broproblem

Verification (Bestätigung)

Überprüfung ist eine Bestätigung oder Studie , die Richtigkeit des etwas bestätigt spezifisch .

Ein Beispiel festgestellt , dass im Zusammenhang mit den Fest – und Software – Systeme überprüft werden müssen , dass die verwendeten Algorithmen Anforderungen erfüllen.

Lambdakalkyle

Lambdakalkyle (auch Lambdakalkyle oder Lambda – Kalkül ) ist ein formales System innerhalb der mathematischen Logik . Das System bietet eine formale Notation zur Definition von Funktionen durch eine Reihe von ungebundenen Variablen ausgedrückt. Das System und die entsprechende Schreibweise wurden ursprünglich von dem amerikanischen Erfinder Mathematiker Alonzo Church in den 1930er Jahren als Werkzeug in der Erforschung der Grundlagen der Mathematik. Das System kann auch als eine grundlegende Notation für gedacht werden Computerprogrammierung und damit treffen Informatik . Eine Reihe von Programmier namens funktionalen Sprachen implementiert verschiedene mechanische Interpretationen von lambdakalkylen, zum Beispiel. Lisp , aber diese haben bis Mitte 00s in erster Linie von theoretischem Interesse. Heute anonyme Funktionen , jedoch häufig in der Mainstream – Sprachen wie verwendet C # und JavaScript .

Notation

Das System „Lambda“ Kalkül genannt , weil sie die griechischen Buchstaben verwenden Lambda die ungebundene Variable in einem Ausdruck denotere. Zum Beispiel. λx.x + 1 die Funktion , die man zu einer Reihe anbringt. Dies steht im Vergleich zum „normalen“ mathematischen Schreibweise f (x) = x + 1 verwendet , um die gleiche Funktion zu beschreiben, die aber zur gleichen Zeit die Funktionsnamen von „F“ zugeordnet wird . Dies unterscheidet das Denken in „normalen“ Mathematik aus der mathematischen Logik, wo in der „normalen“ Mathematik nur den Buchstaben f wählen, der erste Buchstabe des Wortes Funktion , um anzuzeigen , dass der Name keine Rolle spielt.

In einem (fiktiven) Programmiersprache, heißt es Pseudo – Code , ein zum Beispiel könnte. schreiben

Funktion f (x Integer)
beginnen
 return x + 1
als

Aber hier ist der Name Bedeutung. In fast allen aktuellen „Mainstream“ Programmiersprachen ist es möglich , eine Funktion als Parameter an eine andere Funktion zu spezifizieren, aber in der Sprache , wo man nicht anonyme Funktionen geben kann, ist es nicht möglich , einen Funktionsparameter direkt angeben, aber Sie müssen es erklären zuerst und dann den Namen als Parameter eingeben. In Sprache, können anonyme Funktionen erlaubt die Funktion direkt als Parameter Kontrast eingeben, die in einigen Fällen Programmcode ermöglicht , die leichter zu lesen ist (neben Lesbarkeit gibt auch andere Gründe für anonyme Funktionen können wünschenswert sein).

Die lexikalische Analyse

In der mathematischen Logik konzentriert sich auf umfassen mit wie wenig Annahmen zu treffen , zu tun mit mathematischer Argumentation zu beginnen. Ein Problem hierbei ist das Verständnis für mathematische Ausdrücke, zum Beispiel. wenn Sie eine schreiben Textzeichenfolge x + 1, wie kann man eigentlich , dass x lokalisieren ist die ungebundene Variable kann mit „etwas anderes“ , während + 1 und hat angegebene Bedeutung ersetzt werden. Hier ist in dem Ausdruck f (x) = x + 1 ist es klar, dass der Text zwischen (und) , die dem ungebundene Variable, während in λx.x + 1 ist der Text zwischen und λ.

Bei der gewöhnlichen mathematischen Notation muss für die Anwendung der Funktion der vorübergehenden Verwendung zwei Schritte und Schreiben

f (x) = x + 1
f (7)

die achte antworten

In jedoch lambdakalkylen kann man mit einem Schritt machen tun und schreiben

(Λx.x + 1) (7)

Quantencomputer

Ein Quantencomputer ist eine Vorrichtung , die mittels berechnen kann quantum Verschlingung von Quantenzuständen. Vor kurzem (vor Dezember 2008) sind kleine Quantencomputer gebaut wurde. Viele Behörden und militärische Einrichtungen wie. NATO unterstützt Universitäten und kvanteberegningsforskningscentre einen Computer zum Beispiel zu entwickeln. Verschlüsselung .

Es wird angenommen , dass , wenn große Quantencomputer gebaut werden können, werden sie in der Lage sein , um sicher zu lösen Rechenprobleme schneller als jeder klassische Computer . Quantencomputer unterscheiden sich von klassischen Computern , z. DNA – Computer und Computer auf Basis von Transistoren und möglich. Transistoren auf quantenmechanische Effekte ohne Quantenverschränkung basiert.

Geschichte

Es war der Physiker Richard Feynman , der 1982 vorgeschlagen , dass man versuchen sollte , simulieren quantenmechanische Objekte in der Quantenmechanik selbst in Form eines Quantencomputers. In 1985 veröffentlichten David Deutsch Artikel mit einer Beschreibung des universellen Quantencomputers wegweisend. In 1994 überzeugten Peter Shor , dass ein Quantencomputer Zahl exponentiell schneller als ein klassischer Computer faktorisieren könnte [1] .

Dies bedeutete eine Fülle von Forschungsmitteln für die Forschung in der Quantencomputer und ihre Algorithmen , da die überwiegende Mehrheit aller öffentlichen Schlüssel krypteringssytemer ihre „ubrydelighed“ stützen , dass die Schwierigkeit ganze Zahlen von Factoring oder dass es schwierig ist , den diskreten Logarithmus zu lösen.

Gebäude

Teilchen in der Quantenmechanik ist in der Lage zur gleichen Zeit an zwei Orten zu sein , oder auf einmal in zwei Quantenzuständen sein. Dieser Effekt wird oft das Gedankenexperiment mit Schrödingers Katze kann eine Katze sowohl lebendig und tot zugleich sein. Diese Fähigkeit , in mehreren Quantenzuständen zu sein , gleichzeitig genannt Quantenüberlagerung .

Ein klassischer Computerspeicher ist gefertigt aus hochwertigem Bits . Jedes der Bits kann einen von zwei möglichen Zuständen speichern, können diese zum Beispiel. in fast allen Fachliteratur als „0“ und „1“ interpretiert, da die beiden Modi eine Frage der Bequemlichkeit genannt wird. Der Computer berechnet , indem diese Bits zu manipulieren.

Ein Quantencomputer, hingegen eine Vielzahl von Qubits. Ein Qubit speichert die „klassischen“ zwei Zustände „0“, „1“ oder eine Überlagerung der beiden Modi. Es ist falsch zu sagen , dass ein Qubit zwei Ist – Zustände gleichzeitig speichern kann – , dass der Kontrast kann, eine Überlagerung von zwei gewichteten Modi zu speichern ist. Der Quantencomputer berechnet , indem diese Qubits zu manipulieren. Qubittene muss quantenmechanisch verschränkten als Qubits zu handeln.

Ein Quantencomputer kann unter Verwendung eines beliebigen kleinen Teilchen realisiert werden, die eine getrennte Schreib- / lesbares kvantetilstandslager haben kann. Die Teilchen, mit dem Quanten verstrickt kvantetilstandslagre können Photonen , Moleküle …

Verhalten

Ein klassisches Computer durch 3 Bits kann nur ein Muster eines digitalen 3-Einsen oder Nullen speichern. Zum Beispiel haben die Bits zu einem Zeitpunkt „101“ gespeichert.

Ein Quantencomputer mit 3 Qubits speichern kann tatsächlich eine Überlagerung der 16 analogen Zustände / Werte, die vorteilhaft sein können modellieren als 8 komplexe Zahlen . Zu jeder Zeit kann qubittene speichert:

 Bedingung Amplitude Probability 
  (a + b) (a² + b²)
 000 0,37 + i 0,04 0,14
 001 0,11 0,18 0,04 + i
 010 0,09 0,31 0,10 + i
 011 0,30 0,30 0,18 + i
 100 0,35 0,43 0,31 + i
 101 0,40 0,01 0,16 + i
 110 0,09 0,12 0,02 + i
 111 0,15 0,16 0,05 + i
 ---------------------------------
 NA NA 1,00 Sum

Wenn es gewesen war n Qubits, sollte Tabelle mit 2 n Zeilen. Für mehrere hundert n , sollte es mehr Zeilen als es Atome im bekannten Universum . Neu formuliert , dass gilt n Anzahl von Qubits 2 machen n Berechnungen, Mathematik ist eine exponentielle Beziehung. Es ist ersichtlich , dass die Anzahl der möglichen Berechnungen jedes Qubit verdoppelt. [2]

Die erste Spalte zeigt alle möglichen Zustände für drei Bits. Ein klassischer Computer speichern kann nur eines dieser Muster auf einmal. Ein Quantencomputer kann gleichzeitig in einer Überlagerung aller acht Staaten sein. Die zweite Spalte zeigt eine gewählte „Amplitude“ eine bestimmte „direction“ von jedem der 8 Zuständen. Diese komplexen Zahlen 8 ist eine Momentaufnahme des Quantencomputers zu einem bestimmten Zeitpunkt. Durch eine Berechnung, diese 8 Zahlen verändert und miteinander interagieren.

Dieser Quantencomputer, speichern kann und die Amplituden auf die 8 gleichzeitig berechnet werden, zeigt, dass der Quantencomputer des Speicherns viel mehr als ein 3-Bit-klassischen Computer fähig ist.

Es sollte beachtet werden , dass die 8 – Amplituden nicht außerhalb qubittene gelesen werden. Wenn ein Algorithmus vorbei ist, machen eine einzelne Messung / Entladen . Der Messwert wird nur ein 3-Bit – Muster, und in dem Entladevorgang wird 8 Amplituden gelöscht. Das Lesen gibt eine Zufall der 8 Muster mit Wahrscheinlichkeit aus der Tabelle. Im Beispiel ist es 14% Wahrscheinlichkeit des Lesemusters „000“, eine 4% ige Chance des Lesemusters „001“ ist und so weiter. Jeder der komplexen Zahlen (a + b) eine Amplitude und jede Wahrscheinlichkeit (a² genannt + b²) wird die angerufene squared Amplitude , weil sie gleich sind | a + b | ². Die 8 Wahrscheinlichkeiten Summen für die ersten

Referenzen

  1. Sprung nach oben^ Eine kurze Einführung in die Quantum Computation
  2. Oben springt^ Engelhardt, Robin; Jensen, Hans Siggaard. „Angesichts der Selbstverwirklichung“, ERGO: Naturvidenskabens Philosophiegeschichte (erste Ausgabe), Nørhaven Buch A / S 2007, S. 281.. ISBN 978-87-595-2866-2 .

Siehe auch

  • Kvantecomputertidslinje
  • Nanotechnologie

Weitere Informationen

  • Für den interessierten Laien:
    • „The Marvelous Quanten“ erscheint www.dr.dk bis: d. 5. Februar 2014
    • West, J. (2000). Der Quantencomputer – Eine Einführung. ( Erde Erklärung von Quantencomputern. )
  • Gute allgemeine Hinweise:
    • Zentrum für Quantum Computation, University of Oxford http://www.qubit.org
  • thermische Ensembles
    • Übersicht der frühen utvecklingen, mit Links
    • Die ersten beiden Artikel über das Thema geschrieben: DG Cory, AF Fahmy, TF Havel, Proc. Nat. Acad. of Science, 94, 1634 (1997) und N. Gershenfeld und I. Chuang, Wissenschaft, 275, S.. 350-356, 1997. ( Download )
  • Die Verwendung von Quantencomputern Quantensysteme zu simulieren:
    • Feynman, RP „Simulieren Physics with Computers“ International Journal of Theoretical Physics, Bd. 21 (1982), S.. 467-488.
  • Quantenkryptografie:
    • Der erste Artikel über das Thema geschrieben:.. Wiesner, S. „Conjugate Coding“ SIGACT News, Band 15, 1983, S. 78-88; Brassard, G. und Bennett, CH, Proceedings of the IEEE International Conference on Computer Systems and Signal Processing, 1984, S.. 175 Ekert, A. „Quantum Cryptography Basierend auf Bell Theorem“ Physical Review Letters, Vol. 67 1991 pp. 661 -663.
    • Der erste Artikel über das Thema veröffentlicht: Bennett, CH, Brassard, G., Breidbart, S. und Wiesner, S., „Quantenkryptografie oder fälschungs U-Bahn-Token“, Advances in Cryptology: Proceedings of Crypto 82, August 1982, Plenum Press , S.. 267-275.
    • Eine lange Liste von Artikeln über die Quantenkryptografie, Kommentare, finden auf http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC.html
  • Universal – Quantencomputer und Church-Turing – Prinzip :
    • Deutsch, D. „Quantentheorie, das Church-Turing-Prinzip und der Universal-Quantum Computer“ Proc. Roy. Soc. Lond. A400 (1985) pp. 97-117.
  • Shors Faktorisierung:
    • Shor, P. „Algorithmen für Quantenberechnung: diskreter Logarithmen und Factoring“ Proceedings 35. Jahressymposium über Grundlagen der Informatik, Santa Fe, NM, USA, 20. November bis 22 1994 IEEE Comput. Soc. Press (1994), S.. 124-134.
    • John-Pierre Seifert, „Verwenden von weniger Qubits in Shors Faktorisierung Algorithmus über Simultaneous Diophantine Approximation“ ( Download )
    • IBMs Ankündigung der ersten wirklichen Beilegung des Algorithmus, der auch die Geschichte der forstekvantecomputere mit 2, 3, 5 und 7 Qubits gibt. Veröffentlicht in 19 Dezember 2001 Ausgabe von Nature .
  • Kvantedatabase Eintrag:
    • Grover, LK „Ein festes Quantum Mechanical Algorithmus für die Datenbanksuche“ Proceedings of the 28th Annual ACM Symposium über die Theorie der Informatik, Philadelphia (1996), pp. 212-219.
  • Quantum-Simulatoren:
    • libquantum – Eine Bibliothek für Quantensimulation
    • QCL – Simulation von Quantenberechnung in einem Quantencomputer Sprache
    • Quantenverschränkung :: – Kvanteberegningsmodul zu Perl.
  • Quantenmechanische Fehlerkorrektur:
    • Shor, PW „Schema zur Verringerung der Dekohärenz in Quantencomputerspeicher“ Phys. Rev. A 52 (1995), pp. 2493-2496.
    • Calderbank, AR und Shor, PW „gute Quanten Fehlerkorrekturkodes exist“ Phys. Rev. A 54 (1996), pp. 1098-1106.
    • Shor. PW „Fehlertolerante Quantenberechnung“ Proc. 37nd Annual Symposium über Grundlagen der Informatik, IEEE Computer Society Press, (1996), S.. 56-65.
  • Quantenmechanische Fehlervermeidung:
    • EN Lidar, IL Chuang, KB Whaley „Dekohärenz frei Teilräume für Quantenberechnung“, Phys. Rev. Lett 81 (1998), S.. 2594-2587
  • Die Lösung NP-Complete und # P-vollständige Probleme:
    • Daniel S. Abrams (1) und Seth Lloyd (2) ((1) Institut für Physik, MIT, (2) Fakultät für Maschinenbau, MIT), 1988, „Nonlinear Quantenmechanik indebærer polynomialzeit-Lösung für NP vollständige und #P Probleme „( Download )
    • Phil Gossett, 1988, „NP in BQP mit Linearitäts“ ( Download )
    • Yu Shi, 2001 „Verschränkung zwischen Bose-Einstein – Kondensate“, Int. J. Mod. Phys. B , Vol. 15 (10. September 2001) 3007-3030. (Download hier oder hier )