Quantenalgorithmen lösen ein neuartiges Problem!

1994 fand ein Mathematiker heraus, wie man Quantencomputer dazu bringen kann, Dinge zu tun, die gewöhnliche klassische Computer nicht können. Die Arbeit zeigt, dass eine Maschine, die auf den Regeln der Quantenmechanik basiert, im Prinzip große Zahlen effizient in ihre Hauptfaktoren zerlegen kann – eine sehr schwierige Aufgabe für klassische Computer, die die meisten heutigen Grundlagen der Internetsicherheit ausmachen.

Damit kam eine Welle des Optimismus. Vielleicht, so glauben Forscher, gelingt es uns, Quantenalgorithmen zu erfinden, die eine Vielzahl unterschiedlicher Probleme lösen können.

Aber der Fortschritt kam zum Stillstand. „Es ist irgendwie enttäuschend“, sagte Ryan O'Donnell von der Carnegie Mellon University. „Die Leute werden sagen: ‚Das ist großartig, ich bin sicher, wir werden alle möglichen anderen erstaunlichen Algorithmen bekommen‘, und das sind sie auch.“ nicht.“ Die Wissenschaftler fanden nur signifikante Beschleunigungen für eine einzige, enge Klasse von Problemen in einem Standardsatz namens NP, was bedeutet, dass sie über effiziente überprüfbare Lösungen verfügen – wie etwa die Faktorisierung.

Das ist schon seit drei Jahren so. Im April erfanden Forscher dann ein völlig neuartiges Problem, das Quantencomputer schneller lösen können sollten als klassische Computer. Es geht darum, den Input eines komplexen mathematischen Prozesses allein auf der Grundlage seines chaotischen Outputs zu berechnen. Ob dieses Problem ein Einzelfall ist oder das erste von vielen anderen ist, muss noch geklärt werden.

„Da ist ein Gefühl der Aufregung“, sagte Vinod Vaikuntanathan, ein Informatiker am MIT. Da ist nichts.“

Informatiker versuchen besser zu verstehen, was Quantencomputer können, indem sie mathematische Modelle untersuchen, die sie darstellen. Typischerweise stellen sie sich ein Modell eines Quantencomputers oder eines klassischen Computers vor, gepaart mit einem idealen Computer namens Orakel. Ein Orakel ist wie eine einfache mathematische Funktion oder ein Computerprogramm, das Eingaben entgegennimmt und eine vorgegebene Ausgabe ausgibt.

Sie können ein zufälliges Verhalten aufweisen und „Ja“ ausgeben, wenn die Eingabe in einem zufälligen Bereich liegt (z. B. 12 bis 67). Andernfalls geben Sie „Nein“ aus. Oder sie könnten periodisch sein, so dass eine Eingabe zwischen 1 und 10 „Ja“ zurückgibt, 11 bis 20 „Nein“ ergibt, 21 bis 30 wiederum „Ja“ ergibt und so weiter.

Angenommen, Sie haben eine dieser periodischen Prophezeiungen, kennen aber den Zeitraum nicht. Alles, was Sie tun können, ist, ihm Zahlen zu geben und zu sehen, was er ausgibt. Wie schnell kann ein Computer unter diesen Einschränkungen Zyklen finden? Im Jahr 1993 entdeckte Daniel Simon, damals an der Universität Montreal, dass Quantenalgorithmen Antworten auf eng verwandte Probleme schneller berechnen konnten als jeder klassische Algorithmus. Dieses Ergebnis ermöglicht es Simon festzustellen, wo Quantencomputer ein erhebliches Potenzial haben. Eines der ersten Anzeichen einer Dominanz. Doch als er sein Papier bei einer großen Konferenz einreichte, wurde es abgelehnt. Das Papier weckte jedoch das Interesse eines jüngeren Mitglieds des Konferenzprogrammkomitees, Peter Shor, der damals bei Bell Laboratories in New Jersey arbeitete.

Shor entdeckte weiter, dass er Simons Algorithmus optimieren konnte, um die Periode des Orakels zu berechnen, falls es eine gab. Dann wurde ihm klar, dass er den Algorithmus noch einmal optimieren konnte, um eine Gleichung zu lösen, die sich wie eine periodische Prophezeiung verhielt: eine Gleichung, die eine periodische Faktorisierung beschreibt.

Shors Ergebnisse waren historisch. Der von ihm entdeckte Quantenalgorithmus kann große Zahlen schnell auf ihre Primfaktoren reduzieren, was kein bekannter klassischer Algorithmus kann. In den Folgejahren entdeckten Forscher weitere effiziente Quantenalgorithmen. Einige von ihnen, wie Shors Algorithmus, bieten sogar exponentielle Vorteile, aber niemand konnte einen signifikanten Quantenvorteil bei einem nichtperiodischen NP-Problem nachweisen.

