Get best of the week

Wie π kollidierende Blöcke und einen Quantensuchalgorithmus kombiniert

Ein neugieriger Physiker hat einen unerwarteten Zusammenhang zwischen der Theorie der Kollisionsblöcke und dem berühmten Quantensuchalgorithmus entdeckt




Was haben Ziffern von π, kollidierende Blöcke und Quantensuchalgorithmen gemeinsam? Mehr als Sie vielleicht denken. Diese Verbindung wird durch zwei humorvolle wissenschaftliche Arbeiten hergestellt - eine aus dem Jahr 2003 und die zweite aus dem Dezember 2019. Zusammen kombinieren sie die Welten der Dynamik, Geometrie und des Quantencomputers und zeigen, wie selbst die abstraktesten mathematischen Rätsel überraschenderweise einen Zusammenhang mit der Physik aufzeigen können.

Sperren


Stellen Sie sich zwei Metallblöcke mit einem Gewicht von jeweils 1 kg vor, um diese Zusammenhänge zu verstehen. Sie befinden sich reibungsfrei auf der Oberfläche rechts von der festen Wand. Der Block, der der Wand am nächsten liegt, ist bewegungslos, der zweite gleitet darauf zu und nähert sich nach rechts. Eine Reihe von Zusammenstößen muss unvermeidlich auftreten; Angenommen, die kinetische Energie verschwindet bei Kollisionen nicht. Unter solchen idealen Bedingungen läuft dieser Prozess folgendermaßen ab:


Der rechte Block trifft den linken und gibt ihm den ganzen Impuls. Der linke Block prallt von der Wand ab und kehrt für eine weitere Kollision und eine weitere vollständige Impulsübertragung nach rechts zurück.

Wenn Sie jedoch die Masse des rechten Blocks erhöhen, wird die Situation interessanter. Wenn es 100 kg wiegt, überträgt es bei jeder Kollision nur einen kleinen Teil seines Impulses auf den kleineren Block und erhöht sich anstelle der Anzahl der Kollisionen von 3 auf 31.


Mit einem Massenverhältnis von 10.000 zu 1 wird die Situation nach 314 Kollisionen gelöst.


Erhöhen Sie die Differenz, indem Sie die Masse mit 100 multiplizieren, und Sie werden einen schockierenden Trend beobachten können: Die Anzahl der Kollisionen nähert sich der Zahl π immer näher.


Gregory Galperin, ein Mathematiker der University of East Illinois, bemerkte dieses Phänomen erstmals [1993]. 2003 erklärte er dies, indem er die Bewegungen von Blöcken durch einen sich bewegenden Punkt visualisierte, dessen x-Koordinaten die Position eines Blocks und die y-Koordinaten des zweiten angeben. Die Flugbahn eines Punktes in der Ebene ist mit einem Halbkreis verbunden, von wo aus π erscheint.

Ein bemerkenswertes Ergebnis, auch wenn diese idealen Bedingungen es scheinbar nutzlos machen. Wenn Sie jedoch die Schlamperei der realen Welt in der Mathematik vernachlässigen, finden Sie eine reine Regelmäßigkeit, die unerwartete Zusammenhänge mit anderen Bereichen der Wissenschaft aufzeigt.

2019 habe ich drei Videos veröffentlichtAdam Brown, ein Forscher von Google und Physiker an der Stanford University, erklärte die Ergebnisse von Halperin und sah sie sich an. Nach einigen Monaten auf der Konferenz nahm er mich beiseite, um seine Beobachtungen zu teilen. Zu seiner Freude entdeckte er, dass die Mathematik, die die Dynamik dieser Blöcke unter einem bestimmten Gesichtspunkt beschreibt, mit der Mathematik identisch ist, die einen der bekanntesten Quantenalgorithmen beschreibt.

Quantenansatz


Dies bringt uns zum zweiten Teil des Puzzles: Wie die Quantensuche funktioniert.

Angenommen, Sie haben eine lange Liste von Namen ohne Sortierung - beispielsweise eine Million - und müssen einen bestimmten Namen finden. Sie haben keine andere Wahl, als einen Namen nach dem anderen zu überprüfen, bis Sie auf den richtigen stoßen. Im Durchschnitt benötigen Sie eine halbe Million Iterationen. Manchmal mehr, manchmal weniger, aber auf jeden Fall wird es einige Zeit dauern.

