QUANTUM COMPUTING

QUANTUM COMPUTING

Bagaimana logika ganjil dunia subatomik memungkinkan suatu mesin komputasi mengerjakan kalkulasi jutaan kali lebih cepat dibanding mesin sejenis yang kita punyai saat ini

Ketika Perang Dunia II memasuki masa-masa yang paling suram, ketika Perancis telah lepas dari tangan Sekutu dan kapal selam Jerman hilir mudik di Samudera Atlantik, otak-otak paling brilian dari seluruh penjuru Inggris berkumpul di suatu tempat yang dikenal dengan nama Bletchley Park. Dalam sebuah bangunan kayu beratap rendah yang berdiri di atas tanah negara, lima puluh mil di sebelah barat daya kota London, ribuan pria dan wanita bekerja mati- matian untuk memecahkan kode yang dikirimkan oleh negara-negara yang tergabung dalam blok Axis ke kapal perang dan tentara-tentaranya. Ketika sebuah pesan radio masuk dan tercetak oleh teleprinter, jurutulis cepat-cepat memungutnya dan menyalinnya dengan tulisan tangan, sehingga pesan itu tampil dalam format khusus. Para kriptoanalis kemudian mengambil alih tugas berikutnya. Sebagian besar tugas mereka kerjakan secara manual, mulai dari membandingkan lembaran- lembaran kertas printer, melakukan permutasi, menyilang bagian yang salah, memelototi, membolak-balik, hingga menebak-nebak. Setelah berminggu-minggu kerja keras, kabut perang sedikit demi mulai terkuak. Tim Bletchley Park berhasil memecahkan kunci untuk penyandi (chiper) Red dan penyandi Light Blue milik Angkatan Udara pihak Axis. Setelah itu, mereka berhasil mempercundangi penyandi Enigma milik Angkatan Laut dan Angkatan Darat. Dan yang paling luar biasa, mereka sanggup mengurai pesan dari penyandi super rahasia Fish milik komando tertinggi Jerman.

Cukup mengejutkan bahwa nasib Eropa sekali waktu pernah bergantung di ujung pensil dan intuisi. Sekarang, manakala kalkulasi telah menjadi kian rumit dan standard menjadi kian tinggi, hampir setiap orang-orang dengan kecerdasan lumrah dapat memetik keuntungan dari komputer. Kalkulasi-kalkulasi yang tergolong paling berat memang masih dikerjakan dengan kode manual, namun kalkulasi demikian biasanya digunakan untuk menguji keamanan, bukan untuk menyerangnya. Sandi-sandi yang saat ini kita gunakan membuat Fish tampak seperti penyandi subtitusi huruf sederhana yang digemari oleh penggemar teka-teki dan kerap muncul dalam majalah anak-anak (a menjadi b, b menjadi c dan sebagainya). Karenanya, kita membutuhkan metode penyandian yang lebih cepat dan lebih ampuh. Salah satu penyandian yang dikenal sekarang adalah apa yang disebut protokol RSA. Protokol ini memungkinkan dilakukannya electronic banking; dengan protokol ini, transaksi antara bank dan nasabahnya dapat disandikan. Untuk membongkar sandi itu dan mentransfer uang fiktif, seseorang membutuhkan waktu hingga jutaan tahun, meski ia melakukannya dengan komputer tercepat di dunia. Sandi lain yang lumayan terkenal adalah Data Encryption Standard (DES), yang "tidak terlalu sulit" untuk dipecahkan namun masih tetap aman untuk transaksi bisnis biasa.

Selain penyandian, jenis kalkukasi lainnya - searching di Internet, pemodelan ekonomi suatu negara, peramalan cuaca - juga menyita sebagian besar kemampuan komputer, bahkan pada komputer- komputer yang paling cepat dan paling tangguh sekalipun. Kesulitan yang kita hadapi terutama bukan terletak pada kecepatan mikroposessor yang terlampau rendah, namun karena komputer itu sendiri yang secara inheren tidak efisien. Komputer modern beroperasi menurut program yang membagi suatu tugas menjadi operasi-operasi elementer yang kemudian dikerjakan secara serial. Satu operasi per satuan waktu. Para perancang komputer telah mencoba selama bertahun- tahun untuk memaksa dua atau lebih komputer (atau setidaknya dua atau lebih mikroprosessor) agar mengerjakan bagian-bagian berbeda dari suatu problema, secara bersamaan. Sayangnya kemajuan dalam bidang komputasi paralel semacam itu sangat lambat dan mengecewakan. Sebab utamanya adalah karena logika yang tertanam dalam mikroposessor pada dasarnya merupakan logika serial.

Komputer biasa kadang-kadang tampak mengerjakan banyak sekali tugas pada saat yang bersamaan, misalnya menjalankan word processor dan spreadsheet secara berbarengan. Namun pada kenyataannya prosessor hanya beralih secara cepat dari satu tugas ke tugas selanjutnya. Sebaliknya, komputer paralel yang sesungguhnya akan memiliki simultanitas sebagai sifat alamiahnya. Ia akan sanggup melakukan banyak operasi pada saat yang bersamaan; mencari secara cepat dari sekian banyak kemungkinan dan akhirnya menunjuk salah satu yang merupakan pemecahannya.

