Apa yang diketahui tentang keefektifan komputasi yang andal?

Seberapa baik masalah berikut telah diselidiki di TCS? (Saya minta maaf jika pernyataan masalah terdengar kabur!)

Diberikan Model Komputasi MC (Mesin Turing, Cellular Automata, Mesin Kolmogorov-Uspenskii ... dll.) Dan Model Kebisingan yang dapat memengaruhi perhitungan MC, apakah ada cara untuk memulihkan dari kesalahan yang disebabkan oleh kebisingan ini di cara yang efektif ? Sebagai contoh, katakanlah beberapa jenis kebisingan mempengaruhi Mesin Turing M, dapatkah seseorang merancang Mesin Turing M 'yang mensimulasikan M tanpa biaya besar dan dapat diandalkan (yang berarti bahwa M' toleran terhadap kebisingan ini)?

Tampaknya beberapa model perhitungan lebih baik daripada yang lain dalam melakukan ini: Cellular Automata misalnya. Adakah hasil jika kebisingan diganti oleh model musuh?

Maaf atas tagnya! Saya tidak memiliki reputasi yang cukup untuk memasang tag yang sesuai (komputasi andal, toleransi-kesalahan-komputasi ... dll.)

Meskipun ada beberapa teknik yang dapat diterapkan pada toleransi kesalahan untuk semua model, seberapa tahan model komputasi terhadap toleransi kesalahan tergantung pada model. Misalnya, Peter Gacs telah melakukan sedikit riset dengan toleransi kesalahan pada automata seluler, dan dia menunjukkan bahwa (dengan banyak pekerjaan) Anda dapat membangun automata seluler toleran-kesalahan.

Von Neumann membuktikan bahwa dengan menggunakan redundansi, Anda dapat membangun komputer yang andal dari komponen yang tidak dapat diandalkan hanya dengan menggunakan overhead logaritmik.

Untuk perhitungan kuantum, sirkuit kuantum dapat dibuat toleran terhadap kesalahan dengan overhead polylogarithmic ( overhead, di mana menemukan nilai benar masih terbuka). Pertanyaan terbuka lain untuk perhitungan kuantum adalah apakah perhitungan kuantum adiabatik dapat dibuat toleran terhadap kesalahan dengan cara yang masuk akal secara fisik (wajar secara fisik berarti ada kemungkinan bahwa metode tersebut mengarah ke komputer kuantum adiabatik yang dapat diskalakan; misalnya, Anda tidak diizinkan untuk mengambil suhu ke 0 saat ukuran perhitungan semakin besar).$\log^c n$$c$

Saya pikir pekerjaan yang berkaitan dengan stabilisasi diri dekat dengan semangat pertanyaan Anda.

Sistem stabilisasi diri pulih dari segala kerusakan RAM.

Pertanyaan yang diajukan adalah "Apakah ada cara untuk memulihkan dari kesalahan yang disebabkan oleh kebisingan [kuantum] secara efektif?" dan jawaban Peter Shor secara mengagumkan mencakup satu cara efektif untuk menjawab pertanyaan ini, yaitu dengan merancang komputer kuantum yang toleran terhadap kesalahan.

Cara efektif alternatif sangat umum ditemui dalam praktek teknik. Kami beralasan "Jika kebisingannya cukup besar sehingga tidak ada perhitungan kuantum yang layak, maka mungkin dinamika sistem dapat disimulasikan dengan sumber daya klasik di P."

Dengan kata lain, seringkali kita dapat "pulih dengan cara yang efektif" dari noise dengan mengakui bahwa noise menyediakan layanan yang penting bagi kita, dengan secara eksponensial mengurangi kompleksitas komputasi dengan mensimulasikan sistem klasik dan kuantum.

Literatur tentang pendekatan noise-centric untuk simulasi dinamis besar dan berkembang; referensi baru-baru ini yang teorema keduanya termotivasi secara fisik dan menyenangkan, dan yang mencakup banyak referensi ke literatur yang lebih luas, adalah batas atas Plenio dan Virmani pada batas toleransi kesalahan komputer kuantum berisik berbasis Clifford (arXiv: 0810.4340v1).

Dinamika klasik menggunakan bahasa yang sangat berbeda di mana mekanisme kebisingan menggunakan nama teknis termostat ; Frenkel dan Smit's Understanding Molecular Simulation: from Algorithms to Applications (1996) memberikan pengantar matematika dasar.

Ketika kami menuliskan termostat klasik dan kuantum ke dalam bahasa dinamika geometrik, kami menemukan (tidak mengejutkan) bahwa metode klasik dan kuantum untuk mengeksploitasi kebisingan untuk meningkatkan efisiensi simulasi pada dasarnya identik; bahwa literatur masing-masing yang begitu jarang merujuk satu sama lain sebagian besar adalah suatu kecelakaan sejarah yang ditopang oleh penghambatan notasi.

Kurang keras tapi lebih umum, hasil di atas menerangi asal-usul dalam teori informasi kuantum dari aturan heuristik yang secara luas dianut oleh ahli kimia, fisikawan, dan ahli biologi, bahwa sistem klasik atau kuantum yang ada dalam kontak dinamis dengan pemandian termal cenderung membuktikan disimulasikan dengan sumber daya komputasi dalam P untuk semua tujuan praktis (FAPP).

Pengecualian heuristik ini, baik klasik dan kuantum, merupakan masalah terbuka yang penting. Jumlah mereka sangat berkurang dari tahun ke tahun; dua tahunan Kritis Penilaian Struktur Prediksi (CASP) menyediakan satu ukuran yang obyektif dari perbaikan ini.

Batas mendasar untuk kemajuan kemampuan simulasi yang digerakkan oleh kebisingan, beberapa dekade ini, "More than Moore" saat ini diketahui secara tidak sempurna. Tidak perlu dikatakan lagi, dalam jangka panjang pemahaman kita yang terus meningkat akan batas-batas ini akan membawa kita lebih dekat untuk membangun komputer kuantum, sementara dalam jangka pendek, pengetahuan ini sangat membantu kita dalam mensimulasikan sistem secara efisien yang bukan komputer kuantum. Either way, ini kabar baik.

Sepertinya Gacs sedang dalam perjalanan membangun mesin Turing yang toleran terhadap kesalahan. Lihatlah ini: http://arxiv.org/abs/1203.1335

Model Quantum Computing secara eksplisit berurusan dengan noise dan cara-cara membuat komputasi tangguh terhadap kesalahan yang diperkenalkan melalui vektor ini. Komputasi Quantum, anehnya, dapat dilakukan maju dan mundur (pada dasarnya transformasi QM Hadamard dan waktu kemerdekaan Hamiltonian) - "uncomputing" adalah salah satu teknik yang digunakan untuk membendung gelombang kesalahan tersebut.

Pada komputer 'nyata' - Server perusahaan - ada peluang kecil namun layak bahwa sedikit RAM akan terbaca salah. Teori deteksi kesalahan dan koreksi kode dapat diterapkan pada level kata mesin untuk mendeteksi dan memperbaiki kesalahan 1-bit tersebut (tanpa terlalu banyak overhead). Dan sebenarnya banyak server Enterprise yang memiliki operasi kritis mengundang sedikit paritas pada setiap kata RAM.

Walaupun jauh dari bukti, bagi saya kelihatannya skema pengkodean koreksi kesalahan standar dapat dibuat untuk bekerja dengan hampir semua automata teoretis (automata seluler dicurigai) dengan hanya pelambatan polinomial (pada kenyataannya linier?).

$k$$k$$k$$k$