KOMPUTASI PARALEL

#khalidsyahkp #4IA19 #Softskill #KomputasiQuantum

Nama      : Khalidsyah K.P

NPM       : 53415720

KELAS   : 4IA19

Konsep Paralel (Parallelism Concept) 

Pada dasarnya komputasi paralel digunakan untuk menyelesaikan suatu permasalahan besar, dengan memecah masalah tersebut menjadi bagian-bagian yang lebih kecil (sub-masalah). Kemudian sub-masalah tersebut diselesaikan oleh oleh kumpulan-kumpulan dari processor (multiprocessor) yang nantinya terlibat dalam pengeksekusian masalah tersebut, dimana setiap bagian sub-masalah diselesaikan oleh satu processor (single processor). Jadi kesimpulannya, jika sebuah masalah yang diselesaikan oleh satu processor membutuhkan berapa banyak sub-masalah dan berapa lama waktu yang dibutuhkan oleh processor tersebut. Kemudian dapat dilakukan perbandingan dengan masalah yang sama, jikan masalah tersebut dilakukan oleh lebih dari satu processor. 

Jadi komputasi paralel merupakan teknik untuk melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer independen secara bersamaan. Adapun tujuan utama komputasi paralel untuk mempersingkat waktu eksekusi program yang menggunakan komputasi serial. 

Gambar 1. Proses Konsep Paralel

Proses Distribusi (Distributed Processing) 

Proses Distribusi atau Distributed Processing adalah pengerjaan semua proses pengolahan data secara bersama antara komputer pusat dengan beberapa komputer yang lebih kecil dan saling dihubungkan melalui jalur komunikasi. Setiap komputer tersebut memiliki prosesor mandiri sehingga mampu mengolah sebagian data secara terpisah, kemudian hasil pengolahan tadi digabungkan menjadi satu penyelesaian total. Jika salah satu prosesor mengalami kegagalan atau masalah yang lain akan mengambil alih tugasnya. Jadi pengolahan paralel didistribusikan menggunakan pemrosesan paralel pada beberapa mesin. Contohnya dapat dilihat ketika bagaimana beberapa komunitas memungkinkan pengguna untuk mendaftar dan mendedikasikan komputer mereka sendiri untuk memproses beberapa data set yang diberikan kepada mereka oleh server. Ketika ribuan pengguna mendaftar untuk ini, banyak data dapat diproses dalam jumlah yang sangat singkat. 

Gambar 2. Distribusi Paralel

Arsitektur Komputer Paralel (Architectural Parallel Computer) 

Referensi dari Flynn mengenai Arsitektur Komputer Paralel menjelaskan bahwa dalam mendesain sebuah komputer, dikarakteristikkan oleh alur dari instruksi-instruksi yang akan diselesaikan oleh suatu arsitektur komputer. Taksonomi ini menghasilkan empat kemungkinan kombinasi dari pengoperasian instruksi, antara lain : 

Gambar 3. Model Pemrosesan Paralel

1. SISD (Single Instruction, Single Data) 

Arsitektur yang mewakili komputer serial, dimana hanya ada satu prosesor dan satu aliran data (memori) sehingga hanya ada satu task atau tugas yang dapat dieksekusi pada satu waktu. Contohnya arsitektur Von-Neumann. 

Gambar 4. (Single Instruction, Single Data)

2. SIMD (Single Instruction, Multiple Data) 

Eksekusi sebuah instruksi akan dilakukan bersamaan oleh beberapa prosesor, dimana sebuah prosesor dapat menggunakan data yang berbeda dengan prosesor lain.

Gambar 5. (Single Instruction, Multiple Data)

3. MISD (Multiple Instruction, Single Data) 

Berbagai instruksi akan dieksekusi secara bersamaan oleh beberapa prosesor dengan menggunakan data yang sama. 

Gambar 6. (Multiple Instruction, Single Data)

4. MIMD (Multiple Instruction, Multiple Data) 

Berbagai instruksi akan dieksekusi secara bersamaan oleh beberapa prosesor dimana masing-masing prosesor dapat menggunakan data yang berbeda.

Gambar 7. (Multiple Instruction, Multiple Data)

Implementasi Komputasi Paralel (Implementation Parallel Computation) 

Komputasi Paralel mempunyai prinsip yang bersesuaian dengan algoritma Divide and Conquer, yaitu membagi-bagi proses menjadi bagian-bagian yang cukup kecil dan memungkinkan untuk dikerjakan oleh sebuah unit komputasi. 