Komputer dengan kapabilitas semacam itu sebenarnya sudah ditemukan. Para ilmuwan menyebutnya komputer kuantum - bukan semata-mata karena komputer ini 'sejak lahir' berdimensi sangat kecil, namun lebih karena komputer ini bekerja menurut kaidah-kaidah ganjil dalam mekanika kuantum. Sekelompok fisikawan menemukan kaidah yang kemudian terbukti berlaku sepenuhnya di dunia gelombang dan partikel fisika subatomik tersebut pada awal abad 20. Kaidah mekanika kuantum yang secara khusus memicu berbagai studi mengenai terapan mekanika kuantum dalam komputasi adalah konsep bahwa partikel elementer seperti proton, neutron dan elektron dapat berada dalam dua atau lebih stata (state; keadaan) pada saat yang bersamaan. Hal ini memungkinkan Anda -setidaknya secara teoritis- untuk memperlakukan partikel- partikel tersebut sebagai prosessing unit dalam suatu mesin yang lebih efisien ketimbang komputer 'klasik' konvensional.

Komputer kuantum dengan spesifikasi yang amat sederhana telah direkayasa di laboratorium. Sementara itu, di bidang kajian yang saya tekuni, yaitu teori komputasi kuantum, para peneliti tengah sibuk membayangkan seperti apa kira-kira wujud mesin yang lebih canggih itu, jika mesin tersebut dapat dikonstruksi. Bahkan, kami sedang bersiap menulis software untuk peranti yang belum benar-benar terwujud itu. Meski masih dalam bentuk kertas kerja, prospek software tersebut sungguh menggiurkan: suatu algoritma yang dapat memfaktorkan bilangan sepanjang 140 digit dengan kecepatan semilyar (10 ^9) kali lebih cepat dibanding yang ditawarkan oleh metode nonkuantum terbaik yang kita kenal sekarang; sebuah search engine yang sanggup memeriksa setiap 'sudut dan celah' di Internet dalam waktu kurang dari setengah jam; sebuah pemecah kode 'brute-force' yang dapat memecahkan transmisi DES dalam tempo 5 menit.

Hal paling mengejutkan mengenai komputer kuantum barangkali adalah bahwa ide mengenai peranti ini datang agak terlambat. Sejak tahun 1920-an, para fisikawan telah mengetahui bahwa dunia partikel subatomik memiliki perilaku yang sangat berbeda. Akan tetapi, butuh waktu setengah abad bagi para ilmuwan komputer untuk mulai tertarik pada aplikasi efek-efek kuantum dalam komputasi. Jawabannya pun masih jauh dari jelas.

Pada dasarnya, semua komputer harus memenuhi dua persyaratan: ia harus dapat menyimpan informasi sebagai untai 0 dan 1 (kita sebut binary digit atau bit), serta memiliki metode untuk memanipulasi nilai bit- bit tersebut sesuai dengan intruksi yang diterimanya. Komputer mengubah bit-bitnya melalui gerbang logika atau gate, suatu peranti yang didesain untuk mengerjakan operasi logika sederhana. Sebagai contoh, gerbang NOT akan mengubah sembarang bit input menjadi kebalikannya (0 menjadi 1 dan 1 menjadi 0). Gerbang OR akan mengubah dua bit input menjadi bit tunggal yang nilainya merupakan bit input yang lebih tinggi (0 OR 0 menghasilkan 0 ; kombinasi lainnya menghasilkan bit 1 ). Gerbang AND menghasilkan 1 jika kedua bit inputnya adalah 1 ; jika tidak begitu, outputnya adalah 0. Apapun yang dikerjakan komputer, entah itu menirukan suara, menghitung digit kesejuta dari pi atau mengalahkan Gary Kasparov dalam permainan catur, pada dasarnya merupakan hasil tranformasi bit-bit oleh gerbang logika.

Dapatkah partikel subatomik menyimpan bit? Dapatkah mereka membentuk gerbang logika? Kita ambil contoh sebuah elektron. Setiap elektron bertingkah layaknya sebuah magnet kecil yang berputar pada sumbunya, dimana momen magnet dapat menunjuk hanya satu dari dua arah, naik (up) atau turun (down). Dengan demikian, spin elektron terkuantisasi: ia hanya memiliki dua stata yang mungkin, yang dengan segera dapat diidentikkan dengan 0 dan 1 pada prosessor komputer biasa. Anda pun dapat membalik bit, yaitu mengubah down menjadi up atau 0 menjadi 1 dengan menambahkan sepaket energi.

Bagaimana seandainya Anda memberikan lebih sedikit energi? Setengah paket misalnya. Sekali lagi, ketika Anda mengamati stata spin elektron, Anda akan mendapati bahwa spin tersebut terkuantisasi: dia akan memiliki arah up atau down. Namun disini terdapat perbedaan penting yang tak kentara. Menurut aturan mekanika kuantum, kebolehjadian untuk mengamati bahwa spin pada stata up maupun down akan berubah. Perubahan yang berasal dari suatu kondisi yang benar-benar baru dan tidak ada padanannya dalam hukum-hukum fisika non kuantum itu disebut superposisi dua stata spin: suatu kombinasi, suatu kondisi antara yang mungkin dapat berupa 60 persen up dan 40 persen down atau 22 persen up dan 78 persen down.

