Quantum gates,Distributed Processing, Paralel Computation, Algoritma Shor | Pengantar Komputasi Moderen

Pengantar Komputasi Moderen

Feri Chandra

Nadhiranisa S.M

Tubagus M RayhanT

Chisei Nesa

Kelas 4IA19

Fakultas Teknik Informatika

Quantum Gates

Quantum Gates adalah sebuah gerbang kuantum yang dimana berfungsi mengoperasikan bit yang terdiri dari 0 dan 1 menjadi qubits. dengan demikian Quantum gates mempercepat banyaknya perhitungan bit pada waktu bersamaan. Quantum Gates adalah blok bangunan sirkuit kuantum, seperti klasik gerbang logika yang untuk sirkuit digital konvensional.

Quantum Gates / Gerbang Quantum merupakan sebuah aturan logika / gerbang logika yang berlaku pada quantum computing. Prinsip kerja dari quantum gates hampir sama dengan gerbang logika pada komputer digital. Jika pada komputer digital terdapat beberapa operasi logika seperti AND, OR, NOT, pada quantum computing gerbang quantum terdiri dari beberapa bilangan qubits, sehingga quantum gates lebih susah untuk dihitung daripada gerang logika pada komputer digital.

Quantum Logic Gates, Prosedur berikut menunjukkan bagaimana cara untuk membuat sirkuit reversibel yang mensimulasikan dan sirkuit ireversibel sementara untuk membuat penghematan yang besar dalam jumlah ancillae yang digunakan. Diantaranya :

1.      Gerbang CNOT.

2.      Gerbang SWAP.

3.      Gerbang TOFFOLI.

4.      Gerbang FREDKIN.

Gerbang CNOT

-          Table CNOT

-          CNOT gate 2 bit logical

Gerbang SWAP

-          Table SWAP

-          SWAP gate 2 bit logical

Gerbang SWAP dan CNOT

Gerbang TOFFOLI

-          Tabel TOFFOLI komputasi reversibel klasik yang bersifat universal.

-          Gerbang TOFFOLI juga dapat dibilang gerbang yang berhubungan dengan gerbang CNOT.

Gerbang FREDKIN

-          Tabel FREDKIN komputasi reversibel klasik yang bersifat universal.

-          Gerbang FREDKIN juga dapat dibilang gerbang yang berhubungan dengan gerbang SWAP.

 

DISTRIBUTED PROCESSING

Distributed Processing

Distributed Processing mengerjakan 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.

Pemrosesan terdistribusi adalah penggunaan lebih dari satu prosesor untuk melakukan pengolahan untuk tugas individu. Contoh pemrosesan terdistribusi dalam sistem database Oracle muncul dalam Gambar 6-1.

Dalam Bagian A dari gambar, klien dan server yang terletak di komputer yang berbeda, komputer ini terhubung melalui jaringan. Server dan klien dari sistem database Oracle berkomunikasi melalui Net8, antarmuka jaringan Oracle.

Dalam Bagian B dari gambar, satu komputer memiliki lebih dari satu prosesor, dan prosesor yang berbeda memisahkan pelaksanaan aplikasi klien dari Oracle.

Figure 6-1 The Client/Server Architecture and Distributed Processing

Oracle client / server arsitektur dalam lingkungan pemrosesan terdistribusi memberikan manfaat sebagai berikut

·         Aplikasi client tidak bertanggung jawab untuk melaksanakan setiap pengolahan data. Sebaliknya, mereka meminta masukan dari pengguna, data permintaan dari server, dan kemudian menganalisa dan menyajikan data ini menggunakan kemampuan tampilan dari workstation klien atau terminal (misalnya, dengan menggunakan grafik atau spreadsheet).

·         Aplikasi client tidak tergantung pada lokasi fisik dari data. Jika data tersebut akan dipindahkan atau didistribusikan ke server database lain, aplikasi terus berfungsi dengan modifikasi sedikit atau tidak ada.

·         Oracle memanfaatkan fasilitas multitasking dan berbagi-memori sistem operasi yang mendasarinya. Akibatnya, ini memberikan tingkat tertinggi kemungkinan konkurensi, integritas data, dan kinerja untuk aplikasi kliennya.