Terdapat 2 klasifikasi parallel computer yang penting, yaitu : Sebuah komputer dengan banyak unit komputasi internal, atau lebih dikenal sebagai Shared Memory Multiprocessor. Beberapa komputer yang terhubung melalui sebuah jaringan, atau lebih dikenal sebagai Distributed Memory Multicomputer. 

Pada bagian ini yaitu pada rendering Film digunakan unit Komputasi parallel Distributed Memory Multicomputer. Hal ini dikarenakan computer yang digunakan untuk membuat rendering filmnya adalah Kluster Komputer. Kluster computer adalah proses menghubungkan beberapa computer agar dapat bekerja secara bersama-sama dengan sebuah jaringan sebagai media penghubungnya. 

Komponen kluster biasanya saling terhubung dengan cepat melalui sebuah interkoneksi yang sangat cepat, atau juga melalui jaringan local (LAN). Keuntungan memakai Kluster Komputer ini yaitu pemrosesan dapat dilakukan lebih cepat karena mempunyai mesin-mesin yang masing-masing multiprocessor. Terdapat incremental Scalability dimana penambahan sistem-sistem baru dengan inkremen yang kecil. Dalam Kluster Komputer kegagalan yang terjadi di dalam satu node tidak berarti atau disebut dengan “Loss of service”. Dan yang terakhir yaitu biaya yang dibutuhkan lebih murah, hal ini dikarenakan Kluster computer dapat menghasilkan power komputasi yang sama atau lebih tinggi dari computer parallel sebenarnya. 

3D Rendering merupakan salah satu proses yang sangat penting dalam melakukan pengolahan gambar 3D. Tanpa dirender suatu gambar yang diolah oleh perangkat lunak animasi 3D hanya akan tampil dalam bentuk kumpulan point dan wireframe sederhana. Proses render melakukan “pembungkusan” tekstur pada objek yang bersesuaian sesuai cahaya yang datang pada objek tersebut. Namun proses render membutuhkan daya komputasi yang sangat besar karena banyaknya titik koordinat yang harus dikomputasi, terutama jika data 3D yang diolah cukup rumit. 

3D Rendering terdiri dari proses yang bertujuan untuk membentuk sebuah gambar dari sebuah model yang dibentuk oleh perangkat lunak animasi, model tersebut berisi data geometri, titik pandang, tekstur dan cahaya yang diperlukan untuk membuat gambar yang utuh. 3D Rendering merupakan proses yang sangat penting dan telah digunakan untuk berbagai macam penggunaan, seperti program permainan komputer, efek spesial pada film dan program simulasi. 

Salah satu cara untuk memecahkan masalah tersebut adalah dengan menggunakan algoritma Divide and Conquer yang diterapkan ke dalam metode Komputasi Parallel. Dalam Komputasi Parallel tiap-tiap bagian dikerjakan oleh unit pemrosesannya masing-masing, sesuai dengan kesepakatan Divide pada awal komputasi. Komputasi Parallel terbukti jauh lebih efektif untuk melakukan rendering objek 3D dibanding hanya menggunakan sebuah unit komputasi. Sebagai contoh suatu perusahaan animasi asal Jepang, membutuhkan waktu 165 tahun jika proses render yang dilakukan untuk membuat animasi berdurasi 100 menit hanya menggunakan sebuah unit komputasi. Sedangkan ketika perusahaan tersebut menggunakan metode Komputasi Parallel, proses tersebut hanya membutuhkan waktu 1 tahun saja. 

Di Indonesia LIPI Public Cluster adalah sarana komputasi paralel yang dibuka untuk pemakai umum secara cuma-cuma, persembahan LIPI Serpong, Indonesia. Sarana public cluster ini merupakan yang pertama di Indonesia. Rintisan awal mulai dilakukan pada tahun 2004. 

Hingga saat ini, Pusat Penelitian Fisika Lembaga Ilmu Pengetahuan Indonesia (LIPI), hingga saat ini telah berhasil merakit 35 note komputer. Rangkaian komputer ini dijadikan satu membentuk satu cluster untuk kemudian difungsikan mengolah suatu data yang sangat kompleks. Kami menyebutnya kluster karena komputer ini dirakit jadi satu dari beberapa komputer, kata Laksana Tri Handoko, Peneliti Teori Fisika LIPI. 

