Da keine Antwort gegeben wurde, wurde ein Flag gesetzt, das die Konvertierung dieser Frage in ein Community-Wiki anfordert.
Die Kommentare von Aaron Sterling, Sasho Nikolov und Vor wurden in der folgenden Entschließung zusammengefasst, die für Community-Wiki-Diskussionen offen ist:
Behoben: In Bezug auf klassische Algorithmen, die Zahlen, Stichproben oder Simulationstrajektorien ausgeben, erfordert die strenge mathematische Logik, dass entweder alle vier der folgenden Sätze akzeptiert werden oder keiner von ihnen:
- Wir können einen klassischen Algorithmus zur Polynomzeit ausschließen, um Zufallszahlen zu erzeugen. [1]
- "Wir können einen klassischen Polynom-Zeit-Algorithmus ausschließen, um die Ausgabeverteilung eines Quantencomputers abzutasten, unter der alleinigen Annahme, dass die Polynom-Hierarchie unendlich ist." [2]
- "Wir können [eine quantenmechanische Flugbahn] auf die übliche Weise simulieren ... es gibt zu viele Variablen." [3]
- Die erweiterte Church-Turing-These (ECT) ist aus dem strengen Grund ausgeschlossen, dass klassische Algorithmen keine Zufallszahlen erzeugen können. [4]
Um die Diskussion einzuleiten, gibt es hier positive und negative Antworten, die, obwohl jeweils vertretbar, absichtlich überbewertet sind. Ein stark bejahendes Argument könnte sein:
Bejahend: Diese vier Aussagen spiegeln Theoreme wider, nach denen wir aus Gründen der Strenge niemals von klassischen Algorithmen sprechen müssen, die Zufallszahlen, Zufallsstichproben oder Quantensimulationen erzeugen, sondern nur von klassischen Algorithmen, die Pseudozufallszahlen erzeugen, und (von Erweiterung) Pseudozufallsstichproben und Pseudoquantensimulationen.
Wenn dies verstanden wird, sind alle vier Aussagen wahr. Um Mehrdeutigkeiten und Verwirrung zu vermeiden, sollten Mathematiker Wissenschaftler und Ingenieure außerdem ermutigen, das Präfix "Pseudo-" an fast allen Verwendungen von "Zufall", "Stichprobe" und "Quantensimulation" anzubringen.
Ein stark negatives Argument könnte sein:
Negativ: Diese Aussagen (und die damit verbundenen formalen Theoreme) sind Wegweiser, die uns zu einem „Rotlicht“ -Viertel der Mathematik im Lakatos-Stil führen, in dem wir aufgefordert werden, die Disziplinen der Pseudozufälligkeit enthusiastisch anzunehmen (was man so nennen könnte) , Pseudo-Sampling und Pseudo-Simulation… mathematische Praktiken, die aus einem köstlich sündigen Grund Spaß machen: Sie erzielen mathematische Effekte, die laut formaler Logik unmöglich sind. Was könnte magischer und lustiger sein als diese Schlussfolgerung: Die vier Aussagen der Entschließung sind formal formal wahr, aber praktisch falsch?
Wenn dies verstanden wird, sind alle vier Aussagen falsch. Da die meisten praktischen Aspekte von "Zufälligkeit", "Abtastung" und "Quantensimulation" in dieser magischen Umgebung auftreten, in der Probleme im Zusammenhang mit der Komplexität von Kolmogorov und orakelhaften Bewertungen absichtlich übersehen werden, sollten Mathematiker ihre Verwendung ändern.
Realistisch gesehen, wie sollten Komplexitätstheoretiker ihre Erkenntnisse in Bezug auf Zufälligkeit, Stichprobe und Simulation formulieren… einerseits, um ein angemessenes Gleichgewicht zwischen Klarheit, Präzision und Genauigkeit aufrechtzuerhalten… und andererseits, um ein angemessenes Gleichgewicht zu erreichen zur Aufrechterhaltung einer geräuscharmen Kommunikation mit anderen MINT-Disziplinen? Das letztere Ziel ist besonders wichtig, da die praktischen Fähigkeiten in Bereichen wie Kryptographie, statistische Tests, maschinelles Lernen und Quantensimulation stetig zunehmen.
Es wäre sehr hilfreich (und auch erfreulich), gut begründete Antworten zu lesen, entweder positiv oder negativ.
Die gestellte Frage ist
Was ist / sind die allgemein anerkannten Rollen der Verifikation in den komplexitätstheoretischen Definitionen, die mit der Probenahme, Simulation und Prüfung der ECT-These (Extended Church-Turing) verbunden sind?
Die bevorzugte Antwort sind Verweise auf Artikel, Monographien oder Lehrbücher, in denen diese Themen ausführlich behandelt werden.
Sollte sich diese Literatur als spärlich oder auf andere Weise unbefriedigend erweisen, werde ich diese Frage (nach zwei Tagen) in ein Community-Wiki umwandeln und fragen:
Was ist / sind eine vernünftige und angemessene Rolle (n) der Verifikation in den komplexitätstheoretischen Definitionen, die mit der Probenahme, Simulation und Prüfung der ECT-These (Extended Church-Turing) verbunden sind?
Hintergrund
Die gestellte Frage ist motiviert durch den aktuellen Thread "Was würde es bedeuten, die These von Church-Turing zu widerlegen?" , insbesondere die (meiner Meinung nach ausgezeichneten) Antworten von Gil Kalai und Timothy Chow
In der gestellten Frage ist der Ausdruck "richtige und / oder akzeptierte komplexitätstheoretische Definitionen" so auszulegen, dass Alice von unplausiblen Behauptungen wie den folgenden abgehalten wird:
Alice: Hier ist meine experimentelle Stichprobe von wirklich zufälligen Binärziffern, die von meinem linearen optischen Netzwerk (mit einem Photon) berechnet wurden.
Bob: Hier ist meine simulierte Stichprobe von Pseudozufallszahlen, die von einer klassischen Turing-Maschine berechnet wurden.
Alice: Sorry Bob ... deine Probe ist algorithmisch komprimierbar und meine nicht. Daher zeigen meine experimentellen Daten, dass die ECT falsch ist! "
In Ermangelung eines Zusammenhangs zwischen Überprüfung und Probenahme ist Alices Argumentation einwandfrei. Mit anderen Worten, sollten Komplexitätstheoretiker das ECT als bereits vor Jahrzehnten formell widerlegt betrachten?
Aus praktischer Sicht sind Simulationsmethoden, die mit der Probenahme von Quantenbahnen auf verschiedenen Zustandsräumen verbunden sind, in vielen Disziplinen der Wissenschaft und Technik weit verbreitet. Aus diesem Grund wären komplexitätstheoretische Definitionen von Stichproben, die die zentrale Rolle der Verifikation (die untrennbar mit der Reproduzierbarkeit verbunden ist) in Wissenschaft und Technik berücksichtigen, für praktizierende Wissenschaftler und Ingenieure sehr willkommen, insbesondere wenn diese Definitionen von Theoremen begleitet würden, die die rechnerische Komplexität von beschreiben verifizierte Probenahme.
Edit hinzugefügt: Dank einer Zusammenarbeit zwischen der Universität Genf und der Firmen- ID Quantique ist es durchaus möglich, diese Übung in der Realität durchzuführen.
Hier sind 1024 zufällige Bits, die von id Quantique als algorithmisch inkompressibel zertifiziert wurden :
0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011
Sollten wir jetzt die Behauptung akzeptieren: "Die ECT-These ist widerlegt"?
Wenn nicht, welche Gründe sollten wir angeben?
quelle
Antworten:
Der Kern der Frage ist angesichts der Tatsache, dass die Quantenwahrscheinlichkeit eine Quelle wahrer Zufälligkeit ist, wie wirkt sich dies auf die erweiterte (oder effiziente oder polynomielle) Church-Turing-These aus?
Die Antwort ist, dass es laut Vermutung keinen Einfluss darauf hat. Die Leute vermuten, dass BPP = P ist, dh dass randomisierte Algorithmen mit Pseudozufallszahlengeneratoren mit Polynom-Overhead derandomisiert werden können. Der Glaube an PRNGs als Ersatz für echte Zufälligkeit ist ein Grund, warum die Menschen der erweiterten Church-Turing-These glauben würden, wenn sie nicht für die Quantenberechnung verwendet würden.
quelle