Quanta energia computacional cabe em um centímetro cúbico?

22

Esta pergunta é uma continuação da pergunta sobre algoritmos de DNA feita por Aadita Mehra .

Nos comentários, Joe Fitzsimmons disse, em parte:

[O] raio do sistema deve escalar proporcionalmente à massa para evitar isso. A potência computacional escala no máximo linearmente na massa. Assim, sua quantidade exponencial de maquinaria tem um raio exponencial. Como você não pode sinalizar mais rápido que a luz, um sinal de um lado para outro leva um tempo exponencialmente longo para chegar ao outro lado; portanto, se todas as máquinas contribuírem para a resposta, é impossível resolver o problema em menos do que exponencial Tempo.

Minha pergunta tem duas partes.

(1) Qual é a melhor maneira / formal de formalizar uma afirmação como "O poder computacional escala no máximo linearmente na massa"? Esta afirmação não está realmente em debate?

(2) Suponha que a afirmação seja verdadeira. Mesmo assim, a natureza poderia ter realizado uma quantidade exponencial de pré-processamento, da qual poderíamos usar, por exemplo, a criação de sistemas de visão pela evolução por meio da "randomização da força bruta".

Ouvi e li um bom número de respostas suaves (pseudocientíficas) para perguntas desse tipo e ficaria grato por todas as respostas aqui, mas estou mais interessado em como (1) e (2) podem ser reformuladas no rigor do TCS.

Aaron Sterling
fonte
2
Uma questão possivelmente relacionada por Lance Fortnow: qual é o volume de informações?
Kaveh
1
Seth Lloyd define potência computacional máxima como o número máximo de operações básicas da lógica quântica por segundo que as leis da termodinâmica permitem para um computador com peso e volume determinados. Além de papéis de Joe, aqui está uma conta de ciência popular puhep1.princeton.edu/~mcdonald/examples/QM/...
Yaroslav Bulatov

Respostas:

17

A afirmação que fiz não foi particularmente bem escrita. Eu estava me referindo a uma combinação do teorema de Margolus-Levitin (que dá o tempo mínimo para se mover entre dois estados ortogonais e, portanto, um limite mais baixo para o tempo necessário para executar uma porta) e o raio de Schwarzschild (que fornece o raio mínimo de um sistema de energia fixa antes de formar um buraco negro). A combinação dos dois leva a um limite superior do número de portas que podem ser executadas em uma região fixa do espaço-tempo. Você pode pensar nisso como o número máximo de portas por unidade de tempo que pode ser executado.

10511031

Joe Fitzsimons
fonte
Apenas uma ressalva: esses portões são em geral portões quânticos, portanto esse limite superior é um limite superior para circuitos quânticos, que podem não ser simuláveis ​​com um circuito clássico de tamanho semelhante.
93010 Joe Fitzsimons