Komputer ini meski dijadikan satu, namun tetap dapat dipecah dan difungsikan hanya sesuai note (komputer pc yang terangkai di dalam kluster) yang kita perlukan. Misalnya untuk mengolah data hanya butuh tiga hingga empat note, maka hanya jumlah note tersebut saja yang bisa dipakai, lainnya tidak. 

Handoko mengatakan bahwa fungsi kluster ini yang umum dikenal masyarakat adalah sebagai alat pembantu simulasi suatu model. Kebanyakan adalah mahasiswa yang memanfaatkannya, kata Handoko. Hingga saat ini dari 35 note yang terpasang, telah lebih dari 60 orang yang memanfaatkannya. Kebanyakan mereka yang menggunakan adalah untuk kepentingan pemrograman, pendataan atau analisa misalnya untuk identifikasi DNA. Kami juga disini sudah memiliki gen bank, tembahnya. 

Kluster ini menurut Handoko, hampir sama dengan miliknya mesin pencari google. Bedanya jika google memiliki 1.000 note, maka LIPI hanya punya 35 note. Rencananya akan ditambah hingga 45 note. Kecepatannya untuk level superkomputer, kluster Puslit Fisika LIPI mencapai 150 gigaflops. Kecepatan ini masih berada pada kecepatan superkomputer terendah minimal sebesar 135 gigaflops.

Message Passing & OpenMP

Pada bagian komputasi parallel ini akan dibahas tentang Message Passing dan OpenMP.

Pembahasan Jurnal:

Algoritma genetika sekuensial untuk menyelesaikan Container Loading Problem bekerja hanya dengan menggunakan satu  processor  saja meskipun dijalankan pada system multicore. Tujuan dari penelitian ini adalah untuk mengoptimalkan kinerja system multicore. Untuk mengoptimalkan kinerja system multicore diperlukan adanya paralelisasi algoritma genetika untuk menyelesaikan Container Loading Problem.

Dalam penelitian ini paralelisasi yang digunakan adalah paralelisasi shared memory menggunakan OpenMP. Paralelisasi dalam OpenMP dilakukan melalui penyisipan pragma OMP paralel. Dari algoritma genetika serial Container Loading Problem akan diparalelisasi menggunakan OpenMP menjadi algoritma genetika parallel Container Loading Problem. Selanjutnya akan dilakukan pengujian waktu eksekusi algoritma dan perhitungan  speedup.

Hasil dari penelitian ini berupa hasil pengujian kinerja algoritma parallel yang menunjukkan bahwa waktu komputasialgoritma paralel lebih kecil dari algoritma sekuensial sebelum diparalelisasi menggunakan OpenMP. Waktukomputasi yang lebih kecil ini menyatakan efisiensi kinerja algoritma paralel yang lebih baik dari algoritmasekuensial. Peningkatan efisiensi ini juga dapat diidentifikasi dari Speedup  paralelisasi yang semakin besar. Kesimpulan diperoleh dari penelitian ini adalah bahwa paralelisasi terhadap algoritma genetika untuk menyelesaikan Container Loading Problem akan meningkatkan efisiensi waktu komputasi melalui pemanfaatan sistem  multicore.

Message Passing

Massage Passing merupkan suatu teknik bagaimana mengatur suatu alur komunikasi messaging terhadap proses pada system. Message passing dalam ilmu komputer adalah suatu bentuk komunikasi yang digunakan dalam komputasi paralel, pemrograman-berorientasi objek, dan komunikasi interprocess. Dalam model ini, proses atau benda dapat mengirim dan menerima pesan yang terdiri dari nol atau lebih byte, struktur data yang kompleks, atau bahkan segmen kode ke proses lainnya dan dapat melakukan sinkronisasi. Paradigma Message passing yaitu :

1.  Banyak contoh dari paradigma sekuensial dipertimbangkan bersama-sama.

2.Programmer membayangkan beberapa prosesor, masing-masing dengan memori, dan menulis sebuah program untuk berjalan pada setiap prosesor.

3. Proses berkomunikasi dengan mengirimkan pesan satu sama lain.

Terdapat beberapa metode dalam pengiriman pesan yaitu :

·        Synchronous Message Passing

Pengirim menunggu untuk mengirim pesan sampai penerima siap untuk menerima pesan. Oleh karena itu tidak ada buffering. Selain itu Pengirim tidak bisa mengirim pesan untuk dirinya sendiri.

·        Ansynchronous Message Passing