Aufgrund mangelnder Fortschritte haben zwei Informatiker, Scott Aaronson von der University of Texas in Austin und Andris Ambainis von der University von Lettland, durchgeführte Beobachtung. Beweise für den Quantenvorteil scheinen immer auf Vorhersagen mit einer nicht zufälligen Struktur, wie etwa der Periodizität, zu beruhen. Im Jahr 2009 spekulierten sie, dass es bei zufälligen oder unstrukturierten NP-Problemen keine nennenswerte Beschleunigung geben würde;

Ihre Vermutung schränkt die Fähigkeiten von Quantencomputern ein. Aber es heißt nur, dass es für bestimmte Arten von unstrukturierten NP-Problemen – solche mit Ja- oder Nein-Antworten – keine signifikante Beschleunigung gibt. Diese Vermutung gilt nicht, wenn es bei einem Problem darum geht, eine spezifischere, quantitative Antwort zu finden, ein sogenanntes Suchproblem.

Vor diesem Hintergrund beschlossen die Forscher Takashi Yamakawa vom NTT Social Informatics Laboratory und Mark Zhandry von NTT Research und der Princeton University, 2005 mit einem spezifischen Suchproblem zu experimentieren, das Oded Regev gestellt hatte.

Stellen Sie sich eine Reihe von Wetterfahnen vor, die alle in die gleiche Richtung zeigen. Geben Sie ihnen jeweils einen maßvollen Stoß und lassen Sie die Böe ihre Richtung beeinflussen. Regev möchte anhand ihrer endgültigen Richtung feststellen, wohin sie ursprünglich gerichtet waren. Probleme wie dieses wurden als „Fehlerlernen“ bekannt, da Schub und Wind als zufällige Fehlerquellen in der ursprünglichen Richtung wirken. Es gibt Hinweise darauf, dass sowohl klassische als auch Quantenalgorithmen schwer zu lösen sind.

Yamakawa und Zhandry haben die Einstellungen optimiert. Sie haben die Stärke dieser Starts verändert, um sie vorhersehbarer zu machen. Sie haben auch dafür gesorgt, dass der Wind durch ein zufälliges Orakel bestimmt wird, sodass er in einigen Fällen noch zufälliger ist, in anderen Fällen jedoch völlig inaktiv ist.

Mit diesen Modifikationen fanden die Forscher heraus, dass der Quantenalgorithmus effektiv die ursprüngliche Richtung finden kann. Sie bewiesen auch, dass jeder klassische Algorithmus um einen exponentiellen Faktor verlangsamt werden muss. Wie Shor passten sie dann den Algorithmus an, um eine realistische Version des Problems zu lösen, indem sie die Vorhersagen durch tatsächliche mathematische Gleichungen ersetzten.

Informatiker versuchen immer noch, dieses Problem zu verstehen und zu lösen. Vaikuntanathan verglich dies mit einer anderen Situation, die bei der Datenkomprimierung auftritt: Wenn Informationen komprimiert werden, können zwei Bits versehentlich an die gleiche Stelle gequetscht und so überschrieben werden. Die Probleme, diese Kollisionen im Voraus zu antizipieren, um sie zu vermeiden, weisen einige Ähnlichkeiten auf. „Das ist eine Klasse von Problemen, die im Grunde so aussehen“, sagte er. „Vielleicht können diese Probleme auch auf den heutigen jungen Versionen von Quantencomputern gelöst werden.“ gelöst und bietet eine Möglichkeit, sie zu testen. Die Idee war, dass unstrukturierte Probleme möglicherweise weniger Ressourcen zum Programmieren erfordern oder weniger empfindlich gegenüber Rauschen sind, weil sie bereits zufällig sind. Bisher scheint dieses neue Problem jedoch noch zu weit fortgeschritten zu sein, als dass bestehende Quantencomputer es lösen könnten. „Es ist ein seltsames Problem. Ich habe nicht darüber nachgedacht, es zu definieren“, sagte Aaronson, „aber im Nachhinein betrachtet hat es einige wirklich nette Eigenschaften.“ Beispiele für signifikante Quantenvorteile bei NP-basierten Problemen.“ Werden viele andere Probleme in der Quantenwelt von nahezu unlösbar zu lösbar werden? Jetzt gibt es noch mehr Gründe zu dieser Annahme. „Dies verändert in gewissem Maße unsere Sicht darauf, welche Probleme Quantencomputer gut lösen können“, sagte O’Donnell.

Das obige ist der detaillierte Inhalt vonQuantenalgorithmen lösen ein neuartiges Problem!. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!