Rangkuman Materi Quantum computation bab 1.4

1.4 Quantum algorithms

 

komputasi klasik pada komputer kuantum, memberikan beberapa contoh masalah yang menawarkan keunggulan komputer kuantum dibandingkan komputer klasik, dan meringkas algoritma kuantum yang diketahui

 

1.4.1 Perhitungan klasik pada komputer kuantum

 

Setiap rangkaian klasik dapat diganti dengan rangkaian ekivalen yang hanya berisi reversibel elemen, dengan memanfaatkan gerbang reversibel yang dikenal sebagai gerbang Toffoli. Gerbang Toffoli memiliki tiga bit input dan tiga bit output

 

Dua di antaranya adalah bit kontrol yang tidak terpengaruh oleh aksi gerbang Toffoli. Bit ketiga adalah target bit yang dibalik jika kedua bit kontrol diatur ke 1, dan sebaliknya dibiarkan saja.

Gerbang Toffoli dapat digunakan untuk mensimulasikan gerbang NAND dan juga dapat digunakan untuk melakukan FANOUT. Dengan dua operasi ini menjadi mungkin untuk mensimulasikan semua elemen lain dalam rangkaian klasik, dan dengan demikian rangkaian klasik dapat disimulasikan dengan rangkaian reversibel ekivalen.

Gerbang Toffoli  memastikan bahwa komputer kuantum mampu melakukan komputasi yang komputer klasik dapat lakukan.

1.4.2 Quantum parallelism

Paralelisme kuantum adalah fitur mendasar dari banyak algoritma kuantum. Secara heuristik, dan dengan risiko penyederhanaan yang berlebihan, paralelisme kuantum memungkinkan komputer kuantumuntuk mengevaluasi fungsi f(x) untuk banyak nilai x yang berbeda secara bersamaan. Di bagian inikami menjelaskan bagaimana paralelisme kuantum bekerja, dan beberapa keterbatasannya.

1.4.3 Algoritma Deutsch 

 

Perbedaannya adalah bahwa dalam klasik komputer dua alternatif ini selamanya mengecualikan satu sama lain; dalam komputer kuantum adalah mungkin untuk dua alternatif untuk mengganggu satu sama lain untuk menghasilkan beberapa properti global dari fungsi f engan menggunakan sesuatu seperti gerbang Hadamard untuk menggabungkan kembali yang berbeda alternatif, seperti yang dilakukan dalam algoritma Deutsch

1.4.4 Algoritma Deutsch–Jozsa

 

Algoritma Deutsch adalah kasus sederhana dari algoritma kuantum yang lebih umum, yang akan kita disebut sebagai algoritma Deutsch–Jozsa. Aplikasi, yang dikenal sebagai masalah Deutsch

ada beberapa peringatan penting Dalam Aplikasi masalah Deutsch . Pertama, masalah Deutsch bukanlah masalah yang sangat penting; tidak memiliki aplikasi yang dikenal. Kedua, perbandingan antara algoritma klasik dan kuantum dalam beberapa hal merupakan perbandingan apel dan jeruk 

Terlepas dari peringatan ini, algoritme Deutsch–Jozsa berisi benih untuk algoritme kuantum yang lebih mengesankan, dan sangat mencerahkan untuk mencoba memahami prinsip-prinsip di baliknya operasi.

1.4.5 Ringkasan Algoritma kuantum

 

Algoritma Deutsch–Jozsa menunjukkan bahwa komputer kuantum mungkin mampu memecahkan beberapa masalah komputasi jauh lebih efisien daripada komputer klasik. Sayangnya, masalah yang dipecahkannya kurang menarik secara praktis.

Secara garis besar, ada tiga kelas algoritma kuantum yang memberikan keunggulan dibandingkan algoritma klasik yang dikenal. Pertama, ada kelas algoritma berdasarkan versi kuantum dari transformasi Fourier, alat yang juga banyak digunakan dalam algoritma klasik. Algoritma Deutsch–Jozsa adalah contoh dari jenis algoritma ini, seperti algoritma Shor untuk pemfaktoran dan logaritma diskrit. Kelas algoritma kedua adalah algoritma pencarian kuantum. Kelas algoritma ketiga adalah simulasi kuantum, di mana komputer kuantum digunakan untuk mensimulasikan sistem kuantum.