Pengirim akan mengirim pesan kapanpun dia mau. Pengirim tidak peduli ketika penerima belum siap untuk menerima pesan. Oleh karena itu diperlukan buffering untuk menampung pesan sementara sampai penerima siap menerima pesan. Selain itu pengirim dapat pesan untuk dirinya sendiri.

OpenMP (Open Multiprocessing)

OpenMP adalah Application Programing Interface (API) yang mendukung pemrograman multiprosesing shared memory dalam bahasa C/C++ dan fortran pada berbagai arsitektur dan sistem operasi diantaranya: Solaris, AIX, HP-UX,GNU/Linux, Mac OS X, dan Windows.

OpenMP adalah model portabel dan skalabel yang memberikan interface sederhana dan fleksibel bagi programer shared memory dalam membangun aplikasi paralel. Program multithread dapat ditulis dalam berbagai cara. Beberapa diantaranya memungkinkan untuk melakukan interaksi yang kompleks antar thread. OpenMP mencoba untuk memberikan kemudahan pemrograman serta membantu dalam menghindari kesalahan program, melalui pendekatan terstruktur. Pendekatan ini dikenal sebagai model pemrograman fork-join.

OpenMP bekerja berdasarkan model shared memory, maka secara default data dibagi diantara thread-thread dan dapat terlihat dari setiap thread. Terkadang program akan membutuhkan variabel dengan nilai thread spesifik. Jika setiap thread memiliki variabel duplikat akan sangat berpotensi memiliki nilai yang berbeda-beda pada setiap variabel duplikat tersebut.

Sinkronisasi (pengkoordinasian) aksi dari thread adalah sesuatu yang sangat penting untuk menjamin data yang harus dibagi dan untuk mencegah terjadinya data race condition. Secara default OpenMP telah menyediakan mekanisme untuk menunggu thread dalam suatu tim thread sehingga semua thread menyelesaikan tugasnya dalam region, kemudian dapat melanjutkan ke proses selanjutnya. Mekanisme ini dikenal sebagai barrier.

Pemrograman CUDA GPU

CUDA(Compute Unified Device Architecture) adalah suatu skema yang dibuat oleh NVIDIA agar NVIDIA selaku GPU (Graphic Processing Unit) mampu melakukan komputasi tidak hanya untuk pengolahan grafis namun juga untuk tujuan umum. Jadi dengan adanya CUDA kita dapat memanfaatkan banyak prosesor dari NVIDIA untuk melakukan proses perhitungan ataunpun komputasi yang banyak.

Platform CUDA dapat diakses oleh pengembang perangkat lunak melalui library CUDA-accelerated , perintah kompiler (seperti OpenACC ), dan ekstensi untuk bahasa pemrograman standar industri, termasuk C, C++ dan Fortran . C / C++ programmer menggunakan CUDA C / C + +, yang disusun dengan "nvcc", NVIDIA LLVM berbasis C / C++ compiler, dan Fortran programmer dapat menggunakan 'CUDA Fortran', yang disusun dengan PGI CUDA Fortran compiler dari The Portland Grup. Selain library, arahan compiler, CUDA C / C++ dan CUDA Fortran, platform CUDA mendukung interface komputasi lainnya, termasuk Khronos Grup 's OpenCL , Microsoft DirectCompute , dan C++ AMP . Pemrograman pihak ketiga juga tersedia untuk Python , Perl , Fortran , Java , Ruby , Lua , Haskell, Matlab , IDL , dan dukungan asli di Mathematica.

GPU dalah sebuah processor khusus untuk memepercepat dan mengubah memori untuk mempercepat pemrosesan gambar. GPU ini sendiri biasanya berada di dalam graphic card komputer ataupun laptop

Dalam permainan komputer industri, GPU yang digunakan tidak hanya untuk rendering grafis tetapi juga dalam perhitungan fisika permainan (efek fisik seperti puing-puing, asap, api, cairan), contoh termasuk PhysX dan Bullet . CUDA juga telah digunakan untuk mempercepat aplikasi non-grafis dalam biologi komputasi , kriptografi dan bidang lainnya oleh urutan besarnya atau lebih.

CUDA memiliki beberapa keunggulan dibandingkan tradisional perhitungan tujuan umum pada GPU (GPGPU) menggunakan API grafis:

1.       Tersebar membaca - kode dapat membaca dari alamat sewenang-wenang dalam memori.

2.       Memori bersama - CUDA memperlihatkan cepat memori bersama wilayah (sampai 48KB per Multi-Processor) yang dapat dibagi di antara benang. Ini dapat digunakan sebagai cache dikelola pengguna, memungkinkan bandwidth yang lebih tinggi daripada yang mungkin menggunakan pencarian tekstur.

