Menyambut Era Informasi Kuantum

Jika jumlah bilangan itu dilipatduakan, maka jumlah langkah yang diperlukan menjadi 2N, demikian seterusnya. Pertumbuhan yang demikian disebut bersifat linier dan setara dengan fungsi pertumbuhan yang polinomial (orde satu).

Untuk kasus pencarian angka, ada cara yang lebih efisien dari pada pencarian linier jika kumpulan angka tersebut muncul secara berurutan, yaitu dengan pencarian biner.

Sekumpulan 4 buah angka  memerlukan, dua langkah; delapan buah angka perlu tiga langkah, dan jIka ada buah N bilangan, pencarian biner hanya perlu sebanyak  sekitar log2(N) langkah. Pencarian biner memiliki kompleksitas logaritmik, yang memiliki tingkatan lebih rendah dari pencarian linier. 

Untuk permasalahan tertentu, misalnya menemukan faktor (prima) dari suatu bilangan bulat, belum ada cara efisien untuk melakukan perhitungan. Cara termudah adalah dengan mencoba membagi bilangan tersebut dengan semua bilangan prima yang kurang dari akar bilangan tersebut.

Secara garis besar, jika bilangan ini terdiri dari K-digit angka, maka perlu langkah perhitungan sebanyak M yang terdiri dari K/2 digit angka.

Jadi, untuk mencari faktor dari empat digit angka (puluhan ribu), kita perlu mencoba hingga ratusan langkah (dua digit angka). Untuk menemukan faktor bilangan sekian milyar (berdigit 10), perlu puluhan ribu langkah... demikian seterusnya.

Pengolahan Informasi Secara Kuantum
Salah satu keterbatasan dari komputer saat ini, yang kita sebut sebagai komputer klasik, adalah dalam kemampuannya menangani hard problems. Keterbatasan ini justru dapat dimanfaatkan untuk melakukan pengiriman dan penyimpanan informasi. 

Penyandian dengan kunci publik RSA (Rivest-Shamir-Adleman) memanfaatkan ketidakmampuan komputer klasik untuk secara cepat menemukan faktor prima dari bilangan bulat yang bernilai sangat besar (atau memiliki dijit yang panjang); perlu waktu ribuan bahkan milyaran tahun untuk menemukannya hingga secara komputasi tidak efisien.

Perkembangan jenis komputer baru dimulai pada tahun 1980-an, ketika Paul Benioff mengajukan model mekanika kuantum untuk mesin Turing, yang kemudian diikuti oleh beberapa peneliti, antara lain Richard Feynman, Yuri Manin, dan David Deutsch. Satuan informasi terkecil dalam pengolahan data adalah bit yang bernilai atau 0 atau 1 pada saat tertentu. 

Berbeda dengan komputer klasik, qubit dalam komputer kuantum memiliki kemampuan menyatakan kondisi  0 dan 1 sekaligus dalam bentuk superposisi.

Merealisasikan konsep qubit ke dalam satu perangkat (divais) memiliki tantangan yang sangat besar karena saat digunakan tidak boleh ada gangguan sekecil apapun dari lingkungan supaya tidak terjadi dekoherensi.