Berapa banyak daya komputasi yang pas dengan sentimeter kubik?

22

Pertanyaan ini merupakan tindak lanjut dari pertanyaan tentang algoritma DNA yang ditanyakan oleh Aadita Mehra .

Dalam komentar di sana, Joe Fitzsimmons berkata, sebagian:

Jari-jari sistem harus berskala proporsional dengan massa untuk menghindari hal ini. Kekuatan komputasi berskala paling linear dalam massa. Dengan demikian jumlah mesin Anda yang eksponensial memiliki radius eksponensial. Karena Anda tidak dapat memberi sinyal lebih cepat daripada cahaya, sinyal dari satu sisi ke sisi lain membutuhkan waktu yang lama secara eksponensial untuk mencapai sisi lainnya, dan jadi jika semua mesin berkontribusi pada jawaban, mustahil untuk menyelesaikan masalah dalam waktu kurang dari eksponensial. waktu.

Pertanyaan saya ada dua bagian.

(1) Apa cara / cara terbaik untuk memformalkan pernyataan seperti, "Kekuatan komputasi berskala paling linear dalam massa"? Apakah pernyataan ini benar-benar tidak cocok untuk diperdebatkan?

(2) Misalkan pernyataan itu benar. Meski begitu, mungkinkah alam telah melakukan sejumlah besar preprocessing eksponensial yang mungkin dapat kita manfaatkan, misalnya penciptaan sistem visi evolusi melalui "pengacakan brute force".

Saya telah mendengar dan membaca cukup banyak jawaban lunak (pseudoscientific) untuk pertanyaan-pertanyaan semacam ini, dan saya akan berterima kasih atas jawaban apa pun di sini, tetapi saya sangat tertarik dengan bagaimana (1) dan (2) dapat disusun kembali dalam kekakuan TCS.

cc.complexity-theory quantum-computing ne.neural-evol physics natural-computing Aaron Sterling
sumber
2
Sebuah pertanyaan yang mungkin terkait oleh Lance Fortnow: berapa volume informasi?
Kaveh
1
Seth Lloyd mendefinisikan daya komputasi maksimum sebagai jumlah maksimum operasi logika kuantum dasar per detik yang memungkinkan hukum termodinamika untuk komputer dengan berat dan volume tertentu. Selain makalah Joe, berikut ini adalah akun sains populer puhep1.princeton.edu/~mcdonald/examples/QM/…
Yaroslav Bulatov

Jawaban:

17

Pernyataan yang saya buat tidak ditulis dengan baik. Saya merujuk pada kombinasi teorema Margolus-Levitin (yang memberikan waktu minimum untuk bergerak antara dua keadaan orthogonal, dan karenanya batas bawah pada waktu yang diperlukan untuk melakukan gerbang) dan jari-jari Schwarzschild (yang memberikan jari-jari minimum dari sebuah sistem energi tetap sebelum membentuk black hole). Menggabungkan kedua mengarah ini ke batas atas pada jumlah gerbang yang dapat dilakukan di wilayah ruangwaktu tetap. Anda dapat menganggap ini sebagai jumlah maksimum gerbang per satuan waktu yang dapat dilakukan.

10511031

Joe Fitzsimons
sumber
Hanya peringatan: gerbang-gerbang ini pada umumnya gerbang kuantum, jadi batas atas ini adalah batas atas untuk sirkuit kuantum, yang mungkin tidak dapat disimulasikan dengan sirkuit klasik berukuran sama.
Joe Fitzsimons