3.       Download lebih cepat dan readbacks ke dan dari GPU.

4.       Dukungan penuh untuk integer dan bitwise operasi, termasuk pencarian tekstur bulat.

SUMBER :

https://anggasaputro.wordpress.com/2016/06/29/konsep-komputasi-paralel/

https://pandanwulan.wordpress.com/2015/06/28/konsep-distribusi-processing-arsitektur-komputer-paralel-thread-programming-message-passing-atau-openmp-dan-pemrograman-cuda-pada-gpu/

https://isnaenimh.wordpress.com/2015/06/26/konsep-proses-distribusi-arsitektur-komputer-paralel/

https://andri102.wordpress.com/game/soft-skill/konsep-komputasi-parallel-processing/

http://ajiraksakumala.blogspot.com/2016/06/tugas-ke-4-pengantar-komputasi-modern.html

http://debelist.blogspot.com/2016/05/parallel-computation-pengantar-message.html

http://nafa1108.blogspot.co.id/2015/11/pengantar-pemrograman-cuda-gpu.html

Pengantar Quantum Komputasi

PENGANTAR QUANTUM KOMPUTASI

#4IA19

#PengantarQuantumKomputasi

#TugasSoftskill

#PengantarKomputasiModern

 1.     Pendahulan (Stely Novenus Tarigan)

Quantum Komputasi terdiri dari 2 kata yaitu “Quantum” dan “Komputasi”. Quantum artinya jumlah/quantity tanpa batas, dan Komputasi artinya ilmu komputer dimana algoritma digunakan untuk menemukan suatu cara dalam memecahkan masalah dari sebuah data input. Sehingga Quantum Komputasi adalah suatu bidang studi yang berperan pada perkembangan teknologi komputer yang didasari prinsip-prinsip teori kuantum, yang menjelaskan sifat dan perilaku energi dan materi pada tingkat kuantum (atom dan subatom).

Komputer Kuantum disini merupakan komputer/alat hitung yang menggunakan sebuah fenomena mekanika kuantum, seperti superposisi dan keterkaitan, untuk melakukan operasi data. Dalam komputer pada umumnya untuk menghitung jumlah data dengan menggunakan bit, sedangkan dalam komputer kuantum sudah menggunakan qubit.

Pengembangan komputer dengan sistem kuantum memerlukan algoritma baru yang sesuai dengan prinsip kuantum. Beberapa fisikawan seperti Charles H. Bennett dari IBM, Paul A. Benioff dari Argonne National Laboratory, Richard P. Feynman dari California Institute of Technology (Caltech).

Sistem kuantum yang dapat melakukan proses penghitungan merupakan suatu ide yang dikemukakan oleh Richard P. Feynman dan sistem ini bisa menjadi simulator percobaan fisika kuantum. Sehingga para ilmuwan mulai melakukan riset mengenai sistem kuantum tersebut. Saat ini telah ditemukan dua algoritma baru yang bisa digunakan dalam sistem kuantum yaitu algoritma shor dan algoritma grover. Contohnya adalah pemfaktoran (factoring) sebuah bilangan besar masih terlalu sulit bagi komputer meskipun mudah untuk diverifikasi. Itulah sebabnya pemfaktoran bilangan besar ini banyak digunakan dalam metode kriprografi untuk melindungi data.

 

  2.     Entanglement (Cynthia Diana Sinaulan)

Entanglement merupakan efek dari mekanik kuantum yang mengaburkan jarak antara partikel individual sehingga sulit untuk menggambarkan partikel tersebut terpisah walaupun anda berusaha untuk memindahkan mereka. Entanglement juga merupakan gambaran partikel yang dapat berkorelasi dan diprediksi berinteraksi satu sama lain tanpa terpaut jarak. Entanglement secara teoritis dapat mempercepat komputasi dan diyakini dapat memecahkan batasan pada komputer dan kuantum.

Kuantum entanglement adalah bagian dari fenomena kuantum mechanical yang menyatakan bahwa dua atau lebih objek dapat digambarkan mempunyai hubungan dengan objek lainnya walaupun objek tersebut berdiri sendiri dan terpisah dengan objek lainnya. Fenomena ini dimanfaatkan oleh ilmuan dalam pembuatan Quantum Computing.

