Teori Quantum Computing

Quantum Computation

Pendahuluan

Sejarah

Pada tahun 1970-an pencetusan atau ide tentang komputer kuantum pertama kali muncul oleh para fisikawan dan ilmuwan komputer, seperti Charles H. Bennett dari IBM, Paul A. Benioff dari Argonne National Laboratory, Illinois, David Deutsch dari University of Oxford, dan Richard P. Feynman dari California Institute of Technology (Caltech). Feynman dari California Institute of Technology yang pertama kali mengajukan dan menunjukkan model bahwa sebuah sistem kuantum dapat digunakan untuk melakukan komputasi. Feynman juga menunjukkan bagaimana sistem tersebut dapat menjadi simulator bagi fisika kuantum. Pada tahun 1985, Deutsch menyadari esensi dari komputasi oleh sebuah komputer kuantum dan menunjukkan bahwa semua proses fisika, secara prinsipil, dapat dimodelkan melalui komputer kuantum. Dengan demikian, komputer kuantum memiliki kemampuan yang melebihi komputer klasik. Pada tahun 1995, Peter Shor merumuskan sebuah algoritma yang memungkinkan penggunaan komputer kuantum untuk memecahkan masalah faktorisasi dalam teori bilangan. Sampai saat ini, riset dan eksperimen pada bidang komputer kuantum masih terus dilakukan di seluruh dunia. Berbagai metode dikembangkan untuk memungkinkan terwujudnya sebuah komputer yang memilki kemampuan yang luar biasa ini. Sejauh ini, sebuah komputer kuantum yang telah dibangun hanya dapat mencapai kemampuan untuk memfaktorkan dua digit bilangan. Komputer kuantum ini dibangun pada tahun 1998 di Los Alamos, Amerika Serikat, menggunakan NMR (Nuclear Magnetic Resonance)

Quantum Computation

Studi komputasi kuantum sistem teoritis perhitungan (komputer kuantum) yang menggunakan langsung fenomena kuantum mekanik, seperti superposisi dan belitan, untuk melakukan operasi pada data. komputer kuantum yang berbeda dari komputer elektronik digital berdasarkan transistor. Sedangkan komputer digital membutuhkan data yang akan dikodekan menjadi digit biner (bit), yang masing-masing selalu dalam salah satu dari dua negara yang pasti (0 atau 1), komputasi kuantum menggunakan bit kuantum (qubit), yang dapat di superposisi negara. Sebuah mesin Turing kuantum adalah teori model seperti komputer, dan juga dikenal sebagai komputer kuantum universal. Quantum komputer berbagi kesamaan teoritis dengan komputer non-deterministik dan probabilistik. Bidang komputasi kuantum yang digagas oleh karya Paul Benioff dan Yuri Manin pada tahun 1980, Richard Feynman pada tahun 1982, dan David Deutsch pada tahun 1985. Sebuah komputer kuantum dengan spin sebagai bit kuantum juga diformulasikan untuk digunakan sebagai kuantum ruang-waktu pada tahun 1968. Pada tahun 2016, pengembangan komputer kuantum yang sebenarnya masih dalam masa pertumbuhan, tetapi percobaan telah dilakukan dimana operasi komputasi kuantum dieksekusi pada sejumlah kecil bit kuantum. Kedua penelitian praktis dan teoritis terus, dan banyak pemerintah nasional dan badan-badan militer mendanai penelitian komputasi kuantum dalam upaya untuk mengembangkan komputer kuantum untuk sipil, bisnis, perdagangan, lingkungan dan tujuan keamanan nasional, seperti kriptoanalisis. komputer kuantum berskala besar akan mampu memecahkan masalah-masalah tertentu jauh lebih cepat daripada komputer klasik yang menggunakan bahkan yang terbaik algoritma saat ini dikenal, seperti faktorisasi integer menggunakan algoritma Shor atau simulasi kuantum sistem banyak-tubuh. Ada algoritma quantum, seperti algoritma Simon, yang berjalan lebih cepat daripada yang mungkin algoritma klasik probabilistik. Mengingat sumber daya yang cukup komputasi, komputer klasik secara teori dapat dibuat untuk mensimulasikan algoritma kuantum, seperti komputasi kuantum tidak melanggar Gereja -Turing tesis. Di sisi lain, komputer kuantum mungkin dapat efisien memecahkan masalah yang ada komputer klasik akan mampu memecahkan dalam jumlah waktu yang wajar.

