Boson Sampling , manchmal auch als BosonSampling bezeichnet, ist ein attraktives Kandidatenproblem, um die Quantenüberlegenheit zu etablieren. Die technischen Probleme scheinen überwindbarer zu sein als die, die mit einem Turing-vollständigen Quantencomputer verbunden sind.

Die Boson-Abtastung hat jedoch den Nachteil, dass die Ausgabe eines photonischen Quantencomputers, der die Boson-Abtastung mit nur einer Handvoll ( oder so) Qubits ausführen kann, möglicherweise nicht einmal klassisch simuliert werden kann. Dies steht natürlich im Gegensatz zu N P -Problemen wie Factoring, deren technische Aspekte erheblich schwieriger sind.$\le 100$$\mathsf{NP}$

Wir können also die Ergebnisse der Boson-Probenahme an ungefähr Photonen ermitteln, aber um die Ergebnisse zu verifizieren, müssen wir die Permanente einer 100 × 100- Matrix berechnen. Dies ist bekanntermaßen rechenintensiv zu überprüfen. $100$$100\times100$

Vielleicht kann ein Supercomputer, der leistungsfähig genug ist, um die bleibende Karte zu berechnen, den Trick machen. Aber dann würde jeder glauben , haben sowohl die Ergebnisse der Supercomputer und die Boson Ergebnisse der Probenahme.

Gibt es etwas an Boson Sampling, das leicht überprüft werden kann?

Ich hatte Lust, die Ressourcen eines Cryptocurrency-Mining-Netzwerks für die Berechnung einer solchen permanenten Datenmenge zu nutzen und mich bei der öffentlichen Überprüfung auf einige / I P- Tricks zu verlassen, bin aber noch nicht weit gekommen.$\mathsf{\#P}$$\mathsf{IP}$

BEARBEITEN

Ich mag die Antwort von @ gIS.

$\mathsf{PCP}$

Über die Notwendigkeit der Überprüfung der Boson-Probenahme

Lassen Sie mich zunächst darauf hinweisen, dass es nicht unbedingt erforderlich ist, die Ausgabe eines Boson-Samplers zu überprüfen . Damit will ich nicht sagen, dass es nicht nützlich oder interessant ist, dies zu versuchen, sondern dass es in gewisser Weise eher eine praktische als eine grundlegende Notwendigkeit ist.

Ich denke, Sie selbst haben dafür ein gutes Argument vorgebracht, wenn Sie schreiben

Vielleicht kann ein Supercomputer, der leistungsfähig genug ist, um die bleibende Karte zu berechnen, den Trick machen. Aber dann müsste jeder sowohl den Ergebnissen des Supercomputers als auch den Ergebnissen der Boson-Probenahme glauben.

In der Tat gibt es viele Fälle, in denen man ein Problem löst und einer Lösung vertraut, die nicht wirklich vollständig verifiziert werden kann. Ich meine, vergiss die Quantenmechanik, benutze einfach deinen Computer, um zwei große Zahlen zu multiplizieren. Sie haben wahrscheinlich ein hohes Vertrauen, dass das Ergebnis korrekt ist, aber wie können Sie es überprüfen , ohne einen anderen Computer zu verwenden?

Im Allgemeinen beruht das Vertrauen in die Ergebnisse eines Geräts auf einer Vielzahl von Faktoren, z. B. dem Wissen über die innere Funktionsweise des Geräts und dem Unit-Test des Geräts selbst (dh dem Testen, ob es für die speziellen Instanzen, die Sie überprüfen können , ordnungsgemäß funktioniert mit einer anderen Methode).

Das Problem der Boson-Probenahme-Zertifizierung ist nicht anders. Wir wissen, dass wir irgendwann die Ausgabe eines Boson-Samplers nicht mehr vollständig überprüfen können, aber das bedeutet nicht, dass wir ihm nicht vertrauen können. Wenn das Gerät mit der gebotenen Gründlichkeit erstellt wurde und seine Ausgabe für eine Vielzahl kleiner Instanzen überprüft wird und andere Tests, die durchgeführt werden können, alle erfolgreich sind, baut man irgendwann genug Vertrauen in das Gerät auf, um eine zu erstellen Quantum Supremacy Claim (oder was auch immer man sonst noch für den Boson Sampler verwenden möchte) sinnvoll.

Gibt es etwas an BosonSampling, das leicht überprüft werden kann?

Ja, es gibt Eigenschaften, die überprüft werden können. Aufgrund der Stichprobenart des Problems schließen Menschen normalerweise alternative Modelle aus, die möglicherweise die beobachteten Stichproben erzeugt haben. Zum Beispiel zeigten Aaronson und Arkhipov ( 1309.7460 ), dass die BosonSampling-Verteilung weit von der gleichmäßigen Verteilung der Gesamtvariationsentfernung entfernt ist (mit hoher Wahrscheinlichkeit über die Haar-Zufallsmatrizen, die die Verteilung induzieren), und gaben ein Protokoll zur effizienten Unterscheidung der beiden Verteilungen an. Eine neuere Arbeit, die zeigt, wie statistische Signaturen verwendet werden können, um die Verteilung der Bosonenproben anhand alternativer Hypothesen zu zertifizieren, ist ( Walschaers et al. 2014 ).

Alle anderen mir bekannten Arbeiten konzentrieren sich auf die Zertifizierung bestimmter Aspekte eines Boson-Samplers, anstatt das Problem der Suche nach alternativen Verteilungen, die weit von der BosonSampling-Verteilung für zufällige Interferometer entfernt sind, direkt anzugehen.

Insbesondere kann man zwei mögliche Hauptfehlerquellen in einem Boson-Probenahmegerät isolieren: diejenigen, die sich aus einer fehlerhaften Implementierung des Interferometers ergeben, und diejenigen, die sich aus den Eingangsphotonen ergeben, die nicht das sind, was sie sollten (dh völlig ununterscheidbar).

Der erste Fall ist (relativ) einfach zu handhaben, da man ein Interferometer mit Einzelphotonen effizient charakterisieren kann. Es ist jedoch schwieriger, die Ununterscheidbarkeit der Eingangsphotonen zu bestätigen. Eine Idee, dies zu tun, besteht darin, das Interferometer in ein nicht zufälliges Interferometer wie das QFT-Interferometer zu ändern und zu prüfen, ob in diesem einfacheren Fall etwas effizient verifiziert werden kann. Ich werde nicht versuchen, alle relevanten Referenzen hier hinzuzufügen, aber diese Richtung begann mit (Tichy et al. 2010 , 2013 ).

In Bezug auf den Aspekt der öffentlichen Überprüfung wurde in dieser Richtung nichts unternommen, von dem ich gehört habe. Ich bin mir auch nicht sicher, ob es überhaupt eine besonders sinnvolle Richtung ist, dies zu untersuchen: Warum sollten wir für einen Boson-Sampler einen so "hohen Standard" der Überprüfung benötigen, wenn wir für praktisch jede andere Art von Experiment damit zufrieden sind, den Menschen zu vertrauen, die das tun experimentieren, um gut zu sein, was sie tun?

Nur eine kleine Ergänzung zu @gIS ausgezeichnete Antwort: Ich kenne mehrere Personen (einschließlich mich selbst), die sich für den Aspekt der öffentlichen Überprüfung interessieren. Soweit ich weiß, sind alle Versuche gescheitert, daher der Mangel an Literatur zu diesem Thema: Sobald man nachweisen kann, dass der Boson-Sampler richtig funktioniert hat, ist es in der Tat ein Regime, in dem der Boson-Sampler klassisch effizient simuliert werden kann.

$IQP$$IQP$$P$