Analoge Computer und die Church-Turing-These

9

Ich möchte aus Nielsen & Chuang, Quantenberechnung und Quanteninformation, Ausgabe zum 10-jährigen Jubiläum, Seite 5 (Schwerpunkt Mine) zitieren:

Eine Klasse von Herausforderungen für die starke Church-Turing-These kommt aus dem Bereich der analogen Berechnung. In den Jahren seit Turing haben viele verschiedene Forscherteams festgestellt, dass bestimmte Arten von analogen Computern Probleme effizient lösen können, von denen angenommen wird, dass sie auf einer Turing-Maschine keine effiziente Lösung bieten. Auf den ersten Blick scheinen diese analogen Computer die starke Form der Church-Turing-These zu verletzen. Unglücklicherweise für die analoge Berechnung stellt sich heraus, dass bei realistischen Annahmen über das Vorhandensein von Rauschen in analogen Computern deren Leistung in allen bekannten Fällen verschwindet. Sie können Probleme, die auf einer Turing-Maschine nicht effizient gelöst werden können, nicht effizient lösen.Diese Lektion - dass die Auswirkungen von realistischem Rauschen bei der Bewertung der Effizienz eines Rechenmodells berücksichtigt werden müssen - war eine der großen frühen Herausforderungen der Quantenberechnung und der Quanteninformation, eine Herausforderung, die durch die Entwicklung einer Theorie des Quantenfehlers erfolgreich bewältigt wurde -Korrekturcodes und fehlertolerante Quantenberechnung. Im Gegensatz zur analogen Berechnung kann die Quantenberechnung daher im Prinzip eine endliche Menge an Rauschen tolerieren und dennoch ihre Rechenvorteile beibehalten.

Ist dies eine Aussage, dass Rauschen schneller skaliert als eine Potenz der Problemgröße, oder kann mich jemand in die richtige Richtung weisen, damit ich mehr darüber herausfinden kann, ob diese Skalierungsgrenzen grundlegend sind oder nur ein "technisches Problem"?

Um es klar zu sagen, ich frage, ob analoge Computer Turing-Maschinen aufgrund von Rauschen nicht effizienter schlagen können.

Löwenbriten
quelle
1
Die Literatur und Meinungsbeiträge der Vergangenheit, die ich gelesen habe, legen nahe, dass es sich um eine grundlegende Frage der physikalischen Gesetze handelt (zum Beispiel die Existenz reeller Zahlen). Wenn Sie in Scott Aaronsons Schriften stöbern, werden Sie von Zeit zu Zeit darüber diskutieren. Ich habe nichts Überlegeneres und Tieferes gefunden. In dieser Phase definitiv nicht "nur" ein technisches Problem. Es ist im Moment teilweise im Hof ​​der Philosophen.
Mdxn
Ich denke, das ist interessant, aber es ist nicht zu klar, wenn Sie nach Rauschen in den analogen Modellen oder Rauschen in den qm-Modellen usw. fragen. Tatsächlich ist Rauschen bei der QM-Berechnung ein offenes Problem an den Grenzen der Forschung, das die letztendliche theoretische und praktische Realisierbarkeit stark beeinträchtigt.
vzn

Antworten:

6

Zunächst scheinen die Autoren zwei verschiedene Thesen zu verwechseln: die Church-Turing-These und die Cook-Karp-These. Der erste betrifft das, was berechenbar ist, und der zweite betrifft das, was effizient berechenbar ist .

Nach der Cook-Karp-These sind alle vernünftigen "starken" Rechenmodelle in dem Sinne polynomisch äquivalent, dass sie sich alle polynomiell simulieren. Entsprechend kann jedes vernünftige Rechenmodell von einer Turing-Maschine polynomiell simuliert werden. Quantencomputer sind ein Gegenbeispiel zu dieser These, da sie exponentiell effizienter zu sein scheinen als klassische Computer. Sie sind jedoch kein Gegenbeispiel zur Church-Turing-These, dh mit Quantencomputern können Sie nichts berechnen, was Sie mit einer Turing-Maschine noch nicht berechnen können. Wir können auch eine aktualisierte Cook-Karp-These formulieren, die besagt, dass alle physikalisch realisierbaren Rechenmodelle von Quantencomputern polynomiell simuliert werden.

Es wurden verschiedene physikalische Modelle von Berechnungen vorgeschlagen, um diese Thesen in Frage zu stellen, aber unter der Prüfung scheinen sie alle nicht gegen die Church-Turing-These zu verstoßen oder nicht leistungsfähiger zu sein als die Quantenberechnung. Scott Aaronson schlägt vor, diese Situation als "Naturgesetz" zu betrachten. Soweit ich weiß, gibt es jedoch keine theoretischen Argumente, die diese Thesen stützen, außer dem induktiven Argument, dass gezeigt wurde, dass alle vorgeschlagenen Modelle diesen entsprechen.

