Wie viel Rechenleistung passt in einen Kubikzentimeter?

22

Diese Frage ist eine Fortsetzung der Frage zu DNA-Algorithmen, die Aadita Mehra gestellt hat .

In Kommentaren sagte Joe Fitzsimmons zum Teil:

Der Radius des Systems muss proportional zur Masse skaliert werden, um dies zu vermeiden. Die Rechenleistung skaliert höchstens linear in der Masse. Ihre exponentielle Maschinenmenge hat also einen exponentiellen Radius. Da Sie nicht schneller als mit Licht signalisieren können, dauert es exponentiell lange, bis ein Signal von einer Seite zur anderen gelangt. Wenn also alle Geräte zur Lösung beitragen, ist es unmöglich, das Problem in weniger als exponentiellen Schritten zu lösen Zeit.

Meine Frage besteht aus zwei Teilen.

(1) Wie lässt sich eine Aussage wie "Die Rechenleistung skaliert höchstens linear in der Masse" am besten formalisieren? Steht diese Aussage wirklich nicht zur Debatte?

(2) Angenommen, die Aussage ist wahr. Könnte die Natur jedoch bereits eine exponentielle Menge von Vorverarbeitungen durchgeführt haben, die wir nutzen könnten, beispielsweise die Schaffung von Sichtsystemen durch "Brute-Force-Randomisierung" durch die Evolution.

Ich habe eine ganze Reihe von leisen (pseudowissenschaftlichen) Antworten auf Fragen dieser Art gehört und gelesen, und ich wäre dankbar für alle Antworten, aber ich bin am meisten daran interessiert, wie (1) und (2) neu gefasst werden können in TCS Strenge.

Aaron Sterling
quelle
2
Eine möglicherweise verwandte Frage von Lance Fortnow: Wie
Kaveh
1
Seth Lloyd definiert maximale Rechenleistung als die maximale Anzahl grundlegender Quantenlogikoperationen pro Sekunde, die Gesetze der Thermodynamik für einen Computer mit gegebenem Gewicht und Volumen zulassen. Zusätzlich zu Joes Beiträgen gibt es hier einen populärwissenschaftlichen Bericht: puhep1.princeton.edu/~mcdonald/examples/QM/…
Yaroslav Bulatov

Antworten:

17

Die Aussage, die ich machte, war nicht besonders gut geschrieben. Ich bezog mich auf eine Kombination des Margolus-Levitin-Theorems (das die minimale Zeit zum Bewegen zwischen zwei orthogonalen Zuständen und damit eine untere Schranke für die zum Durchführen eines Gates erforderliche Zeit angibt) und des Schwarzschild-Radius (das den minimalen Radius von angibt) ein System fester Energie, bevor es ein Schwarzes Loch bildet). Die Kombination dieser beiden führt zu einer Obergrenze für die Anzahl der Gatter, die in einem festen Raumzeitbereich ausgeführt werden können. Sie können sich dies als die maximale Anzahl von Toren pro Zeiteinheit vorstellen, die ausgeführt werden können.

Die Idee, die beiden Theoreme zu kombinieren, stammt von Seth Lloyd, der mit einem solchen Ansatz Grenzen für die Rechenleistung des Universums aufzeigt ( Link ). Er hat auch eine andere Veröffentlichung, in der er die maximale Leistung untersucht, die mit einem 1 kg schweren Computer mit einem Volumen von 1 Liter erreicht werden kann (etwas, das er den ultimativen Laptop nennt und das fast genau Ihre Frage ist). Siehe arXiv . Er erhält ein Limit von Operationen pro Sekunde für Bits. Aufgrund des endlichen Alters des Universums und der endlichen Lichtgeschwindigkeit erhalten Sie in Kombination mit Lloyd's Ergebnissen eine konstante Obergrenze für die Vorverarbeitung.10511031

Joe Fitzsimons
quelle
Nur eine Einschränkung: Diese Gatter sind im Allgemeinen Quantengatter, daher ist diese Obergrenze eine Obergrenze für Quantenschaltungen, die mit einer ähnlich großen klassischen Schaltung möglicherweise nicht simuliert werden können.
Joe Fitzsimons