Einstein mengkritisi teori kuantum mechanical, ia menunjukkan kelemahan dari teori tersebut yang menggunakan entanglement merupakan sesuatu yang “spooky action at  a distance” karena Einstein tidak mempercayai bahwa partikel kuantum dapat mempengaruhi partikel lainnya melebihi cahaya. Kuantum entanglement dapat diimplementasi dalam berbagai bidang seperti pengiriman pesan rahasia yang sulit untuk di-enkripsi dan pembuatan komputer yang mempunyai performa cepat.

 

  3.     Pengoprasian Data Qubit (Kemal Nurfajri)

Jika pada komputer klasik terdapat bit sebagai memorinya, komputer kuantum menggunakan qubit atau quantum bit sebagai memori dasar informasi. Perbedaan antara bit dan qubit adalah jika bit pada suatu waktu hanya dapat merepresentasikan satu state saja yaitu 0 atau 1, qubit dapat merepresentasikan 0, 1 atau gabungan keduanya yang disebut dengan quantum superposition. Jadi, jika n bit hanya dapat merepresentasikan salah satu dari 2ⁿ states, n qubit dapat merepresentasikan 2ⁿstates tersebut secara bersamaan atau lebih mudahnya 1 qubit dapat menampung lebih dari 1 bit.

Suatu komputer quantum mengoperasikan qubit menggunakan quantum gates danmeasurments. Dimana perhitungan dimulai menggunakan quantum gates dan berakhir pada measurments yang menghasilkanclassical states.

 

  4.     Quantum Gates (Fitri Ayu Anggraini & Novita Rakhmawati)

Gerbang kuantum atau gerbang logika kuantum adalah rangkaian kuantum dasar yang beroperasi pada sejumlah kecil qubit . Mereka adalah analog untuk komputer kuantum ke gerbang logika klasik untuk komputer digital konvensional. Logika logika kuantum bisa dibalik , tidak seperti banyak gerbang logika klasik. Beberapa gerbang logika klasik universal, seperti gerbang Toffoli , memberikan reversibilitas dan dapat dipetakan secara langsung ke gerbang logika kuantum. Gerbang logika kuantum diwakili oleh matriks-matriks kesatuan .

Gerbang kuantum yang paling umum beroperasi pada ruang satu atau dua qubit. Ini berarti bahwa sebagai matriks, gerbang kuantum dapat digambarkan dengan matriks 2 x 2 atau 4 x 4 dengan baris ortonormal .

Ingat Penyelidikan gerbang logika kuantum tidak terkait dengan logika kuantum , yang merupakan formalisme dasar untuk mekanika kuantum berdasarkan modifikasi beberapa aturan logika proposisional .

Berikut ini merupakan contoh dari gerbang kuantum :

a.      Gerbang hadamard

Gerbang ini beroperasi dengan qubit tunggal. Hal ini ditunjukkan oleh matriks Hadamard:

Karena baris matriks bersifat ortogonal, H memang merupakan matriks kesatuan.

b.      Fase shifter gates

Gates di kelas ini beroperasi dengan qubit tunggal. Mereka diwakili oleh 2 x 2 matriks dari bentuknya dimana θ adalah pergeseran fasa .

c.       Gerbang Terkendali

Misalkan U adalah gerbang yang beroperasi pada qubit tunggal dengan representasi matriks

Gerbang terkontrol U adalah gerbang yang beroperasi pada dua qubit sedemikian rupa sehingga qubit pertama berfungsi sebagai kontrol.

|00⟩ ↦ |00⟩

|01⟩ ↦ |01⟩

|10⟩ ↦ |1⟩ U | 0⟩ = |1⟩ ( x 00|0⟩ + x 01|1⟩)

|11⟩ ↦ |1⟩ U | 1⟩ = |1⟩ ( x 10| 0⟩ + x 11| 1⟩)

Dengan demikian matriks gerbang U yang dikontrol adalah sebagai berikut:

d.      Gerbang Takterkendali

Karena gerbang ini bisa direduksi menjadi gerbang yang lebih elementer, biasanya tidak termasuk dalam repertoar dasar gerbang kuantum. Disebutkan disini hanya untuk kontras dengan gerbang yang dikontrol sebelumnya.

 

Universal Quantum Gates

Satu set gerbang kuantum universal adalah seperangkat gerbang yang memungkinkan operasi pada komputer kuantum dapat dikurangi. Satu set sederhana dari gerbang kuantum universal dua qubit adalah gerbang Hadamard ( H ), gerbang rotasi fase , dan gerbang yang dikendalikan-TIDAK , sebuah kasus khusus yang dikendalikan-U sedemikian itu