Komputer klasik dan quantum

komputasi klasik bergantung, pada tingkat akhir, pada prinsip-prinsip yang diungkapkan oleh aljabar Boolean, beroperasi dengan (biasanya) 7-mode prinsip gerbang logika, meskipun mungkin ada dengan hanya tiga mode (yang DAN, TIDAK, dan COPY). Data harus diproses dalam keadaan biner eksklusif pada setiap titik waktu – yaitu, baik 0 (off / false) atau 1 (on / true). Nilai-nilai ini adalah digit biner, atau bit. Jutaan transistor dan kapasitor di jantung komputer hanya bisa dalam satu negara pada setiap titik. Sedangkan saat itu setiap transistor atau kapasitor perlu baik dalam 0 atau 1 sebelum beralih menyatakan sekarang diukur dalam miliar detik, masih ada batas untuk seberapa cepat perangkat ini dapat dibuat untuk beralih negara. Seperti kita maju ke sirkuit yang lebih kecil dan lebih cepat, kita mulai mencapai batas fisik material dan ambang batas untuk hukum klasik fisika untuk diterapkan. Di luar ini, dunia kuantum mengambil alih, yang membuka potensi sebagai besar sebagai tantangan yang disajikan.

Quantum komputer, sebaliknya, dapat bekerja dengan dua modus gerbang logika: XOR dan mode kami akan menelepon QO1 (kemampuan untuk mengubah 0 menjadi superposisi 0 dan 1, gerbang logika yang tidak bisa eksis dalam komputasi klasik) . Dalam komputer kuantum, sejumlah partikel elemental seperti elektron atau foton dapat digunakan (dalam praktek, keberhasilan juga telah dicapai dengan ion), dengan baik biaya atau polarisasi mereka bertindak sebagai representasi dari 0 dan / atau 1. Setiap partikel ini dikenal sebagai bit kuantum, atau qubit, sifat dan perilaku partikel-partikel ini membentuk dasar dari komputasi kuantum. Dua aspek yang paling relevan fisika kuantum adalah prinsip-prinsip superposisi dan belitan.

superposisi

Pikirkan qubit sebagai elektron dalam medan magnet. spin elektron mungkin baik sejalan dengan bidang, yang dikenal sebagai keadaan spin-up, atau berlawanan dengan bidang, yang dikenal sebagai keadaan spin-down. Mengubah spin elektron dari satu keadaan ke keadaan lain dicapai dengan menggunakan pulsa energi, seperti dari laser – mari kita mengatakan bahwa kita menggunakan 1 unit energi laser. Tapi bagaimana kalau kita hanya menggunakan setengah unit energi laser dan benar-benar mengisolasi partikel dari segala pengaruh eksternal? Menurut hukum kuantum, partikel kemudian memasuki keadaan superposisi , di mana ia berperilaku seolah-olah itu di kedua keadaan secara bersamaan. Setiap qubit dimanfaatkan bisa mengambil superposisi dari kedua 0 dan 1. Dengan demikian, jumlah perhitungan bahwa sebuah komputer kuantum dapat melakukan adalah 2 ^ n, di mana n adalah jumlah qubit digunakan. Sebuah komputer kuantum terdiri dari 500 qubit akan memiliki potensi untuk melakukan 2 ^ 500 perhitungan dalam satu langkah. Ini adalah jumlah yang mengagumkan – 2 ^ 500 adalah jauh lebih atom dari ada di alam semesta (ini pemrosesan paralel benar – komputer klasik saat ini, bahkan disebut prosesor paralel, masih hanya benar-benar melakukan satu hal pada suatu waktu: hanya ada dua atau lebih dari mereka melakukannya). Tapi bagaimana partikel-partikel ini akan berinteraksi satu sama lain? Mereka akan melakukannya melalui belitan kuantum.

Entanglement