Pada dasawarsa 70 -an dan awal 80-an, fisikawan dan ilmuwan komputer mulai mencari cara untuk mengaplikasikan sifat-sifat superposisi kuantum dalam ranah komputasi. Ilmuwan yang menggeluti bidang ini -diantaranya Charles H. Bennett (IBM Thomas J. Watson Research Center di Yorktown Heights, New York), Paul A. Benioff (Argonne National Laboratory di Illinois), David Deutsch (University of Oxford) dan almarhum Richard P. Feynman- menunjukkan bahwa partikel yang berada dalam kondisi superposisi dapat difungsikan sebagai bit kuantum atau qubit, dan dikenai operasi yang analog dengan operasi NOT, OR dan AND pada komputasi klasik. Namun itu belum semuanya. Komputer kuantum, jika berhasil dibangun, akan sanggup mencapai hasil yang sebelumnya tampak seperti mimpi - dan benar- benar lain dari yang bisa disediakan oleh sistem klasik manapun.

Bayangkan sebuah komputer kuantum yang terbuat dari dua inti atom yang dari luar dapat dikendalikan dengan medan magnet. Misalkan inti tersebut dipunyai oleh atom karbon dan atom hidrogen yang bertetangga dalam sebuah molekul kloroform (CHCl3). Seperti halnya elektron, inti akan menyesuaikan spinnya dengan medan magnet pada arah up (1 ) atau down (0). Komputasi dapat dimulai dengan sistem yang menyerupai 'mainan' ini, yaitu dengan cara 'menggelitik' inti atom menggunakan gelombang radio. Jika Anda menala frekuensi dan durasi pulsa radio secara tepat, Anda akan dapat membuat salah satu inti tersebut membalik spinnya. Bahkan Anda bisa mengatur agar inti hidrogen hanya akan membalik jika inti karbon telah mengarah naik.

Dalam kasus tersebut, perilaku terkuantisasi dari kedua inti berfungsi sebagai suatu gerbang logika yang oleh para ilmuwan komputer disebut gerbang c-NOT (controlled-NOT), dimana inti karbon berperan sebagai pengontrol. Ditulis dalam bentuk lambang (atom karbon di depan dan hidrogen di belakang), maka akan terdapat empat input yang mungkin, (1 ,1 ), (1 ,0 ), (0 ,1 ) dan (0 ,0). Gerbang c-NOT dapat beroperasi pada salah satu dari keempat cara ini:
(1 ,1 ) => (1 ,0)
(1 ,0 ) => (1 ,1)
(0 ,1 ) => (0 ,1)
(0 ,0 ) => (0 ,0)
Para fisikawan telah membuktikan bahwa dengan merangkai operasi qubit tunggal dan gerbang c-NOT dua qubit, secara teoritis kita dapat membangun komputer kuantum yang sanggup mengerjakan semua hal yang dikerjakan oleh komputer klasik.

Keajaiban yang sesungguhnya terjadi ketika suatu gerbang logika dua- qubit bekerja pada partikel yang stata spinnya tersuperposisi. Mula- mula, letakkan molekul kloroform pada suatu medan magnet eksternal yang akan mengarahkan kedua inti atom ke posisi down atau posisi 0. Kemudian, dengan pulsa gelombang radio tertala, "jewerlah" inti karbon tersebut sehingga ia membalik sebagian, menuju ke stata superposisi dimana kebolehjadian untuk masing-masing arah spin adalah 50 persen (operasi bit- tunggal). Akhirnya, lakukan operasi c- NOT dengan inti karbon sebagai qubit pengontrol. Karena qubit kedua (inti hidrogen) bermula dari stata nol, hanya dua operasi tersebut yang relevan: (1 ,0 ) => (1 ,1 ) dan (0 ,0 ) => (0 ,0 ). Dengan lain kata, jika inti karbon pada awalnya membalik menjadi 1 , operasi c-NOT akan membalik inti hidrogen menjadi 1 pula. Jika inti karbon tetap dalam stata 0, operasi c-NOT akan membiarkan atom hidrogen tetap dalam stata 0 pula. Akan tetapi, aksi c- NOT pada stata superposisi inti karbon dan stata 0 inti hidrogen membuat sistem dua-qubit tersebut menjadi sebuah kesatuan dengan stata superposisi yang lebih rumit, dimana 50 persen kemungkinan berada pada stata (1 ,1 ) dan 50 persen kemungkinan berada dalam stata (0 ,0 ). Superposisi semacam itu disebut stata EPR (EPR states) untuk mengenang Albert Einstein, Boris Podolsky dan Nathan Rosen yang mula-mula mempelajarinya pada tahun 1935.