Ein Computer könnte diese Suche für Sie durchführen, aber das Problem bei großen Listen ist, dass die Zeit, die für die Verarbeitung benötigt wird, proportional zu ihrer Größe zunimmt. Zumindest bei Verwendung eines klassischen Computers. Aber im Jahr 1996, Liebe Grover, der in Bell Labs arbeitete, beschriebenwie ein Quantencomputer eine solche Suche viel schneller und in nicht mehr als 1000 Schritten durchführen kann. Im allgemeinen Fall wird ein Quantencomputer eine Liste der Länge N in π / 4 √N-Schritten verarbeiten. Beachten Sie, dass mit zunehmender Anzahl N die Anzahl der Schritte eines Quantencomputers langsamer wächst als bei einem klassischen.

Eine solche Sucheffizienz ist möglich, weil ein Quantencomputer alle Elemente der Liste gleichzeitig verarbeitet. Er macht jedoch nicht nur das Gleiche wie ein klassischer Computer, sondern nur zur gleichen Zeit.

Ein klassischer Computer beantwortet die Frage: "Ist das 21. Element der Liste der Name, den ich brauche?" Und es wiederholt es für jede Position der Liste von 0 bis 999.999. Direkt, aber nicht sehr effektiv.

Der Algorithmus von Grover arbeitet jedoch mit einer Listenmethode, die auf den ersten Blick seltsam erscheint, aber am Ende nützlicher ist. Ein klassischer Computer kann einfach Bits aus dem Speicher lesen. Unsicherheiten beim Quantencomputing führen dazu, dass Sie die Komponenten des Vektors, mit dem Sie arbeiten, nicht direkt herausziehen können. Jede Position in der Liste hat eine zusätzliche Wahrscheinlichkeitsstruktur. Sie sehen sich nicht an, welcher Name an dieser Position steht, Sie messen die gesamte Liste und erhalten eine zufällige Position - den Index - gemäß den Wahrscheinlichkeiten. Aufgrund der zugrunde liegenden Quantenmechanik arbeiten wir nicht direkt mit probabilistischen Werten, sondern mit Zahlen, deren Quadrat der Wahrscheinlichkeit entspricht, einen Index zu erhalten, der dem gesuchten Namen entspricht.



Wie kann das Lesen eines Zufallsindex nützlich sein? Die Kunst des Quantencomputers besteht darin, eine Liste von Wahrscheinlichkeiten zu manipulieren, die die Chancen zu Ihren Gunsten erhöhen. In unserem Beispiel bedeutet dies, eine Methode zu erfinden (wie es der Grover-Algorithmus tut), um die mit dem Index des gesuchten Namens verknüpfte Zahl nahe an der Einheit zu erhalten, sodass alle anderen Zahlen nahe Null sind. Wenn Sie diese Liste lesen und als Antwort einen Index erhalten, wissen Sie wahrscheinlich, dass dieser dem gesuchten Namen entspricht.

Quantencomputer-Tools bestehen aus Operationen, die ein Forscher auf diese Liste von Wahrscheinlichkeiten anwenden kann. In der Mathematik wird eine solche Liste als Vektor bezeichnet. Es ist oft zweckmäßig, sich einen Vektor als Punkt in einem Koordinatensystem oder als Pfeil vorzustellen, der vom Ursprung zu diesem Punkt gezogen wird.



Ein Zweikomponentenvektor kann als Pfeil im zweidimensionalen Raum dargestellt werden. Ein Vektor mit 1.000.000 Komponenten lebt in einem atemberaubenden Raum mit 1.000.000 Dimensionen. Die von einem Quantencomputer ausgeführten Operationen sehen aus wie Drehungen und Umkehrungen dieses Pfeils. Numerisch wird jede Operation durch eine Matrix angezeigt.



Quantenberechnungen sind besonders schnell, da jede Operation mit dem gesamten Wahrscheinlichkeitsvektor ausgeführt wird und nicht komponentenweise verläuft. Grover entdeckte eine schwierige Möglichkeit, einen bestimmten Vektor mit zwei intermittierenden Operationen zu manipulieren, was zu einem Vektor mit den von uns benötigten Wahrscheinlichkeiten führte. Es ist wichtig, dass die Gesamtzahl der erforderlichen Vorgänge viel kleiner als die Größe der Liste ist.

Wenn Sie sich nur schwer vorstellen können, wie dies funktionieren kann, sind Sie nicht der einzige. Daher war Adam Brown so glücklich, einen Weg zu finden, sich diese abstrakten Vektormanipulationen als verständlicheres Rätsel vorzustellen.

Versteckte Links


