Das recht neue und aufregende Gebiet der Quantenrechner scheint bereit, die These zur sequentiellen Berechenbarkeit herauszufordern. Es besteht die Möglichkeit (gering allerdings, wenn man die Anzahl der Wissenschaftler zählt, die so denken), daß dieses neue Berechnungsmodell einige undurchführbare Probleme in durchführbare und praktisch berechenbare verwandeln könnte.

Quantencomputer gehen völlig neue Wege. Sie beruhen auf der Quantenmechanik, einem verlockenden und paradoxen Teil der Physik des 20. Jahrhunderts. Es wurden bereits einige überraschend effiziente Quantenalgorithmen für Probleme entdeckt, von denen man nicht weiß, ob sie im klassischen Sinne durchführbar sind. Um sie verwenden zu können, müßte man jedoch zuerst einen Quantencomputer bauen: ein spezielles Gerät, das es bislang noch nicht wirklich gibt.

Der Analyse von Deutsch zufolge lassen Quantencomputer sich nicht zum Ausführen nicht-algorithmischer Operationen benutzen (das heißt für Aufgaben jenseits der Fähigkeiten einer Turing-Maschine); sie können aber in bestimmten sehr künstlichen Situationen eine höhere Geschwindigkeit erreichen - im Sinne der Komplexitätstheorie - als eine normale Turing-Maschine. Bislang sind diese Ergebnisse angesichts einer so faszinierenden Idee ein bißchen enttäuschend, aber noch ist nicht aller Tage Abend.