Teka-teki paling membingungkan dari stata EPR muncul ketika dua qubit tersebut terpisah secara fisis dan beroperasi sendiri-sendiri. Misalkan saja Anda hanya mengukur nilai dari qubit pertama, yaitu stata spin inti karbon. Saat Anda melakukan hal itu, Anda akan berhadapan dengan salah satu aturan pokok dalam mekanika kuantum: Jika suatu interaksi memberi informasi mengenai suatu stata kuantum, seluruh sistem dengan segera akan mengatur dirinya kembali agar konsisten dengan informasi tersebut. Secara umum, usaha apapun untuk mengukur atau mengamati suatu sistem yang berada dalam keadaan superposisi dua atau lebih stata dengan segera akan memaksa sistem untuk membuat keputusan. Alih-alih mempertahankan stata tersuperposisinya, komputer kuantum akan berpindah ke satu stata kuantum lain yang mungkin dan terbuka. Dalam bahasa mekanika kuantum, peristiwa ini disebut dekoherensi (decoherence).

Dengan mengamati qubit karbon dalam stata EPR, Anda telah memicu terjadinya dekoherensi dan menghancurkan superposisi; Anda memiliki kesempatan yang sama untuk mengamati stata 0 maupun 1, namun Anda hanya dapat mengamati salah satunya. Pengamatan tersebut juga menyebabkan sistem sebagai suatu kesatuan tidak dapat terus berada dalam keadaan superposisi dua stata (0 ,0 ) dan (1 ,1). Alih-alih demikian, sistem akan mengambil satu stata tertentu sehingga qubit hidrogen memiliki nilai yang sama dengan karbon. Menurut mekanika kuantum, kedua stata tersebut hadir pada saat yang sama karena kedua inti tersebut telah saling terbelit (entangled).

Jika hanya kemampuan-kemampuan di atas yang dimiliki, maka komputasi kuantum tidaklah terlalu menarik. Setelah bersusah payah, Anda hanya akan memperoleh hasil akhir berupa dua qubit identik yang nilainya acak. Namun, aspek menarik berkenaan dengan keterbelitan (entanglement) adalah bahwa Anda tidak harus melakukan observasi atau pengukuran seketika itu juga. Anda dapat meninggalkan sistem tetap dalam keadaan tersuperposisi dan mengerjakan operasi lain yang lebih sulit dan perlu trik sebanyak yang Anda mau, sebelum akhirnya memutuskan untuk mengamati sistem. Sementara Anda melakukan hal itu, operasi kuantum dalam sistem bekerja secara simultan pada seluruh stata. Jika banyaknya qubit adalah q, maka jumlah total stata yang mungkin adalah 2q.

Dengan berbekal 500 buah partikel, secara prinsip kita dapat membuat sistem kuantum yang memiliki superposisi dari 2500 stata. Masing- masing stata akan menjadi daftar tunggal dari 500 buah susunan angka 0 dan 1. Semua operasi kuantum pada sistem tersebut (misalnya pulsa gelombang radio tertentu yang mengeksekusi operasi c-NOT pada qubit ke 175 dan 176 ) akan bekerja secara simultan pada 2500 stata tersebut. Karenanya, dengan satu siklus mesin, satu ketukan dalam jam komputer, operasi kuantum sanggup mengkomputasi tak hanya satu stata mesin seperti halnya komputer klasik yang bekerja serial, tetapi 2500 stata mesin sekaligus! Jumlah itu kira-kira sama dengan angka 1 diikuti 150 buah angka 0 di belakangnya; jauh lebih besar dibanding jumlah atom di alam semesta yang kita ketahui. Yang menjadi masalah, pengamatan terhadap sistem akan membuatnya runtuh (collapse) ke stata kuantum tunggal yang bersesuaian dengan jawaban tunggal pula: suatu daftar tunggal berisi sederet angka 0 dan 1 yang banyaknya 500 buah. Bedanya adalah jawaban tersebut dihasilkan melalui paralelisme masif dalam komputasi kuantum.

Komputer kuantum bekerja jauh lebih cepat pada kasus-kasus tertentu karena ia mampu meng-handle problema-problema yang tak tertangani oleh komputer klasik. Jika komputer kuantum yang berfungsi sepenuhnya berhasil dibangun, pemberdayaan potensinya hanya akan bergantung pada kesanggupan para ilmuwan untuk menyusun algoritma yang sanggup beroperasi secara tepat, untuk tujuan yang tepat.

Realisasi komputer kuantum telah menimbulkan kehebohan pada riset- riset mengenai teori komputasi kuantum. Bidang ini mempunyai tantangannya sendiri. Matematika yang digunakan untuk menganalisis evolusi sistem partikel tidaklah mudah dipahami. Sama halnya Anda dapat terbang dari New York ke Los Angeles secara langsung maupun melalui beberapa bandara transit, partikel subatomik dapat berubah dari satu stata ke stata lain melalui beberapa lintasan yang mungkin. Perbedaannya adalah pesawat Anda hanya dapat mengambil salah satu rute yang mungkin, sedangkan partikel yang berperilaku seperti gelombang dapat mengambil semua kemungkinan secara simultan. Selain itu, kebolehjadian untuk menemukan partikel di tiap-tiap lintasan berfluktuasi dari titik ke titik dan dari waktu ke waktu, seperti halnya gelombang memiliki bukit dan lembah. Untuk menghitung kebolehjadian bahwa suatu stata akan mewujud atau menjadi realitas, kita harus menjumlahkan kebolehjadian dari seluruh lintasan yang menuju ke stata tersebut, dan dengan hati-hati menjaga gelombang kebolehjadian di masing-masing lintasan agar tetap berada pada fase yang tepat.

