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 :).
quelle
Antworten:
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).
quelle