Wissenschaftler in den USA haben herausgefunden, wie Probleme getestet werden können, die dem Menschen noch nicht zur Verfügung stehen. Wissenschaftler verwenden im Dialog mit Computern, die diese Probleme lösen, dieselbe Methode wie Ermittler der Polizei. Sie "verwirren" die Befragten, befragen zwei Autos getrennt usw. Sogar die Quantenmechanik wird verwendet.
Stellen Sie sich vor: Ein Mann kommt zu Ihnen und sagt, dass er einen Wahrsager hat und dass dieser Wahrsager die unverständlichen Geheimnisse des Universums enthüllen kann. Sie sind fasziniert, aber Sie glauben ihm kaum. Sie werden auf jeden Fall sicherstellen wollen, dass der Wahrsager die Wahrheit sagt, und dafür benötigen Sie einen Weg oder eine Methode.
Dies ist die Essenz eines der Hauptprobleme der Informatik. Einige Aufgaben sind zu schwierig, um sie innerhalb eines angemessenen Zeitrahmens zu erledigen. Ihre Lösung ist jedoch leicht zu überprüfen. Aus diesem Grund möchten Informatiker wissen: Wie komplex kann ein Problem sein, das eine überprüfbare Lösung hat?
Es stellt sich heraus, dass die Antwort lautet: Es kann unglaublich komplex sein.
Im April veröffentlichten zwei Informatiker ein Forschungspapier, in dem die Anzahl der Probleme vervielfacht wurde, die schwer zu lösen, aber leicht zu überprüfen sind. Sie beschrieben eine Methode zum Testen von Lösungen für Probleme von fast unglaublicher Komplexität. "Es klingt wie verrückt", sagte Thomas Vidick, ein Informatiker am California Institute of Technology, der an dieser neuen Arbeit nicht beteiligt war.
Die Forschung befasst sich mit Quantencomputern, die Berechnungen nach den widersprüchlichen Regeln der Quantenmechanik durchführen. Quantencomputer tauchen gerade erst auf, aber in Zukunft könnten sie die Berechnung und Berechnung revolutionieren.
Tatsächlich gibt uns die neue wissenschaftliche Forschung die Möglichkeit, den am Anfang des Artikels beschriebenen Wahrsager zu beeinflussen. Selbst wenn er verspricht, uns Antworten auf die Probleme zu geben, die wir selbst nicht lösen können, werden wir auch in dieser scheinbar hoffnungslosen Situation eine Möglichkeit haben, den Wahrsager zu testen und sicherzustellen, dass er die Wahrheit sagt (oder täuscht).
Werbevideo:
ZUM TOD DES UNIVERSUMS
Wenn ein Problem schwer zu lösen, aber leicht zu überprüfen ist, nimmt das Finden einer Lösung viel Zeit in Anspruch, die Überprüfung der Richtigkeit der angegebenen Lösung jedoch nicht.
Hier ist ein Beispiel. Stellen Sie sich vor, Sie bekommen eine Zeichnung. Es ist eine Sammlung von Punkten (Eckpunkten), die durch Linien (Kanten) verbunden sind. Sie werden gefragt, ob es möglich ist, diese Punkte einer Form mit nur drei Farben zu malen, sodass die durch Linien verbundenen Punkte unterschiedliche Farben haben.
Dieses dreifarbige Problem ist schwer zu lösen. Im Allgemeinen nimmt die Zeit, die zum Erstellen einer dreifarbigen Figur (oder zum Feststellen, dass sie nicht existieren kann) benötigt wird, mit zunehmender Größe der Figur exponentiell zu. Wenn eine Figur beispielsweise 20 Verbindungspunkte von Linien hat, dauert die Lösung des Problems 3 bis zur zwanzigsten Potenz von Nanosekunden, dh einige Sekunden in Bezug auf die Zeiteinheiten, die wir gewohnt sind. Wenn die Zahl jedoch 60 Punkte beträgt, dauert die Suche nach einer Lösung 100-mal länger als unser geschätztes Alter des Universums.
Aber stellen wir uns vor: Jemand behauptet, eine solche dreifarbige Figur gemacht zu haben. Wir werden einige Zeit brauchen, um die Richtigkeit seiner Aussage zu überprüfen. Wir werden einfach nacheinander die Verbindungspunkte der Leitungen überprüfen. Wenn die Zahl wächst, erhöht sich auch die Prüfzeit langsam. Dies ist die sogenannte Polynomzeit. Infolgedessen stellt sich heraus, dass der Computer nicht viel mehr Zeit benötigt, um eine dreifarbige Figur mit 60 Eckpunkten zu überprüfen, als eine Figur mit 20 Verbindungspunkten.
"Es ist ziemlich einfach zu testen, ob diese Schaltung funktioniert, vorausgesetzt, es handelt sich um eine echte dreifarbige Figur", sagt der MIT-Physiker John Wright, der gemeinsam mit Anand Natarajan von Caltech eine neue Arbeit geschrieben hat. …
In den 1970er Jahren identifizierten Programmierer eine Klasse von Problemen, die leicht zu testen, aber manchmal schwer zu lösen sind. Sie gaben dieser Klasse den Namen NPT - nicht deterministische Polynomzeit. Seitdem haben viele Informatiker diese Probleme sehr intensiv untersucht. Insbesondere möchten Wissenschaftler wissen, wie sich diese Problemklasse ändert, wenn der Inspektor neue Möglichkeiten hat, die Richtigkeit der Lösung zu überprüfen.
RICHTIGE FRAGEN
Vor der Arbeit von Natarajan und Wright wurden zwei wichtige Entdeckungen gemacht, um die Richtigkeit der Lösung zu überprüfen. Sie haben unsere Fähigkeit, superharte Probleme zu testen, erheblich verbessert.
Stellen Sie sich vor, Sie sind farbenblind, um die Essenz der ersten Entdeckung zu verstehen. Zwei Würfel werden vor Ihnen auf den Tisch gelegt und Sie werden gefragt, ob sie dieselbe Farbe oder unterschiedliche Farben haben. Diese Aufgabe ist für Sie unmöglich. Darüber hinaus sind Sie nicht in der Lage, die Entscheidung einer anderen Person zu testen.
Aber Sie dürfen diese Person befragen, die wir den Prüfer nennen werden. Angenommen, der Prüfer sagt Ihnen, dass zwei Würfel unterschiedliche Farben haben. Wir werden den ersten Würfel mit dem Buchstaben "A" und den zweiten mit dem Buchstaben "B" bezeichnen. Sie nehmen die Würfel, verstecken sie hinter Ihrem Rücken und übertragen sie mehrmals von Hand zu Hand. Dann zeigen Sie die Würfel und bitten den Prüfer, Würfel A zu zeigen.
Wenn die Würfel unterschiedliche Farben haben, ist alles sehr einfach. Der Prüfer weiß, dass der Würfel A beispielsweise rot ist, und zeigt ihn jedes Mal richtig.
Aber wenn die Würfel dieselbe Farbe haben, das heißt, der Prüfer hat gelogen und gesagt, dass ihre Farbe unterschiedlich ist, kann er nur raten, wo sich der Würfel befindet. Aus diesem Grund zeigt er Würfel A nur in 50 Prozent der Fälle korrekt an. Dies bedeutet, dass Sie durch wiederholtes Fragen des Prüfers nach der Lösung deren Richtigkeit überprüfen können.
"Der Prüfer kann dem Prüfer Fragen stellen", sagte Wright. "Und vielleicht steigt am Ende des Gesprächs das Vertrauen des Prüfers."
1985 hat ein Trio von Programmierern bewiesen, dass solche interaktiven Proofs verwendet werden können, um Lösungen für Probleme zu testen, die komplexer sind als die NIP-Klasse. Als Ergebnis ihrer Arbeit erschien eine neue Klasse von Problemen namens IPT - die interaktive Polynomzeit. Mit der Methode zum Testen der Farbe zweier Würfel können Lösungen für komplexere Probleme und Fragen getestet werden.
Der zweite große Schritt wurde im selben Jahrzehnt unternommen. Alles hier folgt der Logik einer polizeilichen Untersuchung. Wenn Sie zwei Verdächtige haben, von denen Sie glauben, dass sie ein Verbrechen begangen haben, werden Sie sie nicht gemeinsam verhören. Sie werden sie in verschiedenen Räumen abfragen und dann die von ihnen gegebenen Antworten vergleichen. Wenn Sie diese Personen separat befragen, können Sie mehr über die Wahrheit erfahren, als wenn Sie nur einen Verdächtigen haben.
"Die beiden Verdächtigen werden nicht in der Lage sein, eine plausible und konsistente Version zu finden, weil sie die Antworten des anderen einfach nicht kennen", sagte Wright.
1988 bewies eine Gruppe von vier Informatikern, dass eine noch breitere Klasse von Problemen als IPV getestet werden könnte, wenn zwei Computer gebeten würden, dasselbe Problem getrennt zu lösen und dann getrennt nach den Antworten zu fragen. Diese Klasse heißt IDMD - interaktiver Beweis mit vielen Prüfern.
Mit diesem Ansatz kann man beispielsweise "Tricolor" -Probleme gegen eine Folge von Formen testen, deren Größe viel schneller wächst als Formen in nichtdeterministischer Polynomzeit. In der nicht deterministischen Polynomzeit nimmt die Größe der Formen linear zu - die Anzahl der Verbindungspunkte von Linien kann von 1 auf 2, dann auf 3, dann auf 4 usw. ansteigen. Daher wird es nie einen großen Unterschied in der Größe einer Figur geben, wie lange es dauert, ihre Trikolore zu testen. Wenn es sich jedoch um einen interaktiven Beweis mit vielen Beweisen handelt, steigt hier die Anzahl der Punkte in der Abbildung exponentiell an.
Infolgedessen werden diese Zahlen zu groß und passen nicht in den Speicher des überprüfenden Computers, weshalb er ihre Trikolore nicht überprüfen kann, indem er die Liste der Verbindungspunkte durchläuft. Es ist jedoch weiterhin möglich, die Trikolore zu überprüfen, indem den beiden Prüfern getrennte, aber verwandte Fragen gestellt werden.
In der IDMD-Problemklasse verfügt der Prüfer über genügend Speicher, um ein Programm auszuführen, um festzustellen, ob zwei Punkte in einer Form durch eine Linie verbunden sind. Der Prüfer kann dann jeden Prüfer bitten, einen der beiden durch eine Linie verbundenen Punkte zu benennen. Danach kann er die Antworten der Prüfer leicht vergleichen, um sicherzustellen, dass die dreifarbige Zahl korrekt ist.
Die Erhöhung des Niveaus von Aufgaben, die schwer zu lösen, aber leicht zu überprüfen sind, von NPV zu IPV und dann zu IDMD, könnte durch klassische Computer erreicht werden. Quantencomputer arbeiten anders. Jahrzehntelang war nicht klar, wie sie das Bild verändern, dh ob es schwieriger oder einfacher ist, die Lösung mit ihrer Hilfe zu überprüfen.
Neue Arbeiten von Natarajan und Wright geben eine Antwort auf diese Frage.
QUANTUM TÄUSCHUNG
Quantencomputer führen die Berechnung durch Manipulieren von Quantenbits (Qubits) durch. Sie haben eine seltsame Eigenschaft, deren Wesen darin besteht, dass sie miteinander verwechselt werden können. Wenn sich zwei Qubits oder sogar große Qubitsysteme miteinander verwickeln, bedeutet dies, dass ihre physikalischen Eigenschaften sie auf eine bestimmte Weise ausspielen.
In ihrer neuen Arbeit betrachten Natarajan und Wright ein Szenario mit zwei separaten Quantencomputern, die gemeinsame verschränkte Qubits teilen.
Es scheint, dass diese Art von Schema gegen die Validierung wirkt. Die Überzeugungskraft interaktiver Beweise bei vielen Prüfern wird genau dadurch erklärt, dass Sie zwei Prüfer getrennt befragen und dann ihre Antworten vergleichen können. Wenn diese Antworten übereinstimmen, sind sie höchstwahrscheinlich richtig. Wenn sich zwei Prüfer jedoch in einem verwirrten Zustand befinden, haben sie mehr Möglichkeiten, konsequent und konsequent falsche Antworten zu geben.
Als 2003 erstmals ein Szenario mit zwei verschränkten Quantencomputern vorgeschlagen wurde, schlugen die Wissenschaftler vor, dass die Verschränkung die Verifizierungsfähigkeiten schwächen würde. "Alle, einschließlich mir, hatten eine sehr offensichtliche Reaktion: Jetzt werden die Prüfer mehr Stärke und Überzeugungskraft haben", sagte Vidik. "Sie können Verschränkungen verwenden, um ihre Antworten zu koordinieren."
Trotz dieses anfänglichen Pessimismus verbrachte Vidic mehrere Jahre damit, das Gegenteil zu beweisen. 2012 hat er zusammen mit Tsuyoshi Ito bewiesen, dass es immer noch möglich ist, alle Probleme in der IDMD-Klasse mit Hilfe von verschränkten Quantencomputern zu testen.
Jetzt haben Natarajan und Wright bewiesen, dass die Situation noch besser ist. Eine breitere Klasse von Problemen kann mit Verschränkung getestet werden als ohne. Die Verbindungen zwischen verschränkten Quantencomputern können zum Nutzen des Prüfers gedreht werden.
Um zu verstehen, wie es geht, erinnern wir uns an das Verfahren zum Testen dreifarbiger Figuren, deren Größe exponentiell zunimmt, wenn ein interaktiver Beweis mit vielen Beweisen verwendet wird. Der Prüfer verfügt nicht über genügend Speicher, um die gesamte Form zu speichern, aber genug, um zwei verwandte Punkte zu identifizieren und die Prüfer zu fragen, welche Farbe sie haben.
Wenn wir über die Probleme sprechen, die Natarajan und Wright in Betracht ziehen - und die zur Klasse der nichtdeterministischen doppelten Exponentialzeit (NDEW) gehören -, nimmt die Größe der Zahl in ihnen noch schneller zu als im Problem der IDMD-Klasse. Die Zahl in NDEV wächst mit einer "doppelten Exponentialrate". Das heißt, es ist eine doppelte geometrische Folge. Die Zahl steigt nicht mit der Geschwindigkeit des 21., 22., 23. Grades, sondern "im Grad". Aus diesem Grund wachsen die Formen so schnell, dass der Prüfer kein einziges Paar verbundener Punkte finden kann.
"Es dauert 2n Bits, um einen Punkt zu markieren, der exponentiell größer ist als der Arbeitsspeicher des Verifizierers", sagt Natarajan.
Natarajan und Wright argumentieren jedoch, dass es möglich ist, die dreifarbige Färbung einer doppelt exponentiellen Figur zu testen, ohne bestimmen zu können, nach welchen Punkten die Prüfer gefragt werden sollen. Der Punkt ist, dass die Prüfer selbst Fragen stellen.
Laut Wissenschaftlern ist die Idee, Computer zu bitten, ihre eigenen Entscheidungen anhand der Abfragemethode zu überprüfen, ebenso vernünftig wie die Idee, Verdächtige eines Verbrechens zu bitten, sich selbst zu befragen. Das heißt, das ist völliger Unsinn. Natarajan und Wright argumentieren zwar, dass dies nicht der Fall ist. Der Grund ist Verwirrung.
"Verwickelter Zustand ist eine gemeinsam genutzte Ressource", sagt Wright. "Unser gesamtes Protokoll zielt darauf ab zu verstehen, wie diese gemeinsam genutzte Ressource zur Vorbereitung verwandter Fragen verwendet werden kann."
Wenn Quantencomputer verwirrt sind, wird ihre Auswahl der Punkte miteinander verbunden und sie geben die richtigen Fragen zum Testen der Trikolore.
Gleichzeitig muss der Prüfer die beiden Quantencomputer nicht zu eng miteinander verbinden, da ihre Antworten auf diese Fragen konsistent sind (dies entspricht der Tatsache, dass sich zwei Verdächtige untereinander auf ein falsches Alibi einigen). Ein weiteres seltsames Quantenmerkmal behebt dieses Problem. In der Quantenmechanik hindert uns das Unsicherheitsprinzip daran, gleichzeitig die Position eines Teilchens und den Impuls seiner Kraft zu kennen. Wenn Sie eine messen, zerstören Sie Informationen über die andere. Das Unsicherheitsprinzip schränkt Ihr Wissen über zwei "komplementäre" Eigenschaften eines Quantensystems stark ein.
Natarajan und Wright nutzten dies in ihrer Arbeit. Um die Farbe eines Scheitelpunkts zu berechnen, verwenden sie zwei Quantencomputer, die sich durch Messungen ergänzen. Jeder Computer berechnet die Farbe seiner Punkte und zerstört dabei alle Informationen über die Punkte des anderen Computers. Mit anderen Worten, die Verschränkung ermöglicht es Computern, miteinander verbundene Fragen zu formulieren, aber das Unsicherheitsprinzip verhindert, dass sie sich bei der Beantwortung verschwören.
"Wir müssen den Prüfer [über die falsche Version von Ereignissen] vergessen lassen, und dies ist die Hauptsache, die sie [Natarajan und Wright] in ihrer Arbeit getan haben", sagte Vidik. "Sie zwingen den Prüfer, die Informationen zu entfernen, wenn er Messungen vornimmt."
Ihre Arbeit hat enorme und sehr wichtige Konsequenzen. Bevor diese Arbeit erschien, war die Grenze des Wissensstands, den wir mit vollem Vertrauen haben konnten, signifikant niedriger. Wenn wir eine Antwort auf das IDMD-Problem erhalten würden, müssten wir es im Glauben akzeptieren, da wir keine andere Wahl haben. Aber Natarajan und Wright haben diese Einschränkung aufgehoben und es ermöglicht, Antworten auf viele weitere Rechenprobleme zu validieren.
Aber jetzt, da sie das getan haben, ist nicht klar, wo die Validierungsgrenze liegt.
"Dies könnte noch viel weiter gehen", sagte Lance Fortnow, Informatikforscherin am Georgia Institute of Technology. "Sie lassen Platz für einen weiteren Schritt."
Kevin Hartnett