Sebuah gerbang tunggal yang terdiri dari gerbang kuantum universal juga dapat diformulasikan dengan menggunakan gerbang Deutsch tiga-qubit, D ( θ )

Gerbang logika klasik universal, gerbang Toffoli , dapat direduksi menjadi gerbang Deutsch, , sehingga menunjukkan bahwa semua operasi logika klasik dapat dilakukan pada komputer kuantum universal.

 

     5.     Algoritma Shor (Alfan Fadhila A)

Algoritma Shor merupakan algoritma yang ditemukan oleh Peter Shor pada tahun 1995. Sebuah komputer kuantum dapat memecahkan sebuah kode rahasia yang saat ini secara umum digunakan untuk mengamankan pengiriman data. Jika data disandikan melalui kode RSA, data yang dikirimkan akan aman karena kode RSA tidak dapat dipecahkan dalam waktu yang singkat. Selain itu, pemecahan kode RSA membutuhkan kerja ribuan komputer secara paralel sehingga kerja pemecahan ini tidaklah efektif.

Algoritma yang berdasarkan dari sebuah teori bilangan: fungsi F(a) = x^amod n adalah fungsi periodik jika x adalah bilangan bulat yang relatif prima dengan n. Dalam Algoritma Shor, n akan menjadi bilangan bulat yang hendak difaktorkan.

Bila menghitung fungsi tersebut pada komputer konvensional untuk jumlah yang eksponensial, akan membutuhkan waktu eksponensial pula. Pada masalah ini algoritma quantum shor memanfaatkan pararellisme quantum untuk melakukannya hanya dengan satu langkah.

Dikarenakan F(A) adalah fungsi periodik, jadi fungsi ini memiliki sebuah periode r. Diketahui x⁰mod n = 1, maka x^rmod n = 1, begitu juga x^2r mod n dan seterusnya.

Dengan informasi ini dan manipulasi persamaan sederhana berikut:

x^r ≡ 1 mod n

(x^r/2)² ≡ 1 mod n

(x^r/2)² – 1 ≡ 0 mod n

Dengan anggapan r adalah angka genap:

(x^r/2 – 1)(x^r/2 + 1) ≡ 0 mod n

Dapat dilihat bahwa hasil dari (x^r/2 – 1)(x^r/2 + 1) adalah kelipatan n. Maka selama |x^r/2| ≠ 1, setidaknya salah satu dari (x^r/2 – 1) atau (x^r/2 + 1) memiliki faktor yang sama dengan n. Maka, dengan menghitung gcd(xr/2 – 1,n) dan gcd(x^{r/2 + 1},n) faktor dari n akan didapat.

Lain halnya untuk menghitung r dari persamaan x^r ≡ 1 mod n akan membutuhkan waktu eksponensial di komputer konvensional. Oleh karena itu proses ini perlu dijalankan dengan komputer quantum agar seluruh nilai superposisi akan terhitung dalam sekali jalan.

Langkah-langkah Algoritma Shor

Masalah yang hendak dipecahkan adalah: Diketahui sebuah bilangan komposit N, dicari sebuah bilangan bulat x dengan x bernilai 1 < x < N.

1.      Algoritma Shor untuk mencari faktor dari bilangan bulat n, dapat dipecah menjadi langkah-langkah berikut:

Menentukan apakan N adalah prima, genap, atau perpangkatan dari bilangan prima. Jika ya, maka Algoritma Shor tidak akan dipakai. Terdapat algoritma konvensional yang efisien untuk menentukan jenis n dan memfaktorkannya. Langkah ini akan dilakukan di komputer konvensional.

2.      Ambil bilangan bulat q, dimana q adalah nilai dari perpangkatan 2 yang memenuhi: n² ≤ q < 2n². Langkah ini akan dilakukan di komputer konvensional.

3.      Mencari bilangan bulat random x yang relatif prima dengan n. Terdapat algoritma konvensional yang efisien untuk proses ini. Langkah ini akan dilakukan di komputer konvensional.

4.      Membuat quantum register yang dipartisi menjadi dua bagian, katakan register 1 dan register 2. Register satu harus cukup besar untuk merepresentasikan bilangan bulat sebesar q-1, sedangkan register 2 sebesar n-1. Langkah ini perlu dilakukan di komputer quantum.

5.      Masukkan kedalam register 1 superposisi yang setara dari semua bilangan bulat 0 sampai q-1, dan register 2 bilangan bulat 0. Langkah ini dapat dilaksanakan dengan menggunakan hadamard gates. Langkah ini perlu dilakukan di komputer quantum. Pada langkah ini, state dari quantum memory register adalah :

6.      Aplikasikan fungsi x^a mod n ke dalam semua bilangan bulat di dalam register 1, dan menyimpan hailnya di register 2. Karena prinsip pararellisme quantum, proses ini hanya perlu dilakukan sekali saja. Langkah ini perlu dilakukan di komputer quantum. Pada langkah ini, state dari quantum memory register adalah:

7.      Mengukur dan memeriksa nilai yang disimpan pada register 2, mendapatkan nilai k. Langkah ini perlu dilakukan di komputer quantum. Langkah ini akan membuat register 1 semua superposisi state a dimana x^amod n ≠ k “kolaps”. Setelah langkah ini, state dari quantum memory register adalah:

Dengan A adalah himpunan dari a’ dimana x n k a mod = , dan ||A|| adalah jumlah elemen dalam himpunan tersebut.

8.      Menghitung transformasi quantum Fourier pada register 1. Langkah ini perlu dilakukan di komputer quantum. Sifat transformasi Fourier quantum akan mengubah |a> menjadi

Karena pararellisme quantum, langkah ini cukup dilakukan satu kali. State dari register setelah transformasi:

9.      Ukur nilai state register satu, katakan nilai ini sebagai m. Bilangan bulat m memiliki probabilitas tinggi adalah kelipatan q/r, dimana r adalah periode yang kita cari. Langkah ini perlu dilakukan di komputer quantum.

10.  Gunakan nilai m untuk mencari nilai r, dengan nilai m dan q diketahui. Jika r tidak dapat ditentukan, maka kembali ke langkah 4. Langkah ini akan dilakukan di komputer konvensional.

11.  Setelah r diketahui, faktor n dapat ditentukan dengan menghitung gcd(xr/2 + 1, n) dan gcd(xr/2-1,n). Disaat ini faktor n telah ditemukan, dan Algoritma telah selesai. Langkah ini akan dilakukan di komputer konvensional.

Kelemahan dan Kelebihan Algoritma Shor

Berbeda dengan komputer konvensional yang deterministik, komputer quantum bersifat nondeterministik dan probabilistik, yang berarti suatu algoritma kadang kala dapat berhasil dan kadang kala akan gagal biarpun untuk kondisi yang sama. Hal ini dikarena sifat pengukuran dalam mekanika quantum yang probabilistik. Akibatnya, Algoritma Shor dapat gagal menemukan faktor karena beberapa sebab, diantaranya:

·         Hasil pengukuran dari transformasi quantum fourier dapat berupa 0, membuat langka ke 10 tak mungkin dilakukan.

·         Kadang hasil faktorisasi algoritma akan menghasilkan 1 dan n, yang secara definisi benar tetapi tidak berguna.

·         Bila hasil r ganjil, maka langkah ke 10 tidak dapat dilakukan.

Walaupun begitu, probabilitas sukses akan bertambah setiap kali algoritma diulang. Dalam Algoritma Shor yang dimodifikasi dengan penentuan order, probabilitas sukses setelah 2 kali jalan lebih dari 60%, dan probabilitas sukses setelah 4 kali jalan lebih dari 90%.

Referensi :

https://www.kompasiana.com/madeteling/teori-quantum/

https://dwijati.wordpress.com/komputasi-modern/

http://chachados.blogspot.co.id/2013/05/komputasi-kuantum.html/ 

http://crows-haikal.blogspot.co.id/2015/08/quantum-computing-entanglement.html

https://djuneardy.blogspot.co.id/2015/04/quantum-computing-entanglement.html

http://ikhsanturion.blogspot.co.id/2016/05/tugas-softskill-teori-komputasi-quantum.html

https://djuneardy.blogspot.co.id/2015/04/quantum-computing-entanglement.html

https://yuliatwn.wordpress.com/2016/04/26/498/

https://amoekinspirasi.wordpress.com/2014/05/15/pengertian-quantum-computing-dan-implementasinya/

https://en.wikipedia.org/wiki/Quantum_computing

http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2008-2009/Makalah2008/Makalah0809-087.pdf

https://mamz.weebly.com/quantum-computation.html

https://www.quantiki.org/wiki/quantum-gates