Teorinya adalah bahwa ada lebih dari 10 ^ 40 posisi, dan komputer yang bekerja dengan skala atom harus sangat besar (Seperti dalam skala galaksi), dan jauh melampaui tingkat pengetahuan kita saat ini.
Tetapi sekarang, komputer kuantum akan segera tersedia. Komputer ini dapat memiliki 2 ^ n, bukannya n byte ruang, karena status kuantum. Dengan tempat baru yang besar ini untuk tablebase, akankah catur diselesaikan? Tentu saja, ini akan mengambil lebih banyak terobosan di masa depan, tetapi apakah kita akan melihat 8 buah database di tahun-tahun berikutnya?
Banyak pertanyaan tentang kemungkinan penyelesaian catur berputar pada kenyataan bahwa kita tidak memiliki cukup ruang komputer untuk mengisinya. Akankah komputer kuantum mengubah status quo?
sumber
Jawaban:
Saya bukan ahli dalam komputasi kuantum tetapi pemahaman saya adalah bahwa komputer kuantum tidak diharapkan berguna untuk catur.
Algoritma Quantum sangat baik dalam menemukan jarum di tumpukan jerami: tiga algoritma kuantum besar adalah algoritma faktorisasi Shor , algoritma pencarian database Grover dan algoritma Deutsch-Jozsa, yang pada dasarnya menentukan apakah daftar panjang angka adalah semua nol, semua satu atau setengah dari masing-masing. Semua masalah ini dapat dilihat sebagai contoh "Saya telah menyembunyikan sesuatu: Anda harus menemukannya dengan cepat." Dalam faktorisasi, saya telah "menyembunyikan" faktor prima dan Anda harus menemukannya; dalam pencarian basis data, saya telah menyembunyikan entri dengan kunci yang diberikan dalam tabel besar yang tidak disortir dan Anda harus menemukannya; dalam masalah yang diselesaikan oleh Deutsch – Jozsa, saya mungkin telah menempatkan sejumlah besar nol dalam tabel yang tetapi, dengan algoritma klasik, ketika Anda melihat setengah tabel dan hanya melihat yang, Anda mungkin hanya beruntung dan melihat setengah "salah". Perhatikan juga bahwa semua masalah ini dapat diselesaikan dengan cepat oleh komputer klasik paralel paralel: Anda bisa mencoba semua faktor secara paralel,
Memecahkan catur bahkan tidak sedikit seperti masalah ini. Ini adalah aktivitas yang secara fundamental berurutan. Apakah langkah saya baik atau tidak tergantung pada apa yang Anda lakukan sebagai respons. Baik atau tidaknya respons Anda tergantung pada apa yang saya lakukan sebagai respons terhadap itu. Dan seterusnya. Anda mungkin membayangkan Anda dapat melakukan langkah pertama pencarian dengan mengambil superposisi dari gerakan yang mungkin. Tapi apa yang Anda lakukan pada lapis kedua? Anda tidak bisa hanya mengambil superposisi dari semua posisi yang kita dapat setelah dua lapis karena itu telah melupakan struktur pohon. Misalnya, pertimbangkan posisi yang sangat artifisial ini, dengan warna putih untuk dipindahkan:
Jika kita melupakan struktur pohon, Black sangat senang. Dia berkata, "Dalam dua lapis, posisi terbaik yang bisa saya miliki adalah saya memberikan skakmat!" Ini benar tetapi, tentu saja, White tidak akan pernah membiarkan itu, karena langkah terbaik White adalah yang mencegah Black dari skakmat (atau melakukan hal lain). Catur bukan tentang mencari tahu langkah terbaik yang bisa Anda buat dalam Nply: ini tentang mencari tahu langkah terbaik yang akan memungkinkan lawan Anda bermain dalam N ply. Komputer kuantum tampaknya tidak bagus dalam penalaran bolak-balik, memberi dan menerima ini. Kami bahkan tidak tahu bagaimana menyelesaikan catur dengan komputer klasik paralel yang tidak realistis.
sumber
Ini harus diucapkan secara verbal apa yang sebenarnya berarti 'solusi untuk catur'.
Kemudian kita akan mengerti apa sebenarnya yang bisa kita dapatkan dari pemecah catur kotak hitam hipotetis (BBCS).
Kami akan memberi makan BBCS dengan posisi papan catur.
BBCS akan mengeluarkan angka integer X. 0 berarti tidak ada solusi untuk posisi itu (atau posisi itu sendiri tidak sah) Angka integer lain berarti jumlah gerakan yang paling sedikit untuk mengubah posisi asli menjadi posisi skakmat di dalam non-kooperatif permainan catur. Solusi terbaik untuk catur hanya akan berupa angka integer yang berarti jumlah gerakan yang tepat dari posisi awal catur ke posisi skakmat. Apakah ini tugas untuk komputer kuantum? IDK. Sebagai pencarian David Richerby - catur bukan untuk QC. Tetapi ketika kita harus menemukan bilangan bulat tunggal X untuk menyatakan "pasangan dalam gerakan X" sepertinya lebih suka menemukan jarum di tumpukan jerami ... Apakah saya salah?
sumber
Peringatan yang adil: Jawaban ini berisi angka spekulatif, dan mungkin tidak sesuai dengan urutan besarnya.
Itu hanya mungkin, tetapi tidak mungkin.
Masalahnya tidak selalu dengan apakah komputer kuantum akan dapat "memparalelkan" sampai sejauh itu. Masalahnya adalah salah satu fisika sederhana, yang bahkan komputer kuantum tidak dapat secara realistis menyiasati. Sederhananya, ada sejumlah perhitungan yang dapat dilakukan. Ini dijawab oleh Thomas Pornin di Security.SE, dan saya mengutip beberapa jawabannya di sini:
Itu adalah jumlah maksimum absolut dari operasi elementer yang mungkin dapat dilakukan. Sekarang mari kita lihat berapa banyak posisi catur yang ada ...
Angka terkecil itu berakhir di sekitar 120 atau lebih.
Mari kita asumsikan bahwa kita mewakili papan kita dengan string 64-byte. (Praktisnya akan ditangani sedikit berbeda, tetapi mari kita lanjutkan untuk sekarang.) Jika saya mengingat matematika saya dengan benar, komputer kuantum akan dapat mewakili ini dengan string 8-byte, atau 64 bit. Ini membuat kami memiliki total 2 126 hingga 2 130 operasi dasar hanya untuk menyimpan setiap posisi hukum dan kemungkinan .
Lihat itu sebentar. Kami tidak melakukan sesuatu yang berguna dengan informasi tersebut, kami hanya menyimpannya. Dan untuk itu kami memobilisasi sumber daya seluruh planet . Tidak masalah di mana penyimpanan berada. Abaikan seluruh masalah pendinginan. Singkirkan masalah transmisi data. Kami mengalihkan kekuatan yang cukup untuk menerangi Bulan hanya untuk menyimpan posisi.
Pada harapan yang paling optimis, komputer kuantum mungkin dapat menyelesaikan catur, dengan mengorbankan sumber daya seluruh planet. Secara realistis, itu tidak akan terjadi.
sumber