·         Klien workstation atau terminal dapat dioptimalkan untuk penyajian data (misalnya, dengan menyediakan grafis dan dukungan mouse) dan server dapat dioptimalkan untuk pengolahan dan penyimpanan data (misalnya, dengan memiliki sejumlah besar memori dan ruang disk) .

·         Dalam lingkungan jaringan, Anda dapat menggunakan workstation klien murah untuk mengakses data remote dari server efektif.

·         Jika perlu, Oracle dapat ditingkatkan sebagai sistem Anda tumbuh. Anda dapat menambahkan beberapa server untuk mendistribusikan beban database pengolahan seluruh jaringan (horizontal skala), atau Anda dapat memindahkan Oracle ke komputer mini atau mainframe, untuk mengambil keuntungan dari kinerja sistem yang lebih besar itu (vertikal skala). Dalam kedua kasus, semua data dan aplikasi yang dipertahankan dengan modifikasi sedikit atau tidak ada, karena Oracle adalah portabel antara sistem.

·         Dalam lingkungan jaringan, data bersama disimpan pada server, bukan pada semua komputer dalam sistem. Hal ini membuat lebih mudah dan lebih efisien untuk mengelola akses konkuren.

·         Dalam lingkungan jaringan, aplikasi client mengirimkan permintaan database ke server dengan menggunakan pernyataan SQL. Setelah diterima, pernyataan SQL diproses oleh server, dan hasilnya dikembalikan ke aplikasi klien. Jaringan lalu lintas disimpan ke minimum karena hanya permintaan dan hasilnya dikirim melalui jaringan.

Distributed data processing /  pemrosesan data terdistribusi

Merupakan sekumpulan peralatan pemrosesan yang saling terhubung melalui jaringan yang mengerjakan tugas-tugas tertentu.

Pemrosesan terdistribusi dapat dikelompokan berdasarkan beberapa kriteria yaitu :

1. Struktur antar hubungan
2. Kesaling tergantungan komponen-komponen.
3. Keselarasan antar komponen.

 Distributed database system / system database terdistribusi

Merupakan sekumpulan database yang saling terhubung secara logical dan secara fisik terdistribusi pada berbagai tempat melalui jaringan computer.

Sistem yang mengelola  database terdistribusi dan menyediakan mekanisme agar distribusi transparent adalahdistributed database management system (DDBMS).

Ciri-ciri untuk system yang bukan merupakan system database terdistribusi :

1. Sistem yang berisi kumpulan file
2. Berbagai arsitektur fisik berkait dengan system multiprocessor.

Ciri sistem database distribusi

1. Data disimpan pada sejumlah tempat. Setiap tempat secara logic terdiri dari processor tunggal.
2. Processor pada tempat yang berbeda tersebut dihubungkan dengan jaringan computer.
3. Bukan sekumpulan file yang berada pada berbagai tempat tetapi merupakan database pada berbagai tempat.
4. Setiap tempat mempunyai kemampuan untuk mandiri memproses permintaan user yang membutuhkan akses kedata ditempat tersebut, dan juga mampu untuk memproses data yang tersimpan di tempat lain 

Keuntungan dan Kelemahan sistem database distribusi

-          Keuntungan :

1. Pengelolaan secara transparan data terdistribusi dan replicated.
2. Mengacu pada struktur organisasi
3. Meningkatkan kemampuan untuk share dan otonomi local
4. Meningkatkan ketersediaan data
5. Meningkatkan kehandalan
6. Meningkatkan unjuk kerja
7. Memudahkan pengembangan system

-          Kelemahan :

1. Kompleksitas manajemen
2. Control integritas lebih sulit
3. Biaya pengembangan
4. Keamanan
5. Kurang standarisasi
6. Menambahkan kebutuhan penyimpanan
7. Lebih sulit dalam mengatur lingkungan data
8. Menambah biaya pelatihan.

PARALLEL COMPUTATION (komputasi pararel)

Komputasi paralel adalah salah satu teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer independen secara bersamaan. Ini umumnya diperlukan saat kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam jumlah besar (di industri keuangan, bioinformatika, dll) ataupun karena tuntutan proses komputasi yang banyak. Kasus kedua umum ditemui di kalkulasi numerik untuk menyelesaikan persamaan matematis di bidang fisika (fisika komputasi), kimia (kimia komputasi) dll.