Belitan Partikel (seperti foton, elektron, atau qubit) yang berinteraksi di beberapa titik mempertahankan jenis koneksi dan dapat dijerat dengan saling berpasangan, dalam proses yang dikenal sebagai korelasi. Mengetahui keadaan spin dari satu partikel terjerat – atas atau bawah – memungkinkan seseorang untuk mengetahui bahwa spin dari pasangannya adalah dalam arah yang berlawanan. Bahkan lebih menakjubkan adalah pengetahuan yang, karena fenomena superposisi, partikel diukur tidak memiliki arah spin tunggal sebelum diukur, tetapi secara bersamaan di kedua spin-up dan spin-down. Keadaan spin partikel yang diukur diputuskan pada saat pengukuran dan dikomunikasikan kepada partikel berkorelasi, yang sekaligus mengasumsikan berlawanan arah spin dengan yang dari partikel yang diukur. Ini adalah fenomena nyata (Einstein menyebutnya “aksi seram di kejauhan”), mekanisme yang tidak bisa, belum, dijelaskan dengan teori apapun – itu hanya harus diambil seperti yang diberikan. belitan kuantum memungkinkan qubit yang dipisahkan oleh jarak yang luar biasa untuk berinteraksi satu sama lain secara instan (tidak terbatas pada kecepatan cahaya). Tidak peduli seberapa besar jarak antara partikel berkorelasi, mereka akan tetap terjerat selama mereka terisolasi.

Secara bersama-sama, superposisi kuantum dan belitan menciptakan daya komputasi sangat besar ditingkatkan. Di mana 2-bit register di komputer biasa dapat menyimpan hanya satu dari empat konfigurasi biner (00, 01, 10, atau 11) pada waktu tertentu, register 2-qubit dalam komputer kuantum dapat menyimpan semua empat angka secara bersamaan, karena masing-masing qubit mewakili dua nilai. Jika lebih qubit ditambahkan, peningkatan kapasitas diperluas secara eksponensial.

Pengoprasian Data Qubit

Sebuah qubit adalah unit dasar informasi dalam sebuah komputer kuantum. Sementara sedikit dapat mewakili hanya satu dari dua kemungkinan seperti 0 / 1, ya / tidak, qubit dapat mewakili lebih: 0 / 1, 1 dan 0, probabilitas terjadinya setiap saat dikombinasikan dengan qubit lebih, dan semua yang secara bersamaan. Secara umum komputer kuantum dengan qubit n bisa dalam superposisi sewenang-wenang hingga 2 n negara bagian yang berbeda secara bersamaan (ini dibandingkan dengan komputer normal yang hanya dapat di salah satu negara n 2 pada satu waktu). Untuk memanipulasi sebuah qubit, maka menggunakan Quantum Gates (Gerbang Kuantum). Cara kerjanya yaitu sebuah gerbang kuantum bekerja mirip dengan gerbang logika klasik. Gerbang logika klasik mengambil bit sebagai input, mengevaluasi dan memproses input dan menghasilkan bit baru sebagai output.

Algoritma Quantum Computing

Quantum computing menggunakan algoritma shor, algoritma grover, Deutsch-Jozsa dan algoritma simon.

Algoritma Shor merupakan sebuah algoritma kuantum yang efisien bisa menguraikan pada pengali jumlah besar. Algortima ini merupakan pusat pada sistem yang menggunakan teori bilangan untuk memperkirakan periodisitas dari urutan nomor. Ditemukan oleh Peter Shor. Algortima ini di perbaharui oleh Lov Grover dari Bell Labs pada tahun 1996, dengan algoritma yang sangat cepat dan terbukti menjadi yang tercepat mungkin untuk mencari melalui database tidak terstruktur. Algoritma ini sangat efisien sehingga hanya membutuhkan rata-rata, sekitar akar N persegi pencarian untuk menemukan hasil yang diinginkan, sebagai lawan pencarian dalam komputasi klasik, yang pada kebutuhan rata-rata N / 2 pencarian. N adalah jumlah total elemen. 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. 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.

