Bedeutet dieser Artikel, dass Turing-Berechenbarkeit nicht dasselbe ist wie „effektiv berechenbar“?

Zunächst entschuldige ich mich, wenn dies gefragt wurde, aber ich habe wirklich nichts gefunden.

Ich bin über diesen Artikel gestolpert . Es heißt, dass es ein Problem gibt, das nur Quantencomputer lösen können. Nach meinem Verständnis sollte dies intuitiv bedeuten, dass dieses Problem "effektiv berechenbar" ist, da wir eine effektive, reale Methode haben, um es zu berechnen: einen Quantencomputer bauen und es lösen. Aber da eine Turing-Maschine (Turing-Maschinen sind keine Quantencomputer, glaube ich?) Sie nicht lösen kann, ist dies nicht turing-berechenbar.

Bedeutet dies also, dass "effektiv berechenbar" und "turing-berechenbar" nicht dasselbe Konzept sind? Ist die These von Church-Turing also falsch? Meine Intuition sagt "nein", denn in diesem Fall wäre dies eine sehr große Neuigkeit. Wenn nicht, warum nicht?

Mir ist auch bewusst, dass es bereits Rechenmodelle gibt, die leistungsfähiger sind als Maschinen, aber diese sind nur "theoretisch", nicht wahr? Quantencomputer hingegen sind physisch baubar.

Es gibt viele verschiedene Bedeutungen des Wortes "kann". Gibt es einen Algorithmus, der die AES-512-Verschlüsselung aufheben kann? Eine Strategie wäre, alle 2 ^ 512 möglichen Blöcke mit 512 Bits zu nehmen, alle mit dem öffentlichen Schlüssel zu verschlüsseln und für jeden von ihnen zu prüfen, ob sie mit dem Chiffretext übereinstimmen. In einem rein abstrakten Sinne ist dies ein Algorithmus, der AES-512 "brechen" kann. Aus praktischer Sicht wäre es nicht möglich, alle 2 ^ 512 Blöcke zu überprüfen, wenn die gesamte Materie im bekannten Universum in Computer umgewandelt und das Programm auf ihnen bis zum Hitzetod des Universums ausgeführt würde.

Daher gibt es ein abstraktes, theoretisches Konzept der "Dose", das die Menge der benötigten Ressourcen nicht berücksichtigt, und eine praktische Bedeutung, die dies tut.

Turing Computability befasst sich mit der ersten Art von "Dose". Eine Turing-Maschine ist ein Gerät, das unbegrenzt lange mit unbegrenztem Speicher betrieben werden darf. Es ist ein abstraktes Modell zur Formulierung theoretischer Behauptungen. In der realen Welt gibt es tatsächlich kein echtes TM.

Es besteht also kein Widerspruch zwischen der Behauptung einerseits, dass ein Quantencomputer alles kann, was ein TM auch kann, und andererseits der Behauptung, dass es Probleme gibt, die ein Quantencomputer lösen kann, aber kein klassischer Computer lösen; Ein tatsächlicher Computer unterliegt Einschränkungen hinsichtlich der Computerleistung, die ein TM nicht hat.

Erstens sind Quantencomputer (oder besser gesagt theoretische Quantenberechnungsmodelle) in der Tat nicht leistungsfähiger als Turing-Maschinen, da sie auf einer Turing-Maschine emuliert werden können und eine Turing-Maschine selbst emulieren können. Beachten Sie, dass der Artikel selbst aus gutem Grund nicht das Wort "berechenbar" verwendet. Berechenbarkeit ist nicht das, worüber sie sprechen.

Der Unterschied zwischen Quantencomputern und klassischen ist die Geschwindigkeit. Hier kommt die Komplexitätstheorie ins Spiel. Hier sind alle Probleme, die wir betrachten, berechenbar, aber einige können im Hinblick auf die asymptotische Laufzeit oder die Speichernutzung sehr ineffizient zu lösen sein.

Die Polynomhierarchie (PH) ist eine große Klasse, die Probleme enthält, die im Grunde genommen ein alternierendes Spiel zwischen dem nicht deterministischen Erraten einer Lösung und dem Finden eines (oder vielmehr alternierenden existenziellen und universellen Quantifizierers) sind, jedoch alle in Polynomzeit. P ist die grundlegendste Klasse innerhalb der PH und entspricht in etwa den Problemen, die wir auf klassischen Computern in angemessener Zeit lösen können. NP ist eine weitere grundlegende Unterklasse von PH.

BQP ist das Analogon für P für Quantencomputer. Nun, nicht ganz, BQP ist näher an BPP, wo wir unserem klassischen Computer erlauben, mit nur geringer Wahrscheinlichkeit eine falsche Antwort zu geben. Die Quanteneffekte können nicht wirklich genutzt werden, ohne die Wahrscheinlichkeit auf sinnvolle Weise einzubeziehen. In jedem Fall befindet sich BPP immer noch innerhalb von PH.

In diesem Artikel geht es um ein Problem, das nachweislich nicht in PH, sondern in BQP liegt. In gewisser Weise ermöglicht der 'Quantenschritt' die Lösung eines Problems, das P oder BPP nicht einmal klassisch nahe kommt, nicht einmal in derselben unendlichen Hierarchie, in Polynomzeit auf einem Quantencomputer. Dies ist also ein starker Beweis für die (theoretische) Leistung des Quantencomputermodells.

Was die Church-Turing-These betrifft, so widerspricht die Quantenberechnung, die schneller als die klassische ist, nicht, da sich die Arbeit nicht um die Rechenzeit kümmert. Die stärkere Extended Church-Turing-These wird jedoch durch dieses Ergebnis widerlegt (dh wenn skalierbare Quantencomputer tatsächlich gebaut werden).