Terobosan Komputasi Kuantum Utama Mengguncang Fisika Dan Matematika

Terobosan Komputasi Kuantum Utama Mengguncang Fisika Dan Matematika

Terobosan Komputasi Kuantum Utama Mengguncang Fisika Dan Matematika – MIP * = RE bukan salah ketik. Ini adalah penemuan inovatif dan judul menarik dari makalah terbaru di bidang teori kompleksitas kuantum. Teori kompleksitas adalah kebun binatang “kelas kompleksitas” kumpulan masalah komputasi di mana MIP * dan RE hanyalah dua.

Makalah 165 halaman menunjukkan bahwa kedua kelas ini adalah sama. Itu mungkin tampak seperti detail yang tidak penting dalam teori abstrak tanpa penerapan di dunia nyata. Tapi fisikawan dan matematikawan berbondong-bondong mengunjungi kebun binatang, meski mereka mungkin tidak mengerti semuanya. Karena ternyata penemuan tersebut memiliki konsekuensi yang mencengangkan bagi disiplin ilmu mereka sendiri.

Terobosan Komputasi Kuantum Utama Mengguncang Fisika Dan Matematika

Pada tahun 1936, Alan Turing menunjukkan bahwa Masalah Halting secara algoritme memutuskan apakah program komputer berhenti atau berputar selamanya tidak dapat diselesaikan. Ilmu komputer modern lahir. Keberhasilannya memberi kesan bahwa segera semua masalah praktis akan menghasilkan kekuatan yang luar biasa dari komputer. idn poker 99

Tapi segera menjadi jelas bahwa, sementara beberapa masalah dapat diselesaikan secara algoritmik, komputasi sebenarnya akan bertahan lama setelah Matahari kita menelan komputer yang melakukan komputasi. Mencari tahu bagaimana memecahkan masalah secara algoritmik saja tidak cukup. Sangat penting untuk mengklasifikasikan solusi berdasarkan efisiensi. Teori kompleksitas mengklasifikasikan masalah berdasarkan seberapa sulit untuk menyelesaikannya. Kekerasan suatu masalah diukur dalam hal berapa lama komputasi berlangsung.

RE adalah singkatan dari masalah yang dapat diselesaikan dengan komputer. Itu adalah kebun binatang. Mari kita lihat beberapa subclass.

Kelas P terdiri dari masalah-masalah yang dapat diselesaikan dengan cepat oleh algoritma yang diketahui (secara teknis, dalam waktu polinomial). Misalnya, mengalikan dua bilangan adalah milik P karena perkalian panjang adalah algoritma yang efisien untuk menyelesaikan soal. Masalah menemukan faktor prima dari sebuah bilangan tidak diketahui di P; Masalahnya pasti bisa diselesaikan dengan komputer tapi tidak ada algoritma yang dikenal bisa melakukannya secara efisien. Masalah terkait, memutuskan apakah nomor yang diberikan adalah prima, berada di limbo sama sampai 2004 ketika algoritma yang efisien menunjukkan bahwa masalah ini adalah di P.

Kelas kompleksitas lainnya adalah NP. Bayangkan labirin. “Apakah ada jalan keluar dari labirin ini?” adalah pertanyaan ya / tidak. Jika jawabannya ya, maka ada cara sederhana untuk meyakinkan kami: cukup beri kami petunjuk arah, kami akan mengikuti mereka, dan kami akan menemukan jalan keluar. Namun, jika jawabannya tidak, kami harus melintasi seluruh labirin tanpa pernah menemukan jalan keluar untuk diyakinkan.

Masalah ya / tidak yang, jika jawabannya ya, kami dapat secara efisien menunjukkan bahwa, milik NP. Setiap solusi untuk suatu masalah berfungsi untuk meyakinkan kita akan jawabannya, dan P terkandung dalam NP. Anehnya, pertanyaan jutaan dolar adalah apakah P = NP. Tidak ada yang tahu.

Percaya Pada Mesin

Kelas yang dijelaskan sejauh ini mewakili masalah yang dihadapi oleh komputer normal. Tetapi komputer secara fundamental berubah komputer kuantum sedang dikembangkan. Tetapi jika komputer jenis baru muncul dan mengklaim dapat memecahkan salah satu masalah kita, bagaimana kita bisa percaya bahwa itu benar?

Bayangkan sebuah interaksi antara dua entitas, seorang interogator dan seorang prover. Dalam interogasi polisi, penguji mungkin adalah tersangka yang mencoba membuktikan bahwa mereka tidak bersalah. Penginterogasi harus memutuskan apakah penguji tersebut cukup meyakinkan. Ada ketidakseimbangan; Secara pengetahuan, interogator berada dalam posisi inferior.

Dalam teori kompleksitas, interogator adalah orang, dengan kekuatan komputasi terbatas, yang mencoba memecahkan masalah. Pembuktiannya adalah komputer baru, yang diasumsikan memiliki daya komputasi yang sangat besar. Sistem bukti interaktif adalah protokol yang dapat digunakan interogator untuk menentukan, setidaknya dengan probabilitas tinggi, apakah pembuktian itu harus dipercaya. Dengan analogi, ini adalah kejahatan yang mungkin tidak dapat diselesaikan oleh polisi, tetapi setidaknya orang yang tidak bersalah dapat meyakinkan polisi bahwa mereka tidak bersalah. Ini adalah IP kelas.

Jika banyak penguji dapat diinterogasi, dan penguji tidak diizinkan untuk mengoordinasikan jawaban mereka (seperti yang biasanya terjadi ketika polisi menginterogasi banyak tersangka), maka kami masuk ke kelas MIP. Interogasi semacam itu, melalui pemeriksaan silang tanggapan para pembukti, memberikan interogator kekuatan yang lebih besar, sehingga MIP berisi IP.

Komunikasi kuantum adalah baru bentuk komunikasi dilakukan dengan qubit. Keterikatan fitur kuantum di mana qubit terjerat secara seram , bahkan jika terpisah membuat komunikasi kuantum berbeda secara fundamental dengan komunikasi biasa. Mengizinkan pembukti MIP untuk berbagi qubit terjerat mengarah ke kelas MIP *.

Tampak jelas bahwa komunikasi antara pembukti hanya dapat berfungsi untuk membantu pembukti mengoordinasikan kebohongan daripada membantu interogator dalam menemukan kebenaran. Karena alasan itu, tidak ada yang menyangka bahwa mengizinkan lebih banyak komunikasi akan membuat masalah komputasi lebih andal dan dapat dipecahkan. Anehnya, kita sekarang tahu bahwa MIP * = RE. Ini berarti komunikasi kuantum berperilaku sangat berbeda dengan komunikasi normal.

Implikasi Yang Menjangkau Jauh

Pada tahun 1970-an, Alain Connes merumuskan apa yang kemudian dikenal sebagai Masalah Penanaman Connes. Sangat disederhanakan, ini menanyakan apakah matriks tak hingga dapat didekati dengan matriks hingga. Makalah baru ini sekarang telah membuktikan bahwa ini tidak mungkin sebuah temuan penting bagi ahli matematika murni.

Terobosan Komputasi Kuantum Utama Mengguncang Fisika Dan Matematika

Pada tahun 1993, Boris Tsirelson menunjuk sebuah masalah dalam fisika yang sekarang dikenal sebagai Masalah Tsirelson. Ini tentang dua formalisme matematika yang berbeda dari satu situasi dalam mekanika kuantum hingga saat ini teori yang sangat sukses yang menjelaskan dunia subatomik. Menjadi dua deskripsi yang berbeda dari fenomena yang sama diharapkan bahwa kedua formalisme itu setara secara matematis.

Tetapi makalah baru sekarang menunjukkan bahwa mereka tidak melakukannya. Bagaimana tepatnya mereka berdua masih dapat memberikan hasil yang sama dan keduanya menggambarkan realitas fisik yang sama tidak diketahui, tetapi itulah sebabnya fisikawan juga tiba-tiba tertarik. Waktu akan memberi tahu pertanyaan ilmiah apa yang belum terjawab akan menghasilkan studi tentang kompleksitas. Tidak diragukan lagi, MIP * = RE adalah lompatan besar ke depan.