Generieren von "unendlicher" Zufälligkeit aus einer konstanten Anzahl von Quellen

11

Ich bin kürzlich auf einen Artikel von Coudron und Yuen über die Zufälligkeitserweiterung mit Quantengeräten gestoßen . Das Hauptergebnis der Arbeit ist, dass es möglich ist, aus einer konstanten Anzahl von Quellen eine "unendliche" Zufälligkeit zu erzeugen (dh die Anzahl der erzeugten Zufallsbits hängt nur von der Anzahl der Runden des Protokolls und nicht von der Anzahl der Quellen ab ).

Naiv klingt dies für mich so, als ob das Ergebnis die Derandomisierung jedes randomisierten Algorithmus mit Quantenquellen ermöglicht und eine Art Eingrenzung randomisierter Komplexitätsklassen innerhalb einer entsprechenden Quantenklasse implizieren würde.

Aber ich verstehe die Quanteninformationstheorie nicht wirklich und bin mir sicher, dass mir viele Feinheiten fehlen. Ganz zu schweigen davon, dass die Autoren es geschafft hätten, wenn solche Behauptungen möglich gewesen wären. Meine Frage lautet also:

Bedeutet die Existenz einer "unendlichen Zufälligkeitserweiterung", wie in der Arbeit (und allen damit verbundenen Arbeiten) beschrieben, eine Art Derandomisierungsaussagen für randomisierte Komplexitätsklassen? Und wenn nicht, warum nicht?

Update: Ich wurde auf diesen hervorragenden Überblick auf hoher Ebene über das Gebiet und das obige Papier von Scott Aaronson hingewiesen . Leider bin ich immer noch verwirrt :).

Suresh Venkat
quelle
2
Nicht direkt auf die Frage eingehen, aber hier ist eine weitere allgemeine Beschreibung und Diskussion des Gebiets und des Ergebnisses eines der beiden Autoren im MIT Theory-Blog .
Clement C.
Ich denke, die Erweiterung der Quantenzufälligkeit befasst sich mit einer orthogonalen Frage zur Derandomisierung. Insbesondere wird davon ausgegangen, dass Sie bereits Geräte haben, die zufällige Bits erzeugen können. Die angesprochene Frage ist die Überprüfung der Zufälligkeit dieser Geräte, für die selbst randomisierte Tests erforderlich sind. Die Erweiterung bezieht sich darauf, wie viel Zufälligkeit für den Test benötigt wird und wie viel neue Zufälligkeit von den Geräten während des Tests erzeugt wird.
Thomas unterstützt Monica

Antworten:

15

Das ist eine großartige Frage, Suresh!

Unser Zufälligkeit Expansion Ergebnis ist nicht impliziert jedes komplexitätstheoretischen Ergebnis. Hier ist eine Möglichkeit, das Ergebnis zu verstehen: Wir glauben, dass die Quantenmechanik die Welt regiert, und unter dieser Annahme gibt es Quantengeräte, die echte, wahre, informationstheoretische Zufälligkeit erzeugen.

Stellen Sie sich jedoch vor, Sie sind misstrauisch gegenüber diesen Boxen, die behaupten, dieses wackelige Quantenmaterial zu machen und Zufälligkeit zu erzeugen (für einige ist dies möglicherweise nicht zu viel Vorstellungskraft erforderlich). Sie wollen nicht mit Qubits umgehen. Alles was Sie verstehen sind klassische Bitstrings.

Die Zufallserweiterung ist ein Protokoll, bei dem Sie als klassischer Prüfer mit einer Reihe von Blackboxen interagieren können (stellen Sie sich diese als nicht kommunizierende Prüfer vor ). Nachdem Sie ein Protokoll mit diesen Blackboxen ausgeführt haben, haben Sie bestätigt, dass ihre Ausgaben enthalten sind sehr hohe Entropie - wenn die Prüfer bestehen. Darüber hinaus ist die Zufälligkeit, mit der Sie begonnen haben, viel geringer als die von Ihnen zertifizierte Ausgabeentropie.

Mit anderen Worten, es ist ein interaktiver Beweis für die Erzeugung von Zufälligkeiten.

Der einzige "Derandomisierungs" -Aspekt besteht darin, zu argumentieren, dass das Protokoll selbst eine geringe Zufälligkeit beim Start erfordert. Das Ergebnis ist jedoch sehr un-randomisiert: Die von den Boxen erzeugte Ausgabe ist echte Zufälligkeit, keine Pseudozufälligkeit (dh keine rechnerischen Annahmen).

Henry Yuen
quelle
1
Aha. Während in einem "normalen" Derandomisierungsargument (etwa über einen Expander) der "Algorithmus-Designer" einen Korrektheitsnachweis erstellt. Hier ist es ein tatsächlicher interaktiver Beweis, der einen Beweis der Zufälligkeit erstellt, der anders ist.
Suresh Venkat
Das ist genau richtig!
Henry Yuen