Komputer kuantum (juga dikenal sebagai superkomputer kuantum) adalah perangkat komputasi yang menggunakan langsung fenomena kuantum mekanik , seperti superposisi dan belitan , untuk melakukan operasi pada data.Quantum komputer berbeda dari komputer digital berdasarkan transistor. Sedangkan komputer digital membutuhkan data yang akan dikodekan menjadi digit biner (bit) , yang masing-masing selalu dalam salah satu dari dua kondisi yang pasti (0 atau 1) , komputasi kuantum menggunakan qubit (quantum bit) , yang dapat dalam superposisi kondisi.
Salah satu model teoritisnya adalah mesin Turing quantum , juga dikenal sebagai komputer kuantum universal. Quantum komputer berbagi kesamaan teoritis dengan komputer non - deterministik dan probabilistik ; salah satu contoh adalah kemampuan untuk berada di lebih dari satu kondisi secara bersamaan.
Bidang komputasi kuantum pertama kali diperkenalkan oleh Yuri Manin pada tahun 1980 dan Richard Feynman pada tahun 1982. Sebuah komputer kuantum dengan berputar sebagai bit kuantum juga diformulasikan untuk digunakan sebagai kuantum ruang-waktu pada tahun 1969.
Berikut merupakan beberapa contoh algoritma untuk Komputer Kuantum :
Algoritma Grover
Algoritma Grover adalah sebuah algoritma kuantum untuk mencari database disortir dengan entri N di O (N1 / 2) waktu dan menggunakan O ( log N ) ruang penyimpanan (lihat notasi O besar ). Lov Grover dirumuskan itu pada tahun 1996 .
Dalam model komputasi klasik, mencari database unsorted tidak dapat dilakukan dalam waktu kurang dari waktu linier (jadi hanya mencari melalui setiap item optimal ). Algoritma Grover menggambarkan bahwa dalam model kuantum pencarian dapat dilakukan lebih cepat dari ini ; sebenarnya waktu kompleksitas O ( N1 / 2 ) adalah asimtotik tercepat mungkin untuk mencari database unsorted dalam model kuantum linear. Ini menyediakan percepatan kuadrat , seperti algoritma kuantum lainnya, yang dapat memberikan percepatan eksponensial atas rekan-rekan mereka klasik. Namun, bahkan percepatan kuadrat cukup besar ketika N besar.
Seperti banyak algoritma kuantum , algoritma Grover adalah probabilistik dalam arti bahwa ia memberikan jawaban yang benar dengan probabilitas tinggi . Kemungkinan kegagalan dapat dikurangi dengan mengulangi algoritma . (Sebuah contoh dari algoritma kuantum deterministik adalah algoritma Deutsch - Jozsa , yang selalu menghasilkan jawaban yang benar.)
Algoritma Shor
Algoritma Shor, dinamai dari nama matematikawan Peter Shor, adalah sebuah algoritma kuantum (algoritma yang berjalan pada sebuah komputer kuantum) untuk integer faktorisasi ditemukan pada tahun 1994 informal memecahkan masalah berikut : Mengingat integer N , menemukan faktor-faktor prima .
Pada komputer kuantum, faktor integer N, algoritma Shor berjalan dalam waktu polinomial ( waktu yang dibutuhkan adalah polinomial dalam log N, yang merupakan ukuran input [ 1 ] ). Secara khusus dibutuhkan waktu O ( ( log N ) 3 ), menunjukkan bahwa masalah faktorisasi integer dapat diselesaikan secara efisien pada komputer kuantum dan dengan demikian dalam BQP kelas kompleksitas. Hal ini secara eksponensial lebih cepat daripada algoritma dikenal paling efisien klasik anjak piutang, umum saringan field nomor, yang bekerja dalam waktu sub - eksponensial - tentang O ( e ( log N ) 1/3 ( log log N ) 2/3 ). Efisiensi terletak pada efisiensi kuantum Transformasi Fourier, dan eksponensial modular oleh squarings.
Mengingat sebuah komputer kuantum dengan jumlah yang memadai qubit, algoritma Shor dapat digunakan untuk memecahkan banyak digunakan skema kriptografi kunci publik yang dikenal sebagai RSA. RSA didasarkan pada asumsi bahwa anjak jumlah besar komputasi tidak layak. Sejauh yang diketahui , asumsi ini berlaku untuk klasik ( non - kuantum ) komputer ; tidak ada algoritma klasik diketahui bahwa bisa faktor dalam waktu polinomial. Namun, algoritma Shor menunjukkan bahwa anjak efisien pada komputer kuantum, sehingga komputer kuantum tepat besar dapat mematahkan RSA. Itu juga merupakan motivator yang kuat untuk desain dan konstruksi dari komputer kuantum dan untuk studi algoritma komputer kuantum baru. Hal ini juga memfasilitasi penelitian tentang kriptografi baru yang aman dari komputer kuantum, secara kolektif disebut kriptografi pasca - kuantum.
Source :
http://en.wikipedia.org/wiki/Grover's_algorithm
http://en.wikipedia.org/wiki/Quantum_computer
http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Shor_s_algorithm.html