Kendala lain yang menghadang adalah fakta bahwa kuantum komputer ternyata sangat rapuh (fragile). Agar tetap berada di stata superposisi, sistem kuantum harus benar-benar terisolasi dari lingkungan sekitar. Interaksi sekecil apapun dengan dunia luar akan mengganggu sistem, merusak superposisi dan menggagalkan komputasi. Akibatnya, siapa saja yang ingin membangun komputer kuantum harus ekstra hati-hati melindunginya dari panas, sinar kosmis dan pengaruh luar lainnya, termasuk dari pengamat luar. Sebagai tambahan, sekali komputer kuantum memecahkan suatu problema yang Anda inputkan, keinginan Anda untuk membaca jawaban atas problema tersebut akan memaksa Anda untuk meruntuhkan sistem.

Perilaku khas sistem kuantum ini telah lama diketahui dan menjadi sebab mengapa kajian mengenai komputasi kuantum yang sedemikian mengesankan sejauh ini hanya berlangsung di atas kertas. Sementara fisikawan eksperimentalis bergumul untuk membangun sistem yang paling sederhana di laboratorium, fisikawan teoritis telah melangkah maju untuk membuat peranti lunak yang dibutuhkan oleh komputer kuantum.

Salah satu potongan penting dari peranti lunak dalam teknologi komputasi adalah metode koreksi kesalahan (error correction code). Mesin komputasi melakukan kesalahan-kesalahan selama operasinya. Komputer klasik didesain untuk 'mendeteksi' kesalahan melalui apa yang disebut redundansi. Mereka mengerjakan tiap unit komputasi elementer beberapa kali dan menganggap jawaban yang paling sering diperoleh sebagai jawaban yang benar. Pendekatan 'aturan mayoritas' itu tidak akan bekerja pada komputer kuantum, karena untuk membandingkan jawaban kita harus melakukan sesuatu yang tabu dalam dunia kuantum, yaitu mengamati sistem sebelum komputasi berlangsung.

Secara mengejutkan, beberapa ilmuwan berhasil membuktikan bahwa quantum error correction bukanlah hal yang mustahil untuk dilakukan. Pada tahun 1995, matematikawan Peter W. Shor (sekarang di AT&T Labs, Florham Park, New Jersey) dan fisikawan Universitas Oxford, Andrew M. Steane secara terpisah menemukan cara untuk 'mengakali' jebakan kuantum tersebut. Skema yang mereka usulkan dapat mendeteksi kesalahan (error) dengan cara sedemikian rupa sehingga tidak memberi informasi apapun mengenai komputasi yang tengah berlangsung (dan dengan demikian tidak meruntuhkan superposisi). Kesalahan yang terdapati kemudian dikoreksi dengan komputasi kuantum lainnya, yang juga mempertahankan sistem kuantum tetap utuh.

Pendekatan yang mirip juga digunakan dalam faktorisasi bilangan yang besar. Faktorisasi adalah sesuatu yang oleh ilmuwan komputer disebut one-way problem: sukar pada satu arah, namun mudah pada arah lainnya. Andaikan saya bertanya kepada Anda, "Bilangan bulat apa yang jika dikalikan akan menghasilkan bilangan 40301 ?" Pengujian sistematis dari semua kandidat yang mungkin barangkali akan membuat Anda sibuk selama 15 menit atau lebih. Tetapi jika saya meminta Anda untuk mengalikan 191 dan 211 dengan pensil dan kertas, Anda mungkin hanya akan membutuhkan waktu 20 detik untuk menemukan bahwa jawabannya adalah 40301 . Kesulitan yang tidak imbang antara faktorisasi dan perkalian merupakan basis dari skema enkripsi data yang banyak digunakan saat ini. Salah satu contohnya adalah protokol RSA. Bilangan prima besar - 100 digit atau lebih - merupakan 'password' yang baik untuk sistem- sistem semacam itu karena mudah diverifikasi (Tinggal kalikan mereka dan lihat apakah hasilnya sesuai dengan bilangan yang tersimpan atau bilangan yang sudah menjadi kunci publik). Mengekstrak password sepanjang 200 digit yang berasal dari hasil kali dua bilangan prima besar tak beda dengan memfaktorkan bilangan besar - suatu problema yang tentu saja sangat berat. Komputer biasa dengan algoritma non kuantum yang tersedia saat ini tidak akan sanggup memfaktorkan bilangan yang panjangnya lebih dari 140 digit.

