Pengantar

Algoritma kuantum menawarkan keunggulan yang bisa dibuktikan atas algoritma klasik dalam model query komputasi. Tapi bagaimana dengan model komputasi yang lebih standar, di mana input masalah diberikan secara eksplisit alih-alih dalam bentuk oracle atau kotak hitam? Ini ternyata adalah pertanyaan yang jauh lebih sulit untuk dijawab, dan untuk mengatasinya kita harus terlebih dahulu membangun fondasi yang solid untuk mendasarkan investigasi kita. Inilah tujuan utama dari pelajaran ini.

Kita akan mulai dengan mendiskusikan biaya komputasi, untuk komputasi klasik maupun kuantum, dan bagaimana itu bisa diukur. Ini adalah konsep umum yang bisa diterapkan pada berbagai masalah komputasi — tapi untuk menjaga hal-hal tetap sederhana kita terutama akan menelitinya melalui lensa teori bilangan komputasi, yang membahas tugas komputasi yang kemungkinan sudah familiar bagi kebanyakan pembaca, termasuk aritmatika dasar, menghitung pembagi persekutuan terbesar, dan faktorisasi bilangan bulat. Meskipun teori bilangan komputasi adalah domain aplikasi yang sempit, masalah-masalah ini sangat baik untuk mengilustrasikan isu-isu dasar (dan mereka juga kebetulan sangat relevan dengan pelajaran yang mengikuti ini).

Fokus kita adalah pada algoritma, sebagai lawan dari hardware yang terus meningkat tempat mereka dijalankan. Sesuai dengan itu, kita akan lebih peduli dengan bagaimana biaya menjalankan algoritma berskala seiring dengan instance masalah spesifik yang dijalankan semakin besar ukurannya, alih-alih berapa banyak detik, menit, atau jam yang dibutuhkan komputasi tertentu. Kita fokus pada aspek biaya komputasi ini dengan mengakui fakta bahwa algoritma memiliki kepentingan fundamental, dan secara alami akan diterapkan pada instance masalah yang semakin besar menggunakan hardware yang lebih cepat dan lebih andal seiring perkembangan teknologi.

Terakhir, kita akan beralih ke tugas yang sangat penting, yaitu menjalankan komputasi klasik pada komputer kuantum. Alasan tugas ini penting bukan karena kita berharap menggantikan komputer klasik dengan komputer kuantum — yang tampaknya sangat tidak mungkin terjadi dalam waktu dekat, jika pun pernah — melainkan karena ini membuka banyak kemungkinan menarik untuk algoritma kuantum. Secara khusus, komputasi klasik yang berjalan di komputer kuantum menjadi tersedia sebagai subrutin, secara efektif memanfaatkan dekade penelitian dan pengembangan pada algoritma klasik dalam mengejar keunggulan komputasi kuantum.

Video pelajaran

Di video berikut, John Watrous memandu kamu melalui konten di pelajaran ini tentang fondasi algoritmik kuantum. Atau, kamu bisa membuka video YouTube untuk pelajaran ini di jendela terpisah. Unduh slide untuk pelajaran ini.