Algoritma Grover adalah sebuah algoritma kuantum untuk mencari database disortir dengan entri N di O ( N1 / 2 ) waktu dan menggunakan O ( log N ) ruang penyimpanan (lihat notasi O besar ) . Lov Grover dirumuskan itu pada tahun 1996 . Dalam model komputasi klasik , mencari database unsorted tidak dapat dilakukan dalam waktu kurang dari waktu linier (jadi hanya mencari melalui setiap item optimal ). Algoritma Grover menggambarkan bahwa dalam model kuantum pencarian dapat dilakukan lebih cepat dari ini ; sebenarnya waktu kompleksitas O ( N1 / 2 ) adalah asimtotik tercepat mungkin untuk mencari database unsorted dalam model kuantum linear . Ini menyediakan percepatan kuadrat , seperti algoritma kuantum lainnya , yang dapat memberikan percepatan eksponensial atas rekan-rekan mereka klasik . Namun, bahkan percepatan kuadrat cukup besar ketika N besar. Seperti banyak algoritma kuantum , algoritma Grover adalah probabilistik dalam arti bahwa ia memberikan jawaban yang benar dengan probabilitas tinggi . Kemungkinan kegagalan dapat dikurangi dengan mengulangi algoritma. ( Sebuah Contoh Bahasa dari algoritma kuantum deterministik adalah algoritma Deutsch – Jozsa , Yang Selalu menghasilkan jawaban Yang BENAR).

Algoritma Deutsch-Jozsa memecahkan kotak hitam masalah yang mungkin memerlukan eksponensial banyak pertanyaan ke kotak hitam untuk setiap komputer deterministik, tetapi dapat dilakukan dengan tepat 1 query dengan sebuah komputer kuantum. Jika kita membiarkan kedua kuantum dibatasi-kesalahan dan algoritma klasik, maka tidak ada percepatan karena algoritma probabilistik klasik dapat memecahkan masalah dengan sejumlah konstan query dengan probabilitas kecil kesalahan. Algoritma menentukan apakah fungsi f adalah baik konstan (0 pada semua input atau 1 pada semua input) atau seimbang (mengembalikan 1 untuk setengah dari domain input dan 0 untuk setengah lainnya).

Algoritma Simon memecahkan masalah black-box secara eksponensial lebih cepat daripada algoritma klasik, termasuk dibatasi-kesalahan algoritma probabilistik. Algoritma ini, yang akan menghasilkan percepatan eksponensial atas semua algoritma klasik yang kita anggap efisien, adalah motivasi untuk algoritma Shor anjak.

Implementasi Quantum Computing

Implementasi quantum computing digunakan oleh suatu bada antariksa yang bernama NASA di amerika serikat. Pada 19 Nov 2013 Lockheed Martin, NASA dan Google semua memiliki satu misi yang sama yaitu mereka semua membuat komputer kuantum sendiri. Komputer kuantum ini adalah superkonduktor chip yang dirancang oleh sistem D – gelombang dan yang dibuat di NASA Jet Propulsion Laboratories. NASA dan Google berbagi sebuah komputer kuantum untuk digunakan di Quantum Artificial Intelligence Lab menggunakan 512 qubit D -Wave Two yang akan digunakan untuk penelitian pembelajaran mesin yang membantu dalam menggunakan jaringan syaraf tiruan untuk mencari set data astronomi planet ekstrasurya dan untuk meningkatkan efisiensi searchs internet dengan menggunakan AI metaheuristik di search engine heuristical. A.I. seperti metaheuristik dapat menyerupai masalah optimisasi global mirip dengan masalah klasik seperti pedagang keliling, koloni semut atau optimasi swarm, yang dapat menavigasi melalui database seperti labirin. Menggunakan partikel terjerat sebagai qubit, algoritma ini bisa dinavigasi jauh lebih cepat daripada komputer konvensional dan dengan lebih banyak variabel. Penggunaan metaheuristik canggih pada fungsi heuristical lebih rendah dapat melihat simulasi komputer yang dapat memilih sub rutinitas tertentu pada komputer sendiri untuk memecahkan masalah dengan cara yang benar-benar cerdas . Dengan cara ini mesin akan jauh lebih mudah beradaptasi terhadap perubahan data indrawi dan akan mampu berfungsi dengan jauh lebih otomatisasi daripada yang mungkin dengan komputer normal