Algoritma kuantum menawarkan sesuatu yang benar-benar berbeda. Pada tahun 1994, Peter Shor menemukan cara untuk membuat faktorisasi menjadi seefisien perkalian. Dalam ilmu komputer, kita sering mencoba untuk memecahkan persoalan berat dengan membaginya menjadi persoalan-persoalan yang lebih sederhana, yang salah satunya sudah terpecahkan. Shor pun memanfaatkan metode yang telah dikenal luas dalam teori bilangan, yaitu mengubah faktorisasi menjadi suatu pemerkiraan periodisitas dari suatu barisan bilangan yang panjang. Secara sederhana, periodisitas adalah jumlah anggota dalam suatu satuan pengulangan yang terdapat dalam sebuah barisan. Barisan 0 , 3 , 8 , 5 , 0 , 3 , 8 , 5,..., misalnya, memiliki perodisitas empat. Untuk memerkirakan periodisitas, algoritma klasik harus melakukan pengamatan setidaknya sebanyak jumlah anggota yang terdapat dalam periode tersebut. Algoritma Shor bekerja jauh lebih baik. Algoritma ini menyusun sistem kuantum yang terbentuk dari sejumlah besar stata tersuperposisi. Tiap stata diidentifikasi dengan anggota dari suatu barisan berulang. Operasi mekanika kuantum tunggal kemudian mengubah masing-masing stata tersuperposisi melalui suatu mekanisme yang bergantung pada nilai barisan dimana stata tersebut berkorespondensi dengan. Serangkaian operasi mekanika kuantum yang secara matematis analog dengan difraksi sinar-X berlangsung dalam stata tersuperposisi.

Metode difraksi sinar-X yang bekerja dengan prinsip yang sama memungkinkan ahli bahan tambang mendeduksi periodisitas kisi kristal dari suatu zat padat yang tidak diketahui. Struktur periodik kisi hanya mengijinkan gelombang dengan panjang gelombang tertentu untuk merambat [ke arah tertentu]. Demikian pula dalam algoritma Shor, sistem kuantum dari stata tersuperposisi hanya mengijinkan gelombang kebolehjadian yang terkait dengan stata kuantum tersebut untuk 'merambat'; sisanya akan teredam atau terhilangkan. Algoritma Shor kemudian menghitung panjang gelombang yang merambat itu, memperkirakan periodisitas dari stata tersuperposisi dan akhirnya mendeduksi faktor bilangan yang dicari. Jadilah sebuah algoritma yang diklaim sebagai algoritma faktorisasi tercepat yang pernah ada.

Faktorisasi sebenarnya adalah sejenis pencarian, yaitu pencarian faktor. Untuk jenis pencarian lainnya, kita memerlukan suatu algoritma yang lebih serba guna. Kontribusi terpenting saya dalam komputasi kuantum adalah algoritma mekanika kuantum yang sangat efisien untuk melakukan searching pada data base yang tidak urut. Algoritma yang saya temukan pada tahun 1996 itu lebih cepat ketimbang semua algoritma klasik yang kita miliki. Lebih dari itu, para peneliti lain telah menunjukkan bahwa tidak ada algoritma mekanika kuantum lainnya yang dapat mengungguli kecepatannya.

Andaikan Anda ingin mencari suatu nomor telpon pada buku direktori nomor telpon (Yellow Pages) yang berisi jutaan nomor. Anggaplah Anda lupa nama pemilik nomor telpon tersebut; informasi yang Anda miliki hanyalah alamat. Dalam kasus seperti ini, satu-satunya pilihan yang dapat Anda lakukan adalah trial and error. Menurut statistik, Anda rata-rata perlu membaca nama 500 ribu orang yang tidak Anda kenal sebelum Anda menemukan apa yang Anda cari. Di hari yang naas, Anda barangkali harus melihat 999 ,999 ribu nama asing. Komputer dapat mencarinya lebih cepat, namun secara algoritmik pencarian yang dilakukan komputer tidak berbeda dengan pencarian kita. Pada umumnya, pencarian pada suatu daftar dengan N item membutuhkan N/2 langkah.

Komputer kuantum dapat melakukan hal itu dengan lebih baik karena mampu mengerjakan banyak operasi pada saat yang bersamaan. Dengan anggapan bahwa Anda memiliki akses ke sistem kuantum, inilah yang dapat Anda lakukan untuk pencarian tersebut. Mula-mula, pilihlah partikel- partikel dalam jumlah yang cukup (sejumlah q) sedemikian sehingga terdapat cukup sistem kuantum dalam sistem (2 q) untuk memberikan setidaknya satu stata bagi masing- masing nama dalam buku telpon. (Untuk memeroleh sejuta nama misalnya, Anda memerlukan 20 partikel, karena 220 sedikit lebih banyak dibanding sejuta). Tempatkan informasi dari buku telpon dalam memori kuantum dan letakkan masing-masing nama ke stata kuantum yang berbeda. Kondisikan sistem hingga berada pada mengalami superposisi dari sejuta stata tersebut. Sistem akan melakukan komputasi untuk memeriksa apakah masing-masing nama tersebut adalah nama yang tepat atau bukan. Berkat superposisi kuantum, komputasi berlangsung secara simultan pada seluruh stata.

Hingga tahap ini, jawaban persoalan kita masih berada di dalam sistem. Perlu trik untuk 'mengeluarkannya'. Mengamati sistem tanpa pemrosesan lanjutan akan segera meruntuhkan superposisi ke salah satu stata dari sejuta stata dalam entanglement. Namun peluang bahwa keadaaan tersebut akan memberi Anda nama yang Anda cari hanyalah sepersejuta. Sama halnya Anda menunjuk salah satu nama secara acak dalam buku telpon.