Es stellte sich heraus, dass Brown, als ich meine Videos über die Berechnung der Zahl π mit kollidierenden Blöcken sah, nur Grovers Algorithmus im Kopf hatte, sodass er ihre Verbindung sofort bemerkte. "Wenn Sie den ganzen Tag über die Quantensuche nachdenken, scheint alles wie eine Quantensuche", sagte Brown, "und es ist zufällig passiert, dass sich herausstellte, dass dieser Fall wirklich mit der Quantensuche zusammenhängt."

Und wenn Galperins Arbeit an Blockkollisionen den Raum verwendete, der die Position jedes Blocks codierte, beginnt die Verbindung mit Grovers Quantensuche mit einem Vektor, dessen x- und y-Komponenten die Geschwindigkeit jedes Blocks codieren. Jede Kollision von Blöcken führt zu einer bestimmten Operation an diesem Vektor, wobei seine Komponenten geändert werden. Wenn beispielsweise der linke Block mit der Wand kollidiert und die Richtung in die entgegengesetzte Richtung ändert, bedeutet dies, dass die Komponente unseres Vektors mit -1 multipliziert wird und die Komponente x unverändert bleibt. Aus geometrischer Sicht sieht dies aus wie eine Reflexion eines Vektors um die x-Achse.

Wenn zwei Blöcke kollidieren, ähnelt eine Änderung ihrer Geschwindigkeiten einem anderen Flip dieses Vektors, der nur von der Mitte versetzt ist. Wenn die Simulation fortgesetzt wird, kollidiert der linke Block erneut mit der Wand, was zu einer weiteren Drehung auf der x-Achse führt. Eine weitere Kollision von Blöcken bedeutet eine weitere Revolution. Infolgedessen füllt der Vektor bei einer ausreichenden Anzahl von Kollisionen die bekannte Kurve: den Kreis.


Brown bemerkte, dass, wenn diese Situation korrekt beschrieben wird, diese beiden Operationen, die sich in die eine oder andere Richtung ändern, mit den beiden Operationen identisch sind, die Grover in seinem Quantensuchalgorithmus verwendet hat.

Um zu verstehen, wie dies geschieht, stellen Sie sich einen großen rechten Block in Form von vielen zusammengeklebten Kilogramm vor. Anstelle eines zweidimensionalen Vektors, der jede Geschwindigkeit beschreibt, erhalten wir dann einen N-dimensionalen Vektor, wobei N die Gesamtzahl der kleinen Blöcke ist, einschließlich des isolierten Blocks links. Jeder der kleinen Blöcke entspricht einem Namen in einer unsortierten Liste, und ein separater Block links entspricht dem Zielnamen.

In seiner Arbeit hat Brown bewiesen, dass die Art und Weise, wie diese Kollisionen von Blöcken den Vektor ändern, der sie beschreibt, absolut identisch mit der Art und Weise ist, wie der Grover-Algorithmus den Quantenvektor ändert, der eine unsortierte Liste von Namen bezeichnet. Der Moment im System kollidierender Blöcke, in dem sich ein großer Block umdrehen soll und fast die gesamte Energie im System in einem kleinen Block liegt, entspricht dem Moment im Grover-Algorithmus, in dem fast die gesamte Wahrscheinlichkeit in dem Namen liegt, den Sie finden müssen.

Die Tatsache, dass die Zahl π beim Zählen von Kollisionen erscheint, spiegelt sich im Grover-Algorithmus wider: π / 4 √N Schritte. Die Quadratwurzel im Ausdruck gibt auch an, wie weit die Zählung der Ziffern von π (in Grad 10) geht, nachdem die Masse eines großen Blocks mit 10 multipliziert wurde.

"Bisher ist es nur eine Spielerei", sagte Brown. "Aber in der Physik haben wir gelernt, dass je mehr Möglichkeiten wir über ein Problem nachdenken können, desto mehr Ideen wir sehen können. Ich hoffe, dass diese Tatsache eines Tages nützlich ist." Wir haben nur wenige gute alternative Möglichkeiten, um den Grover-Algorithmus zu visualisieren.

Diese Verbindungen betonen die Fähigkeiten der universellen Sprache der Mathematik. Die Verwendung von Vektoren zur Codierung des Zustands eines physikalischen Systems funktioniert sowohl bei großflächigen Kollisionen von Blöcken als auch bei Mikroskalen von Quantenzuständen. Viele grundlegende Ideen in der Mathematik, die auf den ersten Blick unangenehm von der Realität getrennt zu sein scheinen, erweisen sich als mächtige Werkzeuge, denn wenn Sie die physikalischen Details in einem der Bereiche weglassen, können Sie ihre verborgenen Verbindungen mit dem anderen entdecken.

More articles:


All Articles