Was ist das Quantenrechenmodell?

Ich habe gelegentlich gehört, dass Leute über Quantenalgorithmen und über Zustände und die Fähigkeit gesprochen haben, mehrere Möglichkeiten gleichzeitig in Betracht zu ziehen, aber ich habe es nie geschafft, jemanden dazu zu bringen, das Rechenmodell dahinter zu erklären. Klar, ich frage nicht, wie Quantencomputer physikalisch aufgebaut sind, sondern wie man sie rechnerisch betrachtet.

Ich werde die Empfehlung von Martin Schwartz von Nielsen & Chaung als Standardreferenz wiederholen. es gibt auch viele andere.

Die Forschung auf diesem Gebiet zieht es vor, einheitliche Familien von Quantenschaltungen zu betrachten, die (ironischerweise) azyklische Netzwerke sind, die beschreiben, wie sich der Zustand eines oder mehrerer Register mit der Zeit ähnlich wie bei klassischen Booleschen Schaltungen verändert. Wenn Sie mehr erfahren möchten, empfehle ich, anhand dieses Modells zu lernen.

Ich möchte einige qualitative Antworten geben, um Martins Antwort zu ergänzen.

1. Die Quantenberechnung berücksichtigt tatsächlich nicht "mehrere Möglichkeiten gleichzeitig" - oder genauer gesagt, ob Sie davon ausgehen, dass sie mehrere Möglichkeiten gleichzeitig berücksichtigen, hängt von Ihrer Wahl der Interpretation der Quantenmechanik ab , dh von einer philosophischen Wahl, die keine hat Einfluss auf die Fähigkeit oder Vorhersagen des Rechenmodells. ("Mehrere Möglichkeiten auf einmal betrachten" entspricht der "Viele-Welten-Interpretation" des QM.)
   
   Zumindest kann man sagen, dass ein Quantencomputer mehrere Möglichkeiten gleichzeitig nur insoweit berücksichtigt, als eine randomisierte Berechnung mit flips berücksichtigt mehrere möglichkeiten gleichzeitig. Das ist weil:

2. Quantenzustände sind Verallgemeinerungen der "üblichen" Wahrscheinlichkeitsverteilungen - mit einigen einfachen, aber wichtigen Unterschieden. Eine Wahrscheinlichkeitsverteilung kann als nicht negativer reeller Vektor dargestellt werden, dessen Einträge sich zu 1 summieren, dh als Einheitsvektor in der norm ^1- Norm. Probabilistische Berechnungen müssen ℓ ¹ -Einheitsvektoren auf andere solche Vektoren abbilden und werden daher durch stochastische Abbildungen beschrieben. Man kann die Quantenberechnung auf ähnliche Weise beschreiben, außer dass man ℓ ² -Einheitsvektoren über ℂ verwendet (nicht darauf beschränkt, real oder nicht negativ zu sein); Transformationen erfolgen nach denjenigen Karten, die die ℓ ² -Norm, dh die einheitlichen Operationen, beibehalten .
   
   Dieser Unterschied ist natürlich nicht trivial und erklärt auch noch nicht, was die Koeffizienten der Quantenzustandsvektoren bedeuten . Aber es kann hilfreich sein, zu erklären, was mit Hilbert-Räumen und Tensorprodukten in der Quantenberechnung vor sich geht: Das heißt, genau die gleichen Dinge wie in der Wahrscheinlichkeitsberechnung. Der Konfigurationsraum eines Zufallsbits ist ein Vektor in ℝ ₊ ² (wobei ℝ ₊ die nicht negativen Reals sind); Da jedoch zufällige Bits korreliert werden können, kombinieren wir die Konfigurationsräume eines oder mehrerer zufälliger Bits, indem wir das Tensorprodukt nehmen. Der Konfigurationsraum von zwei Zufallsbits ist also ℝ ₊ ²  ⊗ ⊗ ₊ ²  ≅ ≅ ₊ ⁴ oder der vollständig allgemeine Raum der Wahrscheinlichkeitsverteilungen über die vier verschiedenen Zwei-Bit-Strings. Eine Operation A an dem ersten dieser Zufallsbits, die nicht an dem zweiten wirkt, wird durch den Operator A  ≤  I _{2 dargestellt}  . Und so weiter. Die gleichen Konstruktionen gelten für Quantenbits; und wir können Quantenregister über Mengen unterscheidbarer Elemente auf dieselbe Weise betrachten, wie wir Wahrscheinlichkeitsverteilungen über solche Mengen betrachten, wiederum unter Verwendung von using ² -Normvektoren über over.
   
   Diese Beschreibung beschreibt eigentlich die "reinen" Quantenzustände - diejenigen, für die man prinzipiell informationsschonend eine Delta-Verteilung über die Bitfolge 00 ... 0 (oder genauer a in der ℓ ^2- Norm willkürlich nahe beieinander liegen ). Zusätzlich zu der Quantenzufälligkeit (von der ich noch nichts explizites erwähnt habe) können Sie die Vanille-Konvexitäts-Zufälligkeit betrachten, die probabilistischen Gemischen von Quantenzuständen entspricht: Diese werden durch Dichteoperatoren dargestellt , die durch positive bestimmte Matrizen dargestellt werden können mit Spur 1 (wieder verallgemeinernde "klassische" Wahrscheinlichkeitsverteilungen, die durch den Spezialfall positiver Diagonalmatrizen mit Spur 1 dargestellt werden können).
   
   Wichtig dabei ist, dass Quantenzustände zwar häufig als "exponentiell groß" beschrieben werden, sie jedoch normalerweise mit den gleichen mathematischen Strukturen wie Wahrscheinlichkeitsverteilungen beschrieben werden. warum Wahrscheinlichkeitsverteilungen nicht in gleicher Weise als "exponentiell groß" beschrieben werden, ist unklar (aber letztendlich unwichtig). Die Schwierigkeit, Quantenzustände zu simulieren, ergibt sich aus dieser Tatsache, zusammen mit der Tatsache, dass sich die komplexen Koeffizienten dieser ℓ ² -Verteilungen (oder die komplexen Terme außerhalb der Diagonale der Dichteoperatoren, wenn Sie es vorziehen) auf eine Weise aufheben können, die Wahrscheinlichkeiten nicht können Dies erschwert die Einschätzung.

3. Verschränkung ist nur eine andere Form der Korrelation. Für die probabilistische Berechnung von z. B. Booleschen Strings sind die einzigen "reinen" Zustände (die durch informationserhaltende Transformationen auf eine Delta-Peak-Verteilung auf 000 ... 0 abgebildet werden können) die "Standardbasis" von Delta-Peak-Verteilungen auf der verschiedene Boolesche Zeichenfolgen. Somit ist diese Basis von ℝ ₊ ^{2 n}wird unterschieden. Aber es gibt in der Quantenmechanik, soweit wir das beurteilen können, keine solche Unterscheidungsgrundlage - dies ist am deutlichsten für Quantenbits. Infolgedessen gibt es mehr informationserhaltende Transformationen als nur die Permutationen: eine kontinuierliche Gruppe von ihnen. Dies ermöglicht zukünftigen Quantencomputern, Zustände auf eine Weise zu transformieren, die für probabilistische Computer nicht möglich ist, und möglicherweise einen asymptotischen Vorteil gegenüber diesen zu erzielen.
   
   Aber wie steht es mit der Verstrickung, die viele Menschen für mysteriös halten und die angeblich die Ursache für die Beschleunigung der Quantencomputer gegenüber der klassischen sind? "Verschränkung" ist hier eigentlich nur eine Form der Korrelation: Genau wie zwei Zufallsvariablen korreliert sind, wenn ihre Verteilung eine konvexe Kombination von mehr als einer Produktverteilung (mit unterschiedlichen Rändern für jede Variable) ist, sind zwei "Quantenvariablen" verschränkt, wenn ihre Verteilung ist eine lineare Kombination (mit Einheit ℓ ²-norm) von zwei gültigen Produktdistributionen; es ist dasselbe Konzept unter einer anderen Norm und spielt eine ähnliche Rolle bei Kommunikationsaufgaben. (Zum Beispiel: "Quantenteleportation" in der Quantenkommunikation entspricht klassisch dem Codieren und Decodieren einer Nachricht unter Verwendung eines Einmal-Pads.) Dies ist eine Form der Korrelation, die allgemeiner ist als nur klassisch korrelierte Bits; Die einzige Möglichkeit, dies zu zeigen, besteht darin, dass die im verwickelten Zustand codierten Korrelationen auf mehr als nur eine privilegierte Basis zutreffen . Verschränkung ist gewissermaßen die Folge des Fehlens einer privilegierten Grundlage.
   
   Die Leute sprechen gerne von Verschränkung als dem Schlüsselelement der Quantenberechnung, aber dies scheint einfach kein Wasser zu halten: Es gab Ergebnisse, die dies belegenDie Verschränkung ist für Shors Algorithmus nicht quantitativ wichtig, um große ganze Zahlen zu faktorisieren, und dass ein Quantensystem in der Tat zu viele Verschränkungen aufweisen kann, um für eine Berechnung nützlich zu sein. Überall, wo mir bewusst ist, dass Verschränkung eine wichtige Rolle in einem Quantenprotokoll spielt, geht es im Wesentlichen um Kommunikation (wobei zu erwarten ist, dass Korrelationen für ein klassisches Protokoll eine wichtige Rolle spielen).

An diesem Punkt fange ich an, mich in den Bereich der persönlichen Meinung zu begeben, also höre ich hier auf. Aber hoffentlich könnten diese Bemerkungen einiges von dem, was an der Quantenberechnung und deren Beschreibung unklar ist, enträtseln.

Lance Fortnow hat einen Artikel geschrieben, der das Quantencomputing ohne Einsatz der Quantenmechanik erklärt. Er stellt es im Wesentlichen so dar, wie man probabilistisches Computing darstellen würde. Ich vermute, dass dies ein schnellerer Ausgangspunkt ist als so etwas wie Nielson und Chuang (obwohl ich der Meinung bin, dass Nielson und Chung auf jeden Fall auf Ihrer Leseliste stehen sollten, wenn Sie wirklich darauf eingehen wollen).

L. Fortnow. Die Sichtweise eines Komplexitätstheoretikers auf das Quantencomputing. Theoretical Computer Science, 292 (3): 597-610, 2003. Sonderausgabe der Arbeiten, die auf dem zweiten Workshop zu Algorithmen in der Quanteninformationsverarbeitung vorgestellt wurden.

Nun, der verwendete Standardtext ist Quantum Computation und Quantum Information von Nielsen und Chuang. Es deckt eine ganze Reihe verschiedener Aspekte auf vernünftigem Niveau ab. Fast jeder, der auf dem Gebiet arbeitet, hat eine Kopie davon in seinem Regal. Das Buch von Kaye, Laflamme und Mosca ist ebenfalls gut, deckt aber weniger ab (obwohl Algorithmen etwas mehr im Fokus stehen).

Obwohl es durchaus möglich ist, Quantencomputing zu erklären, ohne viel mit der Quantenmechanik zu tun zu haben, halte ich dies nicht unbedingt für eine gute Methode, um Quantenberechnung zu erlernen. Das Gespür für die physikalische Theorie bringt eine Menge Intuition mit sich, da viele der neueren Modelle der Quantenberechnung (dh adiabatische, topologische und messungsbasierte Modelle) physisch motivierter sind als die Quanten-Turing-Maschine oder das Schaltungsmodell.

Allerdings ist die zum Verständnis der Quantenberechnung erforderliche Quantenmechanik recht einfach und wird in Nielsen und Chuang recht gut behandelt. Wirklich, Sie können ein gutes Gefühl dafür bekommen, indem Sie das entsprechende Kapitel durchlesen und die Übungen ausprobieren. Das ist die Art von Dingen, die Sie mit ein paar Arbeitstagen einigermaßen verstehen können. Mein Rat ist jedoch, keinen Standard-Intro-Text für die Quantenmechanik zu verwenden. Der Ansatz zur Modellierung von Atomen, Molekülen und Materialien verwendet unendlich dimensionale Systeme und ist um ein Vielfaches aufwändiger. Für die Quanteninformation ist es ein viel besserer Anfang, sich endlichdimensionale Systeme anzuschauen. Traditionell drehen sich die von Physikern untersuchten Probleme auch darum, Grundzustände und Verhaltensweisen im eingeschwungenen Zustand zu finden. und dies ist, was die meisten Einführungstexte behandeln werden (beginnend mit der zeitunabhängigen Schrödinger-Wellengleichung). Für das Quantencomputing interessieren wir uns mehr für die zeitliche Entwicklung von Systemen, und dies wird in Quantencomputertexten viel prägnanter behandelt als in allgemeinen Quantenmechanik-Intro-Texten (die per Definition allgemeiner sind).

$BQP$

$|\phi\rangle$$\cal{H_2}$$\cal{H_2} \otimes ... \otimes \cal{H_2}$$|\psi\rangle$$U$$square$

Eine ausführlichere Einführung finden Sie in den Standard-Lehrbüchern Nielsen und Chuang.

Zunächst müssen Sie die Quantenphysik verstehen.

Ein paar Empfehlungen:

1. " Quantencomputing für Informatiker " von Noson S. Yanofsky und Mirco A. Mannucci
2. "Eine Einführung in das Quantencomputing" von Phillip Kaye, Raymond Laflamme und Michele Mosca

Und auf der unterhaltsameren Seite der Dinge, "Eine Abkürzung durch die Zeit: Der Weg zum Quantencomputer" von George Johnson.

Eine schöne Einführung finden Sie in dem Artikel "Eine Einführung in das Quantencomputing für Nicht-Physiker" von Eleanor Rieffel und Wolfgang Polak. Es ist vielleicht ein bisschen alt, aber es ist immer noch eine gute, kurze, eigenständige Einführung in das Thema: http://arxiv.org/abs/quant-ph/9809016

Ein weiterer, viel zusammenfassenderer Artikel ist Pablo Arrighis "Quantenberechnung, die meiner Mutter erklärt wurde" unter http://arxiv.org/abs/quant-ph/0305045

Das ist Ihnen wahrscheinlich schon bewusst, aber auf seinem Blog hat Scott Aaronson Links zu einer Reihe seiner Kursvorträge zum Thema Quantencomputer sowie Links zu QC-Primern anderer (scrollen Sie einfach in der rechten Seitenleiste nach unten, um diese zu finden). .

Wenn Sie eine buchlange Einführung wünschen, die aber etwas schonender ist als ein Text wie Nielsen und Chuang, würde ich Quantum Computing for Computer Scientists von Yanofsky und Mannucci empfehlen . Sie verbringen eine ganze Menge Zeit damit, die mathematischen Voraussetzungen zu überprüfen, bevor sie in die QC selbst eintauchen. Wenn Sie einen starken mathematischen Hintergrund haben, scheint dieses Buch zu grundlegend zu sein, aber ich fand es ziemlich nützlich.

Im Allgemeinen würde ich Joes Rat befolgen. Aber für eine kurze Einführung würde ich die Texte von Lance Fortnow und Stephen Fenner auf die Leseliste von Informatikern setzen, die quantenmässig werden.

Wenn Sie ziemlich weit fortgeschritten sind, können Sie mit der Untersuchung der Quantenmethoden für klassische Probleme nach de Wolf-Drucker beginnen . Es ist ein guter Weg , Quanten zu verstehen Techniken , bevor Sie zu Quanten bekommen Probleme .

Ich glaube nicht, dass Sie Quantenmechanik lernen müssen. Es kommt jedoch darauf an, in welchem ​​Bereich Sie arbeiten möchten. Es gibt Bereiche auf dem Gebiet, die wirklich Kenntnisse über die Quantenmechanik benötigen, aber als Beispiel für den Bereich, an dem ich arbeite, Typentheorie und Lambda-Berechnung, brauche ich es nicht, ich kann es nur tun, indem ich einige der Rechenmodelle dafür kenne.

Neben seinem Standardtext mit Chuang bietet Michael Nielsen auf Youtube eine Reihe von Videovorträgen mit dem Titel Quantum Computing for the Determined an, die einen Überblick über das Rechenmodell geben. Die Videos sind für alle mit einem kleinen Verständnis der Informatik und der linearen Algebra sehr gut zu sehen.