Masalah selanjutnya adalah pemrosesan lanjutan: rentetan operasi mekanika kuantum pada stata tersuperposisi yang menguatkan kebolehjadian bahwa ketika superposisi diamati, ia hanya akan runtuh ke stata yang bersesuaian dengan nama yang dicari. Itulah yang dilakukan oleh algoritma pencarian yang saya buat. Seperti halnya metode faktorisasi Shor, algoritma tersebut mengambil keuntungan dari sifat alamiah gelombang kebolehjadian dalam komputer kuantum.

Untuk mendapatkan contoh yang lebih gamblang mengenai bagaimana proses ini berlangsung, anggaplah bahwa Anda ingin menemukan suatu nama dalam buku telepon yang hanya memiliki empat aran (entri). Untuk mengeset komputer kuantum Anda, Anda memutuskan untuk melakukan komputasi dengan sepasang partikel -agar bervariasi, kali ini pilihlah proton- dan Anda mengatur segala sesuatunya sedemikian sehingga masing-masing nama dalam buku telpon bersesuaian dengan kombinasi spin yang berbeda: (0 ,0 ), (0 ,1 ), (1 ,0 ) atau (1 ,1). Sekarang, anggaplah bahwa tanpa Anda ketahui, nama yang ingin Anda cari bersesuaian dengan stata ketiga, yaitu (1 ,0). Stata itu adalah targetnya.

Anda mulai dengan menetapkan posisi awal spin proton dengan menggunakan medan magnet, mengarahkan keduanya ke arah up. Kemudian Anda memberi kepada masing-masing partikel medan magnet yang lebih lemah, yang energinya hanya cukup untuk mengubah mengubah stata spin menjadi superposisi 50 persen up dan 50 persen down ('50 percent flip'). Sistem dua-partikel tersebut kini menjadi superposisi dari empat kombinasi spin yang mungkin, masing-masing dengan kebolehjadian 1 /4.

Dalam mekanika kuantum, masing- masing kebolehjadian secara matematis diperlakukan sebagai kuadrat dari amplitudo kebolehjadian, suatu entitas teoritis yang tidak secara langsung teramati. Singkat kata, apa yang dimanipulasi oleh algoritma yang saya buat tak lain adalah amplitudo kebolehjadian. Keuntungan bekerja dengan amplitudo kebolehjadian adalah tidak seperti kebolehjadian sebenarnya, amplitodo ini dapat bernilai positif maupun negatif, dan dapat saling menghilangkan satu sama lain, seperti halnya gelombang dalam air. Algoritma saya menggunakan sifat tersebut dengan membatalkan lintasan komputasional yang pada awalnya tampak menjanjikan namun kemudian berubah menjadi tidak berguna atau 'mati'.

Karena tiap stata dari keempat stata tersuperposisi tadi memiliki kebolehjadian 1 /4 , amplitudo kebolehjadian dari masing-masing stata dalam contoh dua-partikel saya dapat bernilai +1 /2 atau -1 /2 (nilai tersebut sebenarnya berupa bilangan kompleks). Algoritma saya menjamin bahwa seluruh amplitudo kebolehjadian diawali dengan nilai yang sama (1 /2 , 1 /2 , 1 /2 , 1 /2 ). Sekarang kita sampai di jantung algoritma ini. Operasi pertama mengubah tanda amplitudo dari stata target (dalam contoh saya adalah stata ketiga), sehingga amplitudonya menjadi (1 /2 , 1 /2 , -1 /2 , 1 /2). Hal ini mungkin karena ketika komputer kuantum berada di stata target, ia dapat memverifikasi apakah ia berada pada stata yang benar atau tidak, dan dapat membalik fase stata tersebut. Perhatikan bahwa operasi ini tidak memperlihatkan apapun kepada dunia luar, karena dalam hal ini kebolehjadian -yaitu kuadrat amplitudo probabilitas -tak berubah.

Tiga operasi kuantum selajutnya adalah 50 percent flip, kemudian operasi yang membalik fase salah satu stata, dan 50 percent flip sekali lagi. Akibat finalnya adalah suatu manuver yang disebut 'inversion about the average'. Jika Anda membayangkan nilai rata-rata sebagai batang seperti tanda + dimana tingginya sama dengan nilai rata-rata amplitudo (dengan beragam amplitudo individual menonjol ke atas atau menggelantung ke bawah darinya), Anda dapat membalik masing-masing amplitudo dengan cara memutarnya ke sisi seberang dari batang salib tersebut.

Apa hasil akhir yang Anda dapatkan? Rata-rata amplitudo pada keempat stata setelah pergantian tanda amplitudo pada stata target adalah (1 /2 + l /2 - 1 /2 + 1 /2 )/4 , atau 1 /4 . Stata pertama memiliki amplitudo l /2 , yang berati 1 /4 lebihnya diatas rata-rata, sehingga setelah inversion about the average amplitudonya menjadi 1 /4 kurangnya dari rata-rata atau 0 . Kalkulasi yang sama untuk masing- masing stata menunjukkan bahwa amplitudo mereka menjadi (0 , 0 , 1 , 0). Kuadrat dari masing-masing bilangan tersebut menunjukkan kebolehjadian masing-masing stata. Dengan lain kata, efek dari operasi yang Anda kerjakan adalah untuk mengarahkan komputer kuantum ke stata target; kebolehjadian dari stata target, (1 ,0), pasti tercapai. Jika sekarang Anda mengamati sembarang spin proton, superposisi kuantum akan runtuh untuk menunjukkan jawaban yang benar.