Yuval Filmus
quelle
Ich denke, was Sie die Cook-Karp-These nennen, ist ihre verstärkte Version der CT-These. Vielen Dank für die Antwort, ich brauche etwas Zeit, um sie sorgfältig zu lesen.
Lionelbrits
Vielen Dank für Ihre Antwort. Ich habe den Aufsatz zu diesem Thema von Scott Aaronson zuvor gelesen und ihn erneut gelesen. Ich denke, der Kern meiner Frage ist, ob mich jemand auf "mehrere physikalische Modelle von Berechnungen" hinweisen kann, die auf den ersten Blick gegen die These verstoßen. Ich weiß, dass Fredkin mit Cams gearbeitet hat, aber ich bin mir nicht sicher, ob das ein ernsthafter Anwärter sein sollte.
Lionelbrits
1
Scott Aaronson hat dazu mehrere Vorträge gehalten. Zum Beispiel video.ias.edu/computationconference/2014/1122-ScottAaronson .
Yuval Filmus
5

Diese Passage (vor über einem Jahrzehnt geschrieben) ist in der Tat der Schlüssel und ruft einiges an Hintergrundwissen hervor und antizipiert sehr gut einige zukünftige Forschungsrichtungen. Es spielt auf das Gebiet der Hyperberechnung an, das manchmal am Rande von TCS liegt, weil es Rechenmodelle untersucht, die angeblich "leistungsfähiger" sind als Turing-Maschinen. Das Interessante an Turing-Maschinen ist, dass sie geräuschfrei sind. In gewissem Sinne basiert die Informatik auf dieser Idealisierung, die in gewisser Weise physikalisch unrealistisch ist. und elektronische Systeme ahmen diese Geräuschlosigkeit als Konstruktionsprinzip nach. Sie ist immer in der Chipdynamik auf niedriger Ebene vorhanden, wird jedoch in den Konstruktionen auf höherer Ebene, die alle elektrischen Signale auf ideale 0/1-Bits beschränken, sehr effektiv abstrahiert. Zu diesem Thema:

Diese Lektion - dass die Auswirkungen von realistischem Rauschen bei der Bewertung der Effizienz eines Rechenmodells berücksichtigt werden müssen - war eine der großen frühen Herausforderungen der Quantenberechnung und der Quanteninformation, eine Herausforderung, die durch die Entwicklung einer Theorie des Quantenfehlers erfolgreich bewältigt wurde -Korrekturcodes und fehlertolerante Quantenberechnung.

es scheint, dass einige ihrer Behauptungen im Nachhinein eher vorzeitig optimistisch aussehen. Es ist wahr, dass große Mengen an Theorie in QM-Fehlerkorrekturcodes entwickelt wurden. Es wurde jedoch nur sehr wenig experimentell getestet und verifiziert. Es gibt einige Wissenschaftler / Experten, die vermuten / vermuten, dass es physikalische Gesetze gibt, die erfordern, dass Rauschen für größere n-Bit-Quantensysteme "schlecht" skaliert. Es ist also ein Bereich aktiver Forschung und einiger Kontroversen. Tatsächlich ist dies ein Hauptstreitpunkt für zwei führende QM-Computing-Designs / -Ansätze , einen von DWave-Systemen und einen von der Martinis UCSB / Google-Gruppe .

Um es klar zu sagen, ich frage, ob analoge Computer Turing-Maschinen aufgrund von Rauschen nicht effizienter schlagen können.

Das ist die große Frage, nicht wahr? Um dies zu beantworten, bedenken Sie, dass es klassische analoge Systeme und die neueren Quantensysteme gibt. Für klassische Systeme ist der allgemeine Konsens, wie von Nielsen / Chuang skizziert, dass es theoretische Modelle gibt, die " leistungsfähiger " erscheinen, aber wenn Rauschen korrekt berücksichtigt wird, "schmilzt" dieser theoretische "Vorteil" "weg". Mit anderen Worten, die Existenz analoger Computersysteme "grundsätzlich theoretisch schneller" als bereits gebaute elektronische Systeme vorzuschlagen, scheint die Gesetze der Physik / Thermodynamik nahezu zu verletzen.

Die Frage für das QM-Computing ist jedoch viel offener und hängt (wie sie etwas erwarten) von der Art des QM-Rauschens ab und davon, ob es tatsächlich experimentell / kontrolliert werden kann, wie angenommen wurde und derzeit untersucht wird.

Es gibt eine tiefere Analyse dieser Probleme in Aaronsons Artikel NP-vollständige Probleme und physikalische Realität . Die skeptische Übersicht findet sich in Dyakonov Prospects for Quantum Computing: äußerst zweifelhaft .

vzn
quelle
Beachten Sie, dass der Begriff "analoges System" lange vor dem QM-Computing im Gegensatz zu digitalen / diskreten Systemen (wie in der diskreten Mathematik ) steht und daher etwas schwierig ist.
vzn