Akankah komputer kuantum memecahkan catur?

18

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?

MikhailTal
sumber
10
"Tapi sekarang, komputer kuantum akan segera tersedia" Sumber tentang ini?
Cleveland
5
Sebagai mahasiswa fisika, izinkan saya meyakinkan Anda bahwa komputer kuantum tidak akan digunakan untuk bermain catur dalam waktu dekat .
Danu
3
@Spork Anda bisa mengatakan hal yang sama tentang "Seorang teman saya menunjukkan kepada saya sebuah artikel"
Cleveland
3
@Cleveland bahwa satu begitu jelas saya ragu banyak orang akan menaruh banyak kepercayaan di dalamnya. Teman itu mungkin berbicara tentang permainan Xbox 2015 neowin.net/news/…
Spork
3
Komputer kuantum tidak bekerja dengan menyimpan informasi klasik senilai 2 ^ n bit dalam n qubit dan menggunakannya seperti komputer klasik.
JiK

Jawaban:

24

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:

NN - NN

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.

David Richerby
sumber
1
Saya tidak akan menjelaskan komputasi kuantum sebelumnya ... kami telah melihat kemajuan besar dalam masalah jenis pencarian grafik lainnya, seperti menggunakan anil kuantum untuk menyelesaikan masalah salesman keliling. Mungkin beberapa orang pintar bisa mengetahui bagaimana melakukan sesuatu yang serupa dalam catur? gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476
tbischel
2
@tbischel Tapi catur, pencarian pohon permusuhan, tidak terlihat sama sekali seperti TSP, yang merupakan masalah jarum-in-a-tumpukan jerami lainnya. Juga, perhatikan bahwa klaim DWave, harus kami katakan, cukup kontroversial . Setidaknya ada dua kelompok yang telah menulis simulasi anil kuantum yang mengungguli DWave ketika dijalankan pada laptop biasa, misalnya.
David Richerby
2
Saya tidak menyangkal bahwa saat ini tidak ada setara kuantum untuk mengatakan pencarian alpha beta ... tetapi mengingat bahwa algoritma komputasi kuantum masih dalam masa pertumbuhan, itu tidak berarti mereka tidak akan pernah ada. Sebagai contoh: web.ist.utl.pt/luis.tarrataca/publications/... Adapun DWave, saya mengenali kontroversi karena model mereka untuk komputasi kuantum berbeda dari model standar ... Saya akan mendekati mereka dengan hati-hati, walaupun mereka melakukannya. punya pelanggan seperti Google, NASA, dan NSA.
tbischel
Bukankah anil kuantum memecahkan catur?
Behrang Saeedzadeh
-1

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?

pengguna21914
sumber
-3

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:

Mari kita lihat perspektif yang lebih duniawi. Tampaknya adil untuk mengasumsikan bahwa, dengan teknologi yang ada, setiap operasi elementer entah bagaimana harus menyiratkan pergantian setidaknya satu gerbang logika. Daya switching gerbang CMOS tunggal adalah tentang C * V 2 di mana C adalah kapasitansi beban gerbang, dan V adalah tegangan di mana gerbang beroperasi. Pada 2011, gerbang yang sangat tinggi akan dapat berjalan dengan tegangan 0,5 V dan kapasitansi beban beberapa femtofarad ("femto" yang berarti "10 -15 "). Hal ini menyebabkan konsumsi energi minimal per operasi tidak kurang dari, katakanlah, 10 -15 J. Total konsumsi energi dunia saat ini adalah sekitar 500 EJ (5 * 10 20J) per tahun (atau begitulah kata artikel ini ). Dengan asumsi bahwa total produksi energi Bumi dialihkan ke perhitungan tunggal selama sepuluh tahun, kita mendapatkan batas 5 * 1036 , yang mendekati 2 122 .

Maka Anda harus memperhitungkan kemajuan teknologi. Mengingat tren saat ini pada keprihatinan ekologis dan minyak puncak , total produksi energi tidak boleh meningkat banyak di tahun-tahun mendatang (katakanlah tidak lebih dari faktor 2 hingga tahun 2040 - sudah menjadi mimpi buruk seorang ekologis). Di sisi lain, ada kemajuan teknologi dalam desain sirkuit terpadu. Hukum Moore menyatakan bahwa Anda dapat memuat dua kali lebih banyak transistor pada permukaan chip tertentu setiap dua tahun. Pandangan yang sangat optimis adalah bahwa penggandaan jumlah transistor ini dapat dilakukan dengan konsumsi energi yang konstan, yang akan berarti mengurangi separuh biaya energi operasi elementer setiap dua tahun. Hal ini akan menyebabkan grand total 2 138pada tahun 2040 - dan ini adalah perhitungan tunggal selama sepuluh tahun yang memobilisasi semua sumber daya dari seluruh planet ini.

Itu adalah jumlah maksimum absolut dari operasi elementer yang mungkin dapat dilakukan. Sekarang mari kita lihat berapa banyak posisi catur yang ada ...

Mari kita lakukan beberapa angka cepat. Masing-masing dari 64 kotak dapat kosong atau memegang salah satu dari 12 bagian yang berbeda (R, K, B, Q, K, dan P dalam hitam dan putih), sehingga jumlah total posisi yang dapat Anda atur paling banyak

13 64 = 196053476430761073330659760423566015424403280004115787589590963842248961.

Itu sekitar 2 x 10 71 posisi yang berbeda. Tentu saja ini terlalu tinggi perkiraannya, karena sebagian besar posisi palsu (kita harus menghilangkan posisi dengan tiga atau lebih raja, sembilan atau lebih bidak putih, bidak di peringkat kedelapan, cek empat kali lipat, dll). Mari kita ambil akar kuadrat:

13 32 = 442779263776840698304313192148785281,

atau sekitar 5 x 10 35 . Dengan mengambil akar kuadrat kita berpura-pura bahwa untuk setiap posisi hukum ada catur Semesta senilai posisi palsu yang berbeda. Ini mungkin perkiraan yang terlalu rendah, jadi jawaban yang benar harus ada di antara dua angka ini. Sekarang kami dapat dengan yakin mengatakan bahwa komputer tidak dapat mempelajari setiap posisi hukum dalam waktu yang wajar. Bahkan "kecil" 13 32 terlalu besar ...

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.

Jonathan Garber
sumber
1
Komputer kuantum tidak memiliki masalah dengan kapasitas. 2 ^ n vs n, jadi 2 ^ 120 posisi dalam string 64 byte, adalah 2 ^ 126 posisi, atau 2 ^ 129. komputer kuantum hanya membutuhkan 129 partikel kuanta untuk itu (secara teoritis). Karena kita akan memiliki teknologi untuk komputasi kuantum sampai saat itu, mungkin perhitungannya tidak akan mengambil semua sumber daya planet, atau semua ruang planet. Komputer yang dapat melakukan ini mungkin tidak akan lebih besar dari ruangan besar.
MikhailTal
1
Sepertinya ini mungkin salah paham tentang cara kerja komputer kuantum. Seperti yang saya pahami, qbits mewakili superposisi dari semua state, di mana komputasi tunggal (read gate transisi) beroperasi pada semua state secara bersamaan, mengembalikan hasilnya secara probabilistik. Argumen di atas berlaku untuk paradigma CMOS yang lebih tradisional.
tbischel
Saya pikir pertanyaan sebenarnya adalah apakah grafik dapat dicari cocok dengan paradigma komputasi kuantum ... Saya pernah mendengar bahwa ada hasil yang baik dalam menyelesaikan masalah salesman keliling dengan komputer kuantum, jadi mungkin ada pendekatan
tbischel
2
@ JonathanGarber Bagaimana Anda mendapatkan 2 ^ 126 atau 2 ^ 130? Dan saya tidak mengerti bagaimana gerbang CMOS terkait dengan memperkirakan kebutuhan daya komputer kuantum.
JiK
3
Jawaban ini pada dasarnya salah karena sepenuhnya tentang komputer klasik dan pertanyaannya adalah tentang komputer kuantum.
David Richerby