Sebagian besar pencarian tentu saja perlu memayar daftar yang lebih panjang dari sekedar daftar berisi 4 entri. Untuk melakukan searching semacam itu, algoritma harus berulang kali mengulang ketiga operasi kuantum di atas, serta mengarahkan sistem ke stata yang diinginkan di setiap putaran. Mengapa pencarian dengan algoritma kuantum sedemikian ampuh? Karena untuk menemukan nama dalam daftar yang berisi N item, algoritma tersebut hanya membutuhkan akar kuadrat N (N^1 /2 ) langkah. Algoritma pencarian klasik berbasil trial and error membutuhkan N/2 langkah untuk melakukan hal yang sama. Dengan demikian, komputer kuantum dapat mencari suatu nama pada buku telepon yang berisi 1000.000 nama dengan 1000 kali percobaan saja, alih- alih 500 ribu percobaan. Semakin panjang daftar tersebut, semakin dramatis pula algoritma kuantum mengungguli rivalnya (baca: algoritma klasik).

Algoritma ini tak hanya cocok untuk mencari nomer telepon, namun dapat pula dimanfaatkan untuk mencari item-item yang tidak tertulis secara eksplisit dalam daftar. Ia dapat mengaplikasikan pendekatan brute- force untuk sembarang persoalan yang potensi pemecahannya dapat dihitung secara sistemastis, dan mencoba semuanya hingga solusi yang benar ditemukan. Versi nonkuantum dari pendekatan brute- force ini sudah merupakan menu pokok dalam komputasi; algoritma jenis ini diaplikasikan pada program- program game, misalnya permainan catur. Karena kecepatan dan kemampuannya, algoritma pencarian sangat mungkin menjadi komponen kunci dalam peranti lunak masa depan.

Jika abad ke 21 diharapkan menjadi era komputer kuantum, beberapa kemajuan masih diperlukan. Kemampuan model-model yang dibangun saat ini ternyata masih sangat jauh dari potensi teoritisnya. Model-model itu bahkan belum sanggup memfaktorkan bilangan dua digit. Sejauh ini, pendekatan yang paling menjanjikan berasal dari teknologi yang justru lebih dikenal di dunia medis, yakni nuclear magnetic resonance (NMR). Komputer kuantum berteknologi NMR tak lain adalah molekul-molekul dalam zat cair; inti- inti atomik dalam molekul tersebut menyandikan informasi. Teknik ini tidak langsung mengekstrak hasil dari sejumlah qubit yang fragile sifatnya, tetapi memanipulasi (identik dengan 'memrogram') sejumlah besar inti dengan pulsa-pulsa frekuensi radio, kemudian mengaplikasikan statistik untuk menyaring jawaban yang benar (kira-kira satu hasil per sejuta) agar terbebas dari derau latar belakang.

Pada tahun 1997, Isaac L. Chuang dari IBM Almaden Research Center di San Jose, California, Neil A. Gershenfeld dari Massachusetts Institute of Technology, dan Mark G. Kubinec dari University of California, Berkeley, membangun NMR quantum computer sederhana yang memiliki dua qubit. Mereka menggunakan kloroform cair sebagai media. 'Program' yang dijalankan pada komputer itu adalah algoritma pencarian (searching algorithm) temuan saya, yang diaplikasikan pada suatu daftar dengan empat buah item. Belakangan, sebuah kelompok riset di Universitas Oxford juga membangun perangkat yang sama, namun menggunakan dua inti hidrogen yang terdapat pada zat kimia organik yang disebut cytosine.

NMR quantum computers dengan tiga qubit yang menjalankan routine program error corection dari Shor dan Steane telah didemonstrasikan pada tahun 1998 oleh Raymond Laflamme dan kolega-koleganya di Los Alamos National Laboratory, New Mexico. Apakah suatu saat nanti kita akan mengoperasikan peranti lunak untuk komputer kuantum? Berapa lama kita harus menunggu sebelum akhirnya komputer kuantum benar- benar menjelma menjadi mesin komputasi mahadaya seperti yang diprediksikan dalam berbagai kajian teoritis? Saya tidak ingin menantang Anda untuk bertaruh. Namun saya mengajak semua futurolog dan calon futurolog untuk mengingat kembali kalimat yang tercetus pada suatu diskusi mengenai Electronic Numerical Integrator and Calculator (ENIAC) yang muncul dalam majalah Popular Mechanics edisi Maret 1949 : Kalkulator yang terdapat dalam ENIAC terdiri dari 18.000 tabung hampa dengan berat keseluruhan mencapai 30 ton, tetapi komputer di masa depan mungkin hanya tersusun atas 1000 tabung hampa dengan berat tak lebih dari 1 ,5 ton.

Lov Grover sendiri merupakan eksponen utama teori komputasi kuantum. Pada tahun 1994, ia menemukan suatu algoritma yang kelak terbukti sebagai algoritma pencarian tercepat yang mungkin dikerjakan oleh komputer kuantum. Saat ini Lov Grover tercatat sebagai peneliti pada divisi riset ilmu fisika di Bell Labs, Murray Hill, New Jersey.