• Mesin paralel, Untuk melakukan aneka jenis komputasi paralel ini diperlukan infrastruktur mesin paralel yang terdiri dari banyak komputer yang dihubungkan dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu masalah. Untuk itu diperlukan aneka perangkat lunak pendukung yang biasa disebut sebagai middleware yang berperan untuk mengatur distribusi pekerjaan antar node dalam satu mesin paralel. Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan komputasi. Tidak berarti dengan mesin paralel semua program yang dijalankan diatasnya otomatis akan diolah secara paralel !

• GRID, merupakan pengembangan teknologi mesin paralel dengan memanfaatkan jaringan pita lebar di era dijital. Dengan adanya jaringan pita lebar, paralelisasi tidak hanya dilakukan antar komputer dalam satu jaringan, tetapi juga antar mesin paralel yang terpisah secara geografis.

• Pemrograman Paralel,  teknik pemrograman komputer yang memungkinkan eksekusi perintah/operasi secara bersamaan (komputasi paralel), baik dalam komputer dengan satu (prosesor tunggal) ataupun banyak (prosesor ganda dengan mesin paralel) CPU. Bila komputer yang digunakan secara bersamaan tersebut dilakukan oleh komputer-komputer terpisah yang terhubung dalam suatu jaringan komputer lebih sering istilah yang digunakan adalah sistem terdistribusi (distributed computing).

Motivasi

Tujuan utama dari pemrograman paralel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan (dalam waktu yang sama), semakin banyak pekerjaan yang bisa diselesaikan. Analogi yang paling gampang adalah, bila anda dapat merebus air sambil memotong-motong bawang saat anda akan memasak, waktu yang anda butuhkan akan lebih sedikit dibandingkan bila anda mengerjakan hal tersebut secara berurutan (serial). Atau waktu yg anda butuhkan memotong bawang akan lebih sedikit jika anda kerjakan berdua.

Performa dalam pemrograman paralel diukur dari berapa banyak peningkatan kecepatan (speed up) yang diperoleh dalam menggunakan tehnik paralel. Secara informal, bila anda memotong bawang sendirian membutuhkan waktu 1 jam dan dengan bantuan teman, berdua anda bisa melakukannya dalam 1/2 jam maka anda memperoleh peningkatan kecepatan sebanyak 2 kali.

• Peningkatan Kecepatan

Peningkatan kecepatan dapat diformulasikan dalam persamaan berikut ini

{\displaystyle S={\frac {T_{1}}{T_{j}}}} {\displaystyle S={\frac {T_{1}}{T_{j}}}}

Dimana {\displaystyle T_{1}} {\displaystyle T_{1}} adalah waktu yang dibutuhkan untuk menyelesaikan pekerjaan (program komputer) bila dijalankan dalam satu komputer. Dan {\displaystyle T_{j}} {\displaystyle T_{j}} adalah waktu yang dibutuhkan jika pekerjaan dikerjakan bersamaan oleh beberapa komputer.

Ada limitasi dalam usaha membuat suatu program komputer berjalan lebih efisien melalui peningkatan kecepatan, hukum yang menetapkan batasan ini dikenal sebagai Hukum Amdahl. Ide dari hukum amdahl ini adalah bahwa anda hanya akan bisa meningkatkan efisiensi program komputer anda, sebatas pada bagian tertentu dari program tersebut yang dapat di paralelkan. Sementara bagian yang memang harus dilaksanakan secara berurutan, akan menjadi penentu performa akhir.

Kembali ke analogi memasak tadi, bila anda harus menggunakan sarung tangan sebelum menyalakan kompor ataupun memotong bawang, maka waktu yang anda butuhkan untuk memakai sarung tangan ini adalah waktu serial, yang tidak dapat dihindari. Sementara waktu untuk memasak dan memotong bawang tadi adalah bagian yang bisa diparalelkan.

• Hukum Amdahl, Telah dijelaskan bahwa dari {\displaystyle T_{1}} {\displaystyle T_{1}} (waktu yg dibutuhkan menjalankan pekerjaan dalam satu komputer) tadi, ada sebagian yg tidak bisa diparalelkan. Untuk menyatakan ini kita gunakan notasi {\displaystyle \alpha } {\displaystyle \alpha } dimana {\displaystyle 0\leq \alpha \leq 1} {\displaystyle 0\leq \alpha \leq 1} menunjukkan berapa bagian dari {\displaystyle T_{1}} {\displaystyle T_{1}} yang tidak bisa dijadikan paralel (atau bagian serial dari program ini).

Maka kita ketahui {\displaystyle \alpha *T_{1}} {\displaystyle \alpha *T_{1}} adalah waktu yg tidak akan terpengaruh oleh bertambahnya komputer yg digunakan (a).

Sisanya {\displaystyle (1-\alpha )*T_{1}} {\displaystyle (1-\alpha )*T_{1}} adalah waktu yang akan berkurang menjadi {\displaystyle {\frac {(1-\alpha )*T_{1}}{N}}} {\displaystyle {\frac {(1-\alpha )*T_{1}}{N}}} bila kita menggunakan N komputer tambahan {b) .

Sehingga waktu total yang dibutuhkan untuk menjalankan pekerjaan dalam N komputer adalah (a) + (b) alias :

{\displaystyle T_{N}=\alpha *T_{1}+{\frac {(1-\alpha )*T_{1}}{N}}} {\displaystyle T_{N}=\alpha *T_{1}+{\frac {(1-\alpha )*T_{1}}{N}}}

Peningkatan kecepatan yang kita peroleh dari persamaan ini adalah :

{\displaystyle S_{N}={\frac {T_{1}}{\alpha *T_{1}+{\frac {(1-\alpha )*T_{1}}{N}}}}} {\displaystyle S_{N}={\frac {T_{1}}{\alpha *T_{1}+{\frac {(1-\alpha )*T_{1}}{N}}}}}

Mungkin anda akan mendapati persamaan speed up yang terlihat berbeda tetapi pada dasarnya sama. Persamaan dibawah, bisa didapat dari persamaan di atas, dengan mengeliminasi komponen {\displaystyle T_{1}} {\displaystyle T_{1}} (pada bagian atas dan bawah persamaan), lalu mengatur N dan {\displaystyle \alpha } {\displaystyle \alpha }

{\displaystyle S_{N}={\frac {N}{1+\alpha (N-1)}}} {\displaystyle S_{N}={\frac {N}{1+\alpha (N-1)}}}

Bila anda cermati persamaan di atas, bisa dilihat bahwa jika kita menggunakan komputer yang amat banyak ( {\displaystyle N\rightarrow \infty } {\displaystyle N\rightarrow \infty }) komponen (b) akan dapat diabaikan, menyisakan persamaan :

{\displaystyle S_{N}={\frac {1}{\alpha }}} {\displaystyle S_{N}={\frac {1}{\alpha }}}

Inilah batas maksimum peningkatan kecepatan yang bisa dicapai menurut hukum Amdahl yaitu perbandingan terbalik dari seberapa banyak bagian serial dari suatu pekerjaan.

Dalam sistem terdistribusi dimana anda berusaha menggunakan lebih banyak prosesor untuk menyelesaikan masalah, akan ada imbal balik. Menggunakan komputer tambahan dari lokasi yang berbeda memberikan anda sumber komputasi baru, tetapi juga melibatkan biaya komunikasi tambahan, saat anda harus memberikan pekerjaan tersebut pada komputer yg terpisah.

• Bahasa populer dalam Pemrograman Paralel

MPI Message Passing Interface, bahasa pemrograman dengan basis pertukaran pesan.

PVM Parallel Virtual machine.

Istilah-istilah dalam pemrograman paralel

1. Embarasingly Parallel adalah pemrograman paralel yang digunakan pada masalah-masalah yang bisa diparalelkan tanpa membutuhkan komunikasi satu sama lain. Sebenarnya pemrograman ini bisa dibilang sebagai pemrograman paralel yang ideal, karena tanpa biaya komunikasi, lebih banyak peningkatan kecepatan yang bisa dicapai.
2. Taksonomi dari model pemrosesan paralel dibuat berdasarkan alur instruksi dan alur data yang digunakan:
3. SISD Single Instruction Single Datapath, ini prosesor tunggal, yang bukan paralel.
4. SIMD Single Instruction Multiple Datapath, alur instruksi yang sama dijalankan terhadap banyak alur data yang berbeda. Alur instruksi di sini kalau tidak salah maksudnya ya program komputer itu. trus datapath itu paling ya inputnya, jadi inputnya lain-lain tetapi program yang digunakan sama.
5. MIMD Multiple Instruction Multiple Datapath, alur instruksinya banyak, alur datanya juga banyak, tetapi masing-masing bisa berinteraksi.
6. MISD Multiple Instruction Single Datapath, alur instruksinya banyak tetapi beroperasi pada data yang sama.

• Perkembangan di Indonesia, Di Indonesia, usaha untuk membangun infrastruktur mesin paralel sudah dimulai sejak era 90-an, meski belum pada tahap serius dan permanen. Namun untuk pemrograman paralel sudah sejak awal menjadi satu mata-kuliah wajib di banyak perguruan tinggi terkait. Baru pada tahun 2005 dimulai pembuatan infrastruktur mesin paralel permanen, misalnya yang dikembangkan oleh Grup Fisika Teoritik dan Komputasi di P2 Fisika LIPI. Didorong oleh perkembangan pemrograman paralel yang lambat, terutama terkait dengan sumber daya manusia (SDM) yang menguasainya, mesin paralel LIPI ini kemudian dibuka untuk publik secara cuma-cuma dalam bentuk LIPI Public Cluster (LPC)[3]. Saat ini LPC telah dikembangkan lebih jauh menjadi gerbang komputasi GRID di Indonesia dengan kerjasama global menjadi IndoGRID.

Contoh parallel programming models

Name	Class of interaction	Class of decomposition	Example implementations
Actor model	Asynchronous message passing	Task	D, Erlang, Scala, SALSA
Bulk synchronous parallel	Shared memory	Task	Apache Giraph, Apache Hama, BSPlib
Communicating sequential processes	Synchronous message passing	Task	Ada, Occam, VerilogCSP, Go
Circuits	Message passing	Task	Verilog, VHDL
Dataflow	Message passing	Task	Lustre, TensorFlow, Apache Flink
Functional	Implicit	Task	Concurrent Haskell, Concurrent ML
LogP machine	Synchronous message passing	Not specified	None
Parallel random access machine	Shared memory	Data	Cilk, CUDA, OpenMP, Threading Building Blocks, XMTC

Algoritma Shor

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

Menghitung fungsi ini di 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.

Karena F(A) adalah fungsi periodik, maka fungsi ini memiliki sebuah periode r. Diketahui  x0mod n = 1, maka xr mod n =1, begitu juga x2r mod n dan seterusnya.

Dengan informasi ini dan manipulasi persamaan sederhana berikut:

1.      xr ≡ 1 mod n

2.      (xr/2)2 ≡ 1 mod n

3.      (xr/2)2 - 1≡ 0 mod n

4.      Dengan anggapan r adalah angka genap:

5.      (xr/2 – 1)(xr/2 + 1) ≡ 0 mod n

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

Tetapi untuk menghitung r dari persamaan xr ≡ 1 mod n akan membutuhkan waktu eksponensial di komputer konvensional. Karena itu proses ini perlu dijalankan dengan komputer quantum agar seluruh nilai superposisi akan terhitung dalam sekali jalan.

Proses kunci lainnya adalah transformasi quantum fourier. Efeknya adalah akan meningkatkan puncakpuncak amplitudo probabilistik superposisi dimana probabilitas r adalah periode yang benar. Proses ini akan meningkatkan probabilitas kebenaran r.

Kelemahan dan Kelebihan Algoritma Quantum 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%.

Maka walaupun perlu berjalan untuk waktu yang tak ditentukan, waktu tersebut adalah polinomial. Lebih tepatnya, Algoritma Shor berjalan dengan kecepatan O((log n)2*log log n) pada komputer quantum, dan harus melakukan paska prosesing selama O(log n) pada komputer konvensional. Secara utuh algoritma ini polinomial.

REFERENSI

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

https://computing.llnl.gov/tutorials/parallel_comp/

http://maya-ardiati-fst12.web.unair.ac.id/artikel_detail-117049-Prokom-Artikel%20Quantum%20Computing%20Dan%20Quantum%20Crypto.html

https://andynovawijaya.wordpress.com/tugas/tugas-study-kasus-distributed-accounting/

https://towardsdatascience.com/demystifying-quantum-gates-one-qubit-at-a-time-54404ed80640