Selasa, 02 Agustus 2011

Indonesia military strength

Indonesia is ranked 18 for the military rank, based on 45 factors.
globalfirepower.com

Indonesia military strength

Selasa, 26 Juli 2011

My First WolframAlfa widget: Vector Addition in 3D

I am trying to get my feet wet with Wolfram Alfa widget. Here is my first one: Vector Addition in three-dimensional space.



You may build your own widget here: Wolfram|Alfa widget .

Kamis, 14 Juli 2011

Algoritma Shor

Slide presentasi mengenai algoritma Shor:

Algoritma Kuantum untuk Faktorisasi Bilangan .

Informasi dan Komputasi Kuantum

Ini adalah catatan pribadi saya sebagai seorang pelajar, semoga berguna.

(repost dari Milis Fisika Indonesia, 4 Desember 2001. http://tech.groups.yahoo.com/group/fisika_indonesia/message/2856 )

…trying to find a computer simulation of physics seems
to me to be an excellent program to follow out…
and I'm not happy with all the analysis that go with just
the classical theory, because NATURE ISN'T CLASSICAL,
dammit, and if you want to make a simulation of nature,
you'd better MAKE IT QUANTUM MECHANICAL,
and by golly it's a wonderful problem because it doesn't
look so easy…
(R.P. Feynman(1981), Int. J. Theo. Phys. 81 p.486)


TEORI INFORMASI KUANTUM

0. RINGKASAN

Teori informasi kuantum adalah bidang kajian yang
menyatukan gagasan dari teori informasi klasik dan
teori kuantum. Informasi pada hakekatnya adalah
sesuatu yang bersifat fisis. Informasi dapat
dinyatakan sebagai simbol tertentu yang
direpresentasikan oleh obyek fisis tertentu, dan
komputasi didefinisikan sebagai pengolahan sistematis
dari informasi tertentu menjadi informasi lainnya,
yang dilakukan oleh piranti fisis yang disebut
komputer. Jika kita menginterpretasikan setiap keadaan
fisis sebagai suatu simbol tertentu, maka pada
dasarnya setiap proses fisis dapat dianggap sebagai
suatu komputasi. Teori informasi klasik, seperti yang
dirumuskan oleh Turing, Church, Post, dan Godel, yang
direalisasikan dalam bentuk komputer digital sekarang
ini, adalah teori matematika abstrak yang tidak
mengacu kepada hukum fisika. Hubungan mendasar antara
komputasi dengan hukum fisika pertama kali dibahas
oleh Benioff dan Feynman, yang kemudian dikembangkan
lebih lanjut oleh Deutsch.
Komputer kuantum merupakan perluasan dari mesin Turing
universal, yang menjadi dasar komputer digital saat
ini. Gagasan klasik mengenai teori informasi jelas
membutuhkan tinjauan ulang dalam sudut pandang teori
kuantum. Ada beberapa gejala kuantum tidak terdapat
dalam fisika klasik. Misalnya, dalam fenomena kuantum
terdapat proses acak (random) murni, seperti proses
radioaktif, yang tidak terdapat dalam dinamika klasik.
Selanjutnya, dalam teori kuantum, observabel nonkomut
tidak dapat secara bersamaan memiliki nilai pasti
(prinsip ketidakpastian), yaitu pengukuran observabel
A akan mempengaruhi pengukuran observabel B, jika A
dan B nonkomut. Jadi, tindakan memperoleh informasi
dari sebuah sistem selalu mengganggu sistem tersebut.
Hal ini tidak terdapat dalam fisika klasik. Prinsip
ketidakpastian ini berkaitan dengan keacakan kuantum:
Karena hasil pengukuran memiliki elemen acak maka kita
tidak dapat menentukan keadaan awal suatu sistem
berdasarkan hasil pengukuran.
Kenyataan bahwa proses pengukuran akan mengganggu
sistem juga berkaitan dengan kenyataan bahwa keadaan
kuantum tidak dapat disalin (no-cloning theorem).
Seandainya kita dapat menyalin sebuah keadaan kuantum,
maka kita dapat mengukur sebuah observabel dari
keadaan salinan tanpa menggangu keadaan asli, sehingga
akan melanggar prinsip ketidakpastian. Hal seperti ini
juga tidak terdapat dalam fisika klasik.
Selain prinsip ketidakpastian, teori informasi kuantum
berbeda dari teori informasi klasik dalam hal bahwa
informasi kuantum dapat dikodekan dalam keterkaitan
nonlokal antara bagian berbeda dari sebuah sistem
fisis (quantum entanglement), yang tidak terdapat
dalam fisika klasik.
Dengan berbagai fenomena kuantum yang tidak terdapat
dalam fisika klasik tersebut, tentunya timbul
pertanyaan apakah komputer kuantum (seandainya mungkin
dibangun) memiliki kemampuan komputasi melebihi
komputer klasik. Salah satu jawaban dari pertanyaan
ini adalah algoritma faktorisasi bilangan oleh Peter
Shor yang menunjukkan bahwa secara prinsip komputer
kuantum mampu memfaktorkan bilangan secara efisien,
dengan memanfaatkan superposisi dan keterkaitan
(entanglement) dari keadaan kuantum.
Algoritma faktorisasi kuantum Shor menyarankan bahwa
komputer kuantum memiliki kemampuan melebihi komputer
klasik, paling tidak dalam kelas masalah tertentu.
Faktorisasi bukanlah satu-satunya algoritma kuantum:
algoritma Grover untuk pencarian data dalam sebuah
database memberikan kecepatan kuadratik daripada
algoritma pencarian klasik, walaupun algoritma ini
tidak mengubah kategori kompleksitas. Masalah
faktorisasi adalah masalah yang menarik ditinjau dari
teori kompleksitas, sebagai contoh masalah yang tidak
dapat diselesaikan dalam waktu yang dibatasi oleh
polinomial dari jumlah input. Dari segi praktis hal
ini juga menarik karena kesulitan faktorisasi
digunakan sebagai dasar dari program pengamanan
(cryptography) seperti RSA.

1. INFORMASI ADALAH FISIS

Informasi pada hakekatnya adalah sesuatu yang bersifat
fisis. Informasi dapat dinyatakan sebagai simbol
tertentu yang direpresentasikan oleh obyek fisis
tertentu, dan komputasi didefinisikan sebagai
pengolahan sistematis dari informasi tertentu menjadi
informasi lainnya, yang dilakukan oleh piranti fisis
yang disebut komputer. Jika kita menginterpretasikan
setiap keadaan fisis sebagai suatu simbol, maka pada
dasarnya setiap proses fisis dapat dianggap sebagai
suatu komputasi. Tidak ada informasi tanpa
representasi fisis. Misalnya bunyi adalah fluktuasi
dari tekanan udara, tulisan di papan tulis adalah
pengaturan molekul-molekul kapur, bahkan pikiran
manusia juga bergantung pada neuron. Jadi batas dari
komputasi ditentukan oleh hukum fisika, bukan
ditentukan oleh logika abstrak.


2. PENGHAPUSAN INFORMASI

Rolf Landauer menyadari bahwa proses penghapusan
informasi adalah disipatif, karena melibatkan kompresi
ruang fasa dan karenanya irreversible.
Contoh, misalnya kita simpan satu bit informasi dengan
meletakkan "gas" yang hanya mengandung satu partikel
dalam kotak di sebelah kiri atau kanan dari partisi
yang membagi kotak jadi dua bagian sama besar.
Penghapusan memori adalah menggeser partikel ke
sebelah kiri (entah partikelnya sudah ada di kiri
atau masih di kanan) (bisa juga digeser ke kanan,
tergantung konvensi) dengan cara : melepas sekat, lalu
perlahan2 mendorong dengan piston sampai partikel ada
di kiri. Proses ini akan mengurangi entropi gas
sebesar dS=k ln 2 dan akan ada aliran panas dari kotak
ke lingkungan, dan entropi lingkungan bertambah. Jika
proses isotermal pada temperatur T, maka kerja W=kT ln
2 dilakukan pada kotak, kerja yang harus dibayar.


3. PARADOKS MAXWELL

Tinjau sebuah kotak berisi gas, yang diberi sekat
ditengah2nya, sehingga kotak terbagi dua. Dalam sekat
itu terdapat sebuah detektor (demon) yang mencatat
kecepatan partikel gas dan sebuah celah yang akan
dibuka oleh "sang demon" dalam kondisi:
partikel cepat ke kiri,
dan partikel lambat ke kanan.
Dengan cara ini bagian kiri semakin panas, dan bagian
kanan semakin dingin. Panas mengalir dari bagian
dingin ke bagian panas tanpa membutuhkan biaya
termodinamik (kerja). Hal ini jelas-jelas melanggar
hukum kedua termodinamika.
Solusinya: si demon harus menyimpan informasi mengenai
molekul. Jika memori sang demon terbatas, maka dia
harus menghapus memorinya. Pada saat inilah rekening
termodinamiknya harus dibayar. Szillard mengkaitkan
pencapaian satu bit informasi dengan entropi sebesar
dS= k ln 2. Pada saat si demon menghapus memorinya
itulah, entropi dilepaskan ke lingkungan.


4. KOMPUTASI REVERSIBLE

Tinjau gerbang logika NAND (not and) dengan input dua
bit dan output satu bit
yang tidak reversible:
00 -> 1
01 -> 1
10 -> 1
11 -> 0
Bennet membuktikan bahwa semua gerbang logika dapat
dibuat reversible. Contohnya untuk NAND di atas, ada
gerbang Toffoli yang membutuhkan tiga bit input dan
merubah bit ketiga hanya jika kedua bit pertama adalah
1:
000 000
001 001
010 010
011 011
100 100
101 101
110 111
111 110
Output bit ketiga menjadi NAND dari dua bit pertama
jika bit ketiga adalah 1.
Kenyataannya untuk perangkat keras yang ada sekarang
batas Landauer di atas masih toleran. Namun jika
perangat keras makin kecil, kita harus dapat
melindungi komponen dari panas. Juga untuk komputasi
kuantum, panas akan berinterasi dengan sistem kuantum
dan merusak koherensi kuantum. Jadi satu-satunya
jawaban adalah komputasi reversible.

5. IT FROM BIT

Segala informasi dapat direduksi menjadi satuan
informasi terkecil yang disebut bit. Sebuah bit
mempunyai dua nilai, yang biasanya direpresentasikan
sebagai 0 atau 1. Segala sesuatu selalu dapat
direpresentasikan sebagai kumpulan bit, atau dengan
kata lain: "it from bit".


6. BIT KUANTUM VS BIT KLASIK

Sebuah bit kuantum (=qubit=quantum bit) berbeda dengan
bit klasik dalam hal bahwa sebuah bit kuantum adalah
superposisi dari 0 dan 1, sementara sebuah bit klasik
hanya dapat mempunyai nilai 0 atau 1 pada suatu saat,
tapi tidak dapat mempunyai kedua nilai pada saat yang
sama.
Ini adalah hal yang luar biasa, karena dengan L qubit,
kita dapat menyimpan 2^L bilangan, dan dapat melakukan
transformasi sekaligus pada semua bilangan tersebut
(Kita dapat memperoleh evolusi dari keadaan kuantum
dari persamaan diferensial (persamaan Schrodinger)) .
Dan akibatnya kita dapat melakukan komputasi berbagai
keadaan secara paralel (massive parallel computation).
Namun perlu diingat, bahwa ketika kita mengukur
keadaan dari qubit, kita tidak memperoleh semua
keadaan yang terdapat dalam superposisi, karena
pengukuran dalam fisika kuantum bersifat acak: kita
hanya mengetahui peluang bahwa pengukuran akan
memberikan hasil tertentu, tetapi tidak dapat
menentukan secara pasti hasil dari pengukuran
tersebut. Jadi keluaran dari sebuah algoritma kuantum
bersifat probabilistik, kita tidak dapat meramalkan
dengan pasti keluaran dari sebuah algoritma kuantum.
Kenyataannya, algoritma Shor menggunakan massive
parallel computation seperti ini, dan menggunakan
sejenis trick untuk memanfaatkan keluaran algoritma yg
bersifat probabilistik. (Sekarang mungkin kita melihat
ada sesuatu yang aneh di sini: evolusi dari keadaan
kuantum digambarkan oleh persamaan diferensial yang
deterministik, tapi pengukuran bersifat probabilistik!
Tapi untuk sementara kita tidak usah terlalu khawatir
mengenai hal ini. Mari kita terusan saja pembahasan
mengenai dunia kuantum yang aneh ini.)


7. ENTANGLEMENT

Tidak semua orang terkesima oleh sifat probabilistik
dari keadaan kuantum. Beberapa orang berargumen bahwa
dalam fisika klasik juga terdapat sifat probabilistik,
misalnya lemparan koin, atau lemparan dadu (Karena
pembahasan kita lebih kepada qubit, mari kita fokuskan
pada kasus koin saja, yang mempunyai dua keluaran.)
Dalam komputer klasik kita juga mengenal algoritma
probabilistik, misalnya untuk menghitung random number
generator. Komputer klasik juga bisa mensimulasi
lemparan koin. Komputer klasik juga bisa mensimulasi
keadaan kuantum, tetapi untuk menggambarkan sebuah
keadaan dengan N qubit, sebuah komputer klasik
membutuhkan 2^N bit. (There's too much room in Hilber
space!)
Apakah kita bisa memanipulasi komputer klasik sehingga
bisa mensimulasikan komputer kuantum tanpa harus
menggambarkan secara lengkap semua evolusi dari N
qubit? Bukankah hasil akhir pengukuran dalam fisika
kuantum bersifat probabilistik, sehingga kita dapat
mensimulasikan secara lokal setiap kemungkinan,
seperti lemparan koin?
Ternyata tidak. Keadaan kuantum tidak seperti koin.
Menurut teorema Bell, mekanika kuantum tidak dapat
digambarkan oleh algoritma lokal probabilistik.
Keadaan kuantum umumnya berkorelasi secara nonlokal,
dalam arti pengukuran sebuah qubit terkait dengan
pengukuran qubit lainnya.
(Mungkin beberapa orang berargumen bahwa dalam fisika
klasik juga terdapat korelasi. Misalnya saya selalu
memakai kaos kaki dengan warna yang sama. Jadi warna
kaos kaki di salah satu kaki saya terkait dengan warna
kaos kaki di kaki yang lainnya. Begitu anda melihat
satu kaki saya dan melihat kaos kaki warna merah, maka
anda yakin bahwa kaos kaki di kaki yang satu lagi
warnanya juga merah. Ini tidak berarti bahwa
pengukuran anda (melihat warna kaos kaki) di salah
satu kaki mempengaruhi pengukuran di kaki lainnya,
tetapi anda sudah memperoleh cukup informasi mengenai
warna kaos kaki saya. Tetapi keadaan kuantum tidak
seperti kaos kaki: pengukuran sebuah keadaan kuantum
mempengaruhi pengukuran keadaan kuantum lainnya.)
Entanglement dapat digunakan sebagai sumber informasi.
Trick yang digunakan dalam komunikasi kuantum,
misalnya dense coding, teleportation, quantum key
distribution, menggunakan korelasi keadaan kuantum
sebagai sumber informasi. Bahkan dalam komputasi
kuantum, algoritma Shor juga memanfaatkan
entanglement.


8. NO CLONING THEOREM

Sebuah keadaan kuantum yang tidak diketahui tidak
dapat disalin. Kecuali kita sudah mengetahui sebuah
keadaan kuantum, kita tidak dapat menyalinnya. Jadi
tidak ada sebuah mesin copy kuantum yang bisa mengcopy
semua keadaan kuantum (kecuali untuk keadaan tertentu
yang sudah diketahui).
Kenyataan bahwa sebuah keadaan kuantum tidak dapat
disalin ternyata dapat digunakan dalam quantum
cryptography atau lebih tepatnya quantum key
distribution.


9. QUANTUM CRYPTOGRAPHY

Cryptography kuantum berbeda dengan cryptography
klasik. Cryptography klasik biasanya bergantung pada
teori bilangan, misalnya RSA yang bergantung pada
sulitnya memfaktorkan sebuah bilangan hasilkali
bilangan prima. Entanglement dan no cloning theorem
memungkinkan pengiriman kode yang aman, dan kode
tersebut nantinya akan digunakan untuk men-encode
komunikasi privat yang aman.


10. DENSE CODING

Penggunaan entanglement sebagai sumber informasi
memungkinkan kita mengirim dua bit klasik dengan
menggunakan satu qubit (two classical bits for the
price of one qubit!).


11. TELEPORTATION

Teleportasi kuantum adalah sebuah "trick" untuk
mentransfer qubit tanpa mengirim qubit secara fisis
(Istilah "tele" diusulkan karena qubitnya tidak
dikirim secara fisis.). Teleportasi adalah sebuah cara
menggunakan informasi klasik untuk mengirimkan
informasi kuantum.
Misalkan Alice mempunyai sebuah qubit yang tidak
diketahui, dan Bob membutuhkan qubit tersebut.
Biasanya Alice mengirim langsung qubit tersebut secara
fisis (entah itu foton, atom, elektron, atau apa pun).
Namun kali ini saluran komunikasi kuantum mengalami
gangguan (the quantum channel is down again!).
Teleportasi kuantum memungkinkan transfer qubit
menggunakan jaringan komunikasi klasik. Untuk
melakukan hal ini, Alice dan Bob harus memiliki
pasangan qubit yang terkait (entangled). Melalui
prosedur sistematik tertentu, akhirnya Bob akan
memperoleh qubit yang diinginkan. Namun, Bob hanya
akan memperoleh qubit yang diinginkan hanya jika qubit
tersebut lenyap dari Alice (ingat no cloning
theorem!).



12. ALGORITMA SHOR

Efisiensi dalam algoritma didefinisikan dalam ukuran
bagaimana jumlah langkah eksekusi dari suatu algoritma
bertambah jika jumlah masukannya bertambah. Sebuah
algoritma dikatakan efisien jika waktu eksekusi (atau
jumlah langkah eksekusi) adalah fungsi polinomial dari
jumlah masukan. Algoritma yang berada di luar kelas
polinomial dikategorikan sebagai tidak efisien.
Klasifikasi kompleksitas seperti ini dikatakan
universal, yaitu tidak bergantung kepada spesifikasi
perangkat keras yang digunakan.
Sebagai contoh kita tinjau algoritma perkalian dan
faktorisasi. Jika p dan q bilangan prima besar, maka
algoritma untuk menghitung hasilkali n=pq adalah
algoritma yang efisien. Namun diberikan n, algoritma
untuk menentukan menentukan p dan q adalah algoritma
yang tidak efisien. (Hal ini belum dibuktikan secara
formal, tetapi sampai saat ini belum ada yang mampu
menciptakan algoritma polinomial untuk faktorisasi.)
Algoritma klasik tercepat saat ini membutuhkan jumlah
operasi sebanding dengan eksponensial dari ukuran
masukan (sebanding dengan eksponensial dari ln (n)).
Ini berarti untuk mencari faktor dari sebuah bilangan
130 digit akan membutuhkan jumlah operasi sekitar
10^18, yang jika dikerjakan oleh superkomputer dengan
kecepatan 10^10 operasi/detik memerlukan waktu sekitar
setahun. Dengan kemampuan teknologi komputer yang
tercepat saat ini, faktorisasi bilangan sebesar 400
digit akan membutuhkan waktu seumur alam semesta.
(This is like a mission:impossible!)
Algoritma faktorisasi bilangan oleh Peter Shor
menunjukkan bahwa secara prinsip komputer kuantum
mampu memfaktorkan bilangan secara efisien, yaitu
membutuhkan waktu sebanding dengan polinomial dari
ukuran input, dengan memanfaatkan superposisi dan
keterkaitan (entanglement) dari keadaan kuantum.

13. THE ROAD AHEAD (CUAP-CUAP)

Kita sudah melihat bagaimana memanfaatkan fenomena
kuantum untuk melakukan berbagai jenis komunikasi
kuantum (quantum cryptography, dense coding, dan
teleportation) dan komputasi kuantum (algoritma Shor
untuk faktorisasi bilangan, dan algoritma Grover untuk
pencarian data.)
Dari sudut pandang teoretis, sampai sekarang masih
belum jelas sampai di mana komputer kuantum dapat
mengubah kompleksitas dari masalah tertentu. Tapi
beberapa aplikasi yang mungkin (secara prinsip) saat
ini adalah simulasi fenomena kuantum oleh komputer
kuantum (sebagaimana diusulkan oleh Feynman: the
quantum computer has no difficulty simulating itself),
dan masalah tertentu seperti faktorisasi dan pencarian
database. Tetapi kelihatannya komputer kuantum tidak
akan menggantikan komputer klasik (seperti juga fisika
kuantum tidak menggantikan fisika klasik: you never
fix your car to a 'quantum mechanics'), karena
komputer klasik cukup powerful untuk masalah-masalah
tertentu, sedangkan komputer kuantum tidak terlalu
praktis untuk masalah-masalah tertentu. Namun komputer
kuantum menjadi sangat powerful dalam menyelesaikan
masalah tertentu dibanding komputer klasik. Dan teori
informasi kuantum memberikan sudut pandang baru
mengenai kompleksitas dari sistem.
Dari sudut pandang eksperimentalis, quantum hardware
yang cukup besar untuk melakukan algoritma Shor atau
Grover (atau algoritma kuantum lainnya) mungkin masih
sulit dibangun dalam waktu dekat, entah 30 atau 50
tahun lagi. Tapi komunikasi kuantum seperti quantum
key distribution mungkin bisa direalisasi dalam waktu
dekat (mungkin bisa kurang dari 10 tahun lagi). Dense
coding dan teleportation dari sistem yang cukup besar
juga mungkin belum bisa direalisasi dalam waktu dekat.


Because nature isn't classical, dammit ! ....