Pengenalan
Algoritma kuantum menawarkan kelebihan yang boleh dibuktikan berbanding algoritma klasik dalam model pertanyaan pengiraan. Tetapi bagaimana pula dengan model pengiraan yang lebih standard, di mana input masalah diberikan secara eksplisit dan bukannya dalam bentuk oracle atau kotak hitam? Ini ternyata merupakan soalan yang jauh lebih sukar untuk dijawab, dan untuk menanganinya kita mesti terlebih dahulu membina asas yang kukuh untuk menjadi landasan penyiasatan kita. Ini adalah tujuan utama pelajaran ini.
Kita akan mulakan dengan membincangkan kos pengiraan, untuk pengiraan klasik dan kuantum, dan cara mengukurnya. Ini adalah konsep umum yang boleh digunakan pada pelbagai masalah pengiraan — tetapi untuk memudahkan perkara kita akan meneliti terutamanya melalui kaca mata teori nombor pengiraan, yang menangani tugas pengiraan yang kemungkinan besar sudah biasa kepada kebanyakan pembaca, termasuk aritmetik asas, mengira pembahagi sepunya terbesar, dan pemfaktoran integer. Walaupun teori nombor pengiraan adalah domain aplikasi yang sempit, masalah-masalah ini sangat berguna untuk menggambarkan isu asas (dan ia juga kebetulan sangat relevan dengan pelajaran berikutnya).
Tumpuan kita adalah pada algoritma, berbanding perkakasan yang sentiasa bertambah baik di mana ia dijalankan. Sehubungan itu, kita lebih prihatin tentang bagaimana kos menjalankan algoritma berskala apabila kejadian masalah tertentu yang dijalankan padanya bertambah besar, dan bukannya berapa banyak saat, minit, atau jam yang diperlukan oleh sesuatu pengiraan. Kita menumpukan pada aspek kos pengiraan ini kerana mengiktiraf hakikat bahawa algoritma mempunyai kepentingan fundamental, dan secara semulajadi akan digunakan terhadap kejadian masalah yang semakin besar menggunakan perkakasan yang lebih pantas dan lebih boleh dipercayai seiring perkembangan teknologi.
Akhirnya, kita akan beralih kepada tugas yang sangat penting, iaitu menjalankan pengiraan klasik pada komputer kuantum. Sebab tugas ini penting bukan kerana kita berharap untuk menggantikan komputer klasik dengan komputer kuantum — yang nampaknya sangat tidak mungkin berlaku dalam masa terdekat, jika pun berlaku — tetapi kerana ia membuka banyak kemungkinan menarik untuk algoritma kuantum. Khususnya, pengiraan klasik yang berjalan pada komputer kuantum tersedia sebagai subrutin, secara berkesan memanfaatkan dekad penyelidikan dan pembangunan algoritma klasik dalam mengejar kelebihan pengiraan kuantum.
Video pelajaran
Dalam video berikut, John Watrous membimbing kamu melalui kandungan dalam pelajaran tentang asas algoritmik kuantum ini. Sebagai alternatif, kamu boleh membuka video YouTube untuk pelajaran ini dalam tetingkap berasingan. Muat turun slaid untuk pelajaran ini.