Wie führt die Nichtkommutativität von Observablen zu einer Quantenbeschleunigung beim Lösen von Algorithmen im Quantencomputing?

tl;dr Es geht nicht nur darum, dass Observables nicht pendeln. Entscheidend ist auch, dass Zustände überlagert, verschränkt etc. werden können.

Einige Berechnungsprobleme können auf verschiedenen Skalen auftreten, z. B. beim Sortieren$n$Elemente, oder wählen Sie den Pfad zwischen$n$Städte geht am schnellsten . Bei einer solchen Aufgabe und einem Lösungsweg, der als Algorithmus bezeichnet wird, quantifiziert die Zeitkomplexität dieses Algorithmus, wie stark er verlangsamt wird$n$erhöht sich. Zum Beispiel nehmen einige Arten des Sortierens das, was wir nennen$O(n^2)$Zeit und Verdoppelung groß$n$vervierfacht die Sortierzeit, während sonst nur dauern$O(n\log n)$Zeit und Verdoppelung$n$verdoppelt die Zeitskala kaum (wenn da nicht die nervtötenden wären$\log n$Faktor, es wäre nur eine Verdoppelung). In jedem Fall ist es nicht so teuer, eine Liste zu sortieren. Im Gegensatz dazu dauert das andere Problem, das ich erwähnt habe, ewig, es sei denn$n$ist sehr klein, obwohl nur wie viel teurer eine größere$n$Dies hängt vom verwendeten Algorithmus ab.

Es ist bekannt, dass Quantencomputer es uns ermöglichen, die zeitliche Komplexität einiger Probleme zu reduzieren, indem Algorithmen verfügbar gemacht werden, die klassische Computer nicht verwenden können. Es ist nicht bekannt, dass dies eine allgemeine Beschleunigungseigenschaft von Quantencomputern ist.

Hier ist ein Beispiel. Angesichts einer Liste von$n$Artikel haben wir garantiert genau einen mit der gewünschten Eigenschaft und können jeden prüfen. Wie finden wir heraus, was es ist? Klassischerweise können wir sie nur einzeln durchgehen, und das dauert$O(n)$Zeit. Erstaunlicherweise brauchen Quantencomputer nur$O(\sqrt{n})$Zeit! Warum?

Die vollständigen Details sind hier , aber das Wesentliche ist Folgendes: Wir bereiten eine Überlagerung aller Kandidatenantworten vor, in der sie jeweils denselben komplexwertigen Koeffizienten haben, und wenden dann weiter an, was man sich als Drehungen und Reflexionen vorstellen kann, die den Zustand verschieben$2\arcsin\frac{1}{\sqrt{n}}$Radiant, und sobald sich die Gesamtverschiebung annähert$\pi/2$eine Messung wird mit ziemlicher Sicherheit den richtigen Kandidaten identifizieren.

Die Überlagerung an sich ist jedoch nicht immer der springende Punkt: Ein mögliches Ergebnis davon, die Verschränkung, kann auch entscheidend sein. Ein viel schwierigeres Beispiel, das ich nicht im Detail erörtern werde, ist, dass die Nutzung verschränkter Zustände es Quantencomputern ermöglicht, große positive ganze Zahlen schneller zu faktorisieren als jeder bekannte klassische Algorithmus.

Ein paar Gedanken:

1. Der Aspekt der "nicht-kommutierenden Observablen" der Quantenmechanik entspricht im Wesentlichen der Möglichkeit, Überlagerungen und damit Interferenzeffekte usw. zu haben. Zu sagen, dass zwei Observablen pendeln, läuft darauf hinaus, dass die Messung ihrer jeweiligen Eigenbasen "inkompatible Informationen" liefert, dh das Wissen um die Das Ergebnis einer Messung verringert das Wissen über das Ergebnis der anderen.

2. Die Inkompatibilität unterschiedlicher Messgrundlagen wiederum läuft auf die Möglichkeit hinaus, in Überlagerungsgrundlagen zu messen. Dies ist die Eigenschaft von Quantensystemen, Informationen in den Zusammenhängen zwischen verschiedenen Bestandteilen halten zu können. Damit meine ich, dass ein Quantensystem so sein kann, dass seine einzelnen Komponenten überhaupt keine Informationen enthalten, und der einzige Weg, auf seine Informationen zuzugreifen, darin besteht, in nicht-lokalen Basen zu messen.

3. Meines Wissens gibt es keine eindeutig zufriedenstellende Antwort auf die Frage: Welche Eigenschaften der Quantenmechanik führen zu einer Quantenbeschleunigung in einem bestimmten Algorithmus? Einige relevante Diskussionen finden Sie zB hier . Sicher, Sie können sagen, dass schneller als klassische Quantenalgorithmen diejenigen sind, die Interferenzeffekte auf intelligente Weise ausnutzen, aber imo läuft das im Wesentlichen darauf hinaus, dass die Quantenmechanik die Algorithmen schneller macht. Interferenzeffekte sind so grundlegend und intrinsisch für die Quantenmechanik, dass die Aussage „X ist schneller wegen Interferenz“ so etwas wie die Aussage „X ist schneller wegen Quantenmechanik“ ist. Es hilft sicherlich nicht viel dabei, herauszufinden, welche Algorithmen tatsächlich einen Quantenvorteil bieten.