Bagaimana komputasi kuantum akan mengubah pemrograman? [Tutup]

Bagaimana pemrograman algoritma kuantum berbeda? Akan seperti apa bahasa C jika dirancang untuk qubit? Apakah tipe akan berubah?

Ketika saya melihat ini beberapa waktu yang lalu, jelas bahwa algoritma kuantum, meskipun tidak terlalu cepat, memungkinkan paralelisme masif secara eksponensial. Jadi mereka akan bersinar dalam kasus yang melibatkan pencarian di ruang yang tidak praktis dengan perangkat keras sekuensial, bahkan perangkat keras sekuensial paralel besar-besaran.

Salah satu sifat dari algoritma kuantum adalah mereka harus dapat dibalik . Algoritma apa pun yang diberikan dapat diterjemahkan ke dalam satu yang dapat dibalikkan, dengan menambahkannya pada pencatatan yang cukup untuk memungkinkannya dijalankan mundur.

Properti lainnya adalah bahwa mendapatkan jawaban dari algoritma kuantum adalah masalah hit-and-miss, karena apa yang Anda dapatkan pada akhir perhitungan adalah beberapa jawaban, masing-masing dengan probabilitasnya sendiri. Itu perlu dijalankan sedemikian rupa sehingga jawaban yang Anda inginkan memiliki probabilitas tinggi. Ini mungkin melibatkan menjalankan algoritme maju dan mundur beberapa kali.

Lihat Algoritma Pencarian Grover .

Dimasukkan untuk menunjukkan operasi dasar dari algoritma Grover. Misalkan ada masalah pencarian. Jawaban yang mungkin adalah 0, 1, 2, dan 3, tetapi jawaban yang tepat adalah 2. Jadi komputer kuantum ditempatkan di superposisi keempat negara, dan ia melewati serangkaian langkah-langkah untuk melihat mana yang benar, dan membalikkan amplitudonya, seperti titik dan panah hitam di bawah ini:

Anda dapat melihat bahwa panah 2 telah terbalik di dalam mesin, tetapi tidak ada cara untuk mengatakannya di luar, karena hanya probabilitas yang terlihat di luar, yang merupakan amplitudo kuadrat , dan ketika kuadrat mereka semua sama.

Namun, amplitudo memiliki rata-rata, ditunjukkan oleh garis merah, dan komputer dapat dibuat untuk melewati serangkaian langkah yang membalikkan setiap amplitudo tentang rata-rata . Ketika itu selesai, amplitudo, dan probabilitas, pindah ke status 2, jawaban yang tepat ! Jadi jika mesin diamati, nyatakan 2 bersinar.

Tidak sesederhana ini. Umumnya dibutuhkan beberapa siklus mesin, maju dan mundur, membalik pada akhir setiap siklus, untuk memaksimalkan probabilitas jawaban yang benar. Juga, seseorang harus berhati-hati untuk tidak melakukannya lebih dari itu beberapa kali, karena dapat dengan mudah membalikkan dirinya sendiri.

Jadi mengapa mereka mengatakan komputer kuantum sangat cepat ? Karena setiap kali Anda menggandakan jumlah qubit, Anda menyejajarkan paralelisme, tetapi Anda tidak menguadratkan lamanya waktu, sehingga akhirnya ia menang.

Bukankah itu menyenangkan?

Saya pribadi tertarik pada bagaimana ini dapat diterapkan untuk verifikasi kebenaran perangkat lunak. Sekarang kita menguji perangkat lunak dengan melemparkan banyak input uji padanya dan (terlalu sederhana) melihat apakah itu mengenai Assert. Dalam komputer kuantum dimungkinkan untuk menjalankannya secara paralel terhadap serangkaian input yang jauh lebih padat dan melihat apakah ada kasus yang mengenai Assert.

Seperti jika input ke algoritme adalah 128 byte, atau 1024 bit, ada 2 ^ 1024 atau 10 ^ 308 kemungkinan input yang berbeda. Tidak ada cara untuk menguji banyak input pada komputer konvensional, tetapi komputer kuantum dapat mencoba semuanya secara paralel.

Akan seperti apa bahasa C jika dirancang untuk qubit? Apakah tipe akan berubah?

Ini akan sangat berbeda secara drastis sehingga tidak bisa dipahami seperti C.

Masalah utama (seperti yang saya mengerti) adalah bahwa komputasi kuantum tidak bekerja dengan cara imperatif yang baik 'lakukan ini, lalu itu, maka hal lain ini'. Mencoba memaksakan kemampuan C untuk melakukan itu ke dalam 'prosesor' komputer kuantum jika tidak mustahil, sangat tidak efisien.

Algoritme pemrograman untuk komputer kuantum (sekali lagi, seperti yang saya pahami) cenderung lebih dekat dengan peta gaya pemrograman fungsional / perkecil, karena komputasi kuantum memungkinkan semua kandidat di bagian 'perkecil' ada secara bersamaan dan "terjatuh" dari komputer saat diamati.

Perhatikan bahwa ada beberapa algoritma yang ada untuk komputer kuantum, meskipun perangkat tidak ada untuk menjalankannya. Algoritma Simon misalnya.

Untuk membuat penggunaan komputer kuantum seefektif mungkin, seseorang harus mampu menangani input dan output yang merupakan status register kuantum, yang sebenarnya tidak ada analog klasik. Berbicara dari beberapa tahun pengalaman di bidang informasi kuantum, saya harus memperingatkan Anda bahwa tidak ada yang benar-benar memiliki intuisi yang bagus untuk ini di luar matematika abstrak C * aljabar, dan saya diberitahu bahwa bahkan intuisi ini ternyata tidak memadai. jika Anda mulai bertanya-tanya tentang teori relativitas.

Kelas masalah yang dipecahkan secara efisien pada komputer kuantum dikenal sebagai BQP, untuk Bounded Quantum Polynomial. Ini adalah versi kuantum BPP, dan Anda dapat menemukan informasi lebih lanjut dalam makalah ini: http://www.scottaaronson.com/papers/bqpph.pdf

Saya diberitahu tadi malam oleh seorang peneliti algoritma kuantum bahwa ada masalah yang sangat penting yaitu BQP-complete: menyelesaikan sistem linear persamaan N. Secara klasik, ini dapat dipecahkan dalam langkah O (N) dengan eliminasi Gaussian. Algoritma Harrow-Hassidim-Lloyd ( http://arxiv.org/abs/0811.3171 ) memecahkannya dalam polylog (N), asalkan Anda bersedia menerima jawaban yang memiliki solusi yang dikodekan sebagai keadaan kuantum. Jika Anda ingin menggunakan komputer kuantum secara penuh, maka dari itu tampaknya perlu bagi Anda untuk memiliki tipe yang sesuai dengan keadaan register kuantum.

Meskipun saya sedikit di luar keahlian khusus saya saat ini, saya akan menebak bahwa Anda akan dapat memprogram komputer kuantum selama Anda memiliki akses ke jenis yang berkaitan dengan keadaan ajaib. Namun, itu konsep yang sulit, yang membutuhkan studi tentang subjek tersebut.

Berhati-hatilah karena kita sangat lama tidak memiliki bahasa pemrograman kuantum, karena kita berada pada tahap penelitian komputasi kuantum yang sangat primitif. Meminta kuantum C saat ini akan seperti pergi ke Alan Turing dan memintanya untuk mendesain Python. Kami bahkan belum mendapatkan versi kuantum dari tabung vakum!