QUANTUM COMPUTING LANGUAGE
PENGANTAR KOMPUTASI MODERN
Dosen: I Made Wiryana S. Kom. MApp Sc
Disusun Oleh : Kelompok 7
Aam Surganda
Benny Maulana Akbar
Muhammad Ridhwan
Muhammad Agus Y
Primadika Ramadhan
4IA08
KATA PENGANTAR
Segala puji dan syukur kami panjatkan kepada Tuhan Yang Maha Esa karena atas berkat rahmat dan karunia-Nya serta dorongan doa restu, dan dorongan dari berbagai pihak sehingga kelompok kami dapat menyelesaikan tugas penulisan buku ini dengan judul Quantum Computing. Kami penulis ingin mengucapkan banyak terimakasih kepada Bapak I Made Wiryana S. Kom. MApp Sc yang telah memberikan bimbingan maupun arahan kepada kelompok kami sehingga kami bisa memahami tugas yang telah diberikan oleh bapak dan mengerjakannya dengan baik.
Ucapan terimakasih juga kami ucapkan kepada teman-teman kelas 4IA08 yang telah turut membantu dalam memberikan informasi seputar pengerjaan tugas ini. Kami sebagai penulis menyadari bahwa buku yang kami susun ini masih jauh dari nilai sempurna, sehingga apabila ada penulisan nama maupun materi yang salah mohon dimaklumi. Dengan disusunnya buku ini, besar harapan kami dari tim penulis dapat membantu sekaligus memberikan informasi kepada pembaca agar dapat dimanfaatkan oleh pembaca di kemudian hari.
1 BAB I
PENDAHULUAN
Algoritma kuantum adalah suatu algoritma yang berhubungan dengan perhitungan kuantum. Semua masalah yang dapat diselesaikan pada komputer klasik dapat diselesaikan pada komputer kuantum. Komputer klasik yang ada saat ini materialnya sudah kuantum, sifat-sifat kuantum dipakai, tetapi proses komputasi belum kuantum. Algoritma kuantum ini menarik, karena algoritma ini mungkin dapat memecahkan beberapa masalah lebih cepat dibandingkan algoritma klasik. Hal inilah yang mungkin menyebabkan algoritma kuantum akan lebih populer dibandingkan algoritma klasik.
Peran teknologi dalam pengembangan teknologi informasi (IT, information technology), sudah tidak diragukan lagi. Bertambahnya kecepatan komputer dari waktu ke waktu, meningkatnya kapasitas hardisk dan memori, semakin kecil dan bertambahnya fungsi telepon genggam, adalah contoh contoh kongkrit produk teknologi di bidang IT. Teknologi komputer merupakan salah satu teknologi yang paling cepat mengalami perkembangan dan kemajuan. Komputer-komputer yang ada saat ini sudah mencapai kemampuan yang sangat mengagumkan. Tetapi kedahsyatan komputer tercanggih yang ada saat ini pun masih belum bisa memuaskan keinginan manusia yang bermimpi untuk membuat sebuah superkomputer yang benar-benar memiliki kecepatan super. Komputer yang nantinya layak untuk benar-benar disebut sebagai Komputer Super ini adalah Komputer Kuantum.
Teori tentang komputer kuantum ini pertama kali dicetuskan oleh fisikawan dari Argonne National Laboratory sekitar 20 tahun lalu. Paul Benioff merupakan orang pertama yang mengaplikasikan teori fisika kuantum pada dunia komputer di tahun 1981. Komputer yang biasa kita gunakan sehari-hari merupakan komputer digital. Komputer digital sangat berbeda dengan komputer kuantum yang super itu. Komputer digital bekerja dengan bantuan microprocessor yang berbentuk chip kecil yang tersusun dari banyak transistor. Microprocessor biasanya lebih dikenal dengan istilah Central Processing Unit (CPU) dan merupakan ‘jantung’nya komputer. Microprocessor yang pertama adalah Intel 4004 yang diperkenalkan pada tahun 1971. Komputer pertama ini cuma bisa melakukan perhitungan penjumlahan dan pengurangan saja. Adapun permasalahannya adalah ketidakpuasan manusia terhadap kecepatan pada komputer konvensional yang ada sekarang.
Kajian ini ditulis dengan tujuan untuk mengkaji sejauh mana teori-teori yang berkembang tentang komputer kuantum yang berkembang akhir-akhir ini. Sedangkan manfaat dari penelitian ini adalah untuk memperluas pengetahuan tentang teknologi komputer kuantum, khususnya bagi penulis dan pembaca.
2 BAB II
2.1 KOMPUTER DAN PEMROGRAMAN
Quantum Komputer Penerapan prinsip-prinsip fisika kuantum untuk bidang lead komputasi dengan konsep komputer kuantum, di mana data tidak disimpan sebagai bit dalam memori konvensional, tetapi sebagai keadaan kuantum gabungan dari banyak 2-state sistem qubit. Bab ini memperkenalkan dasar-dasar teoritis, komponen dan dasar operasi dari sebuah komputer kuantum serta beberapa model komputasi kuantum.
2.1.1 Church-Turing
Tesis Ide dasar dari ilmu komputasi modern adalah pandangan dari perhitungan sebagai mekanik, daripada proses murni mental. Sebuah metode, atau prosedur M untuk mencapai beberapa hasil yang diinginkan disebut efektif atau mekanik hanya dalam kasus.
- M diatur dalam hal jumlah terbatas petunjuk yang tepat (masing-masing instruksi diekspresikan dengan cara jumlah terbatas simbol);
- M akan, jika dilakukan tanpa kesalahan, selalu menghasilkan hasil yang diinginkan dalam jumlah terbatas langkah;
- M dapat (dalam praktek atau pada prinsipnya) dilakukan oleh manusia tanpa bantuan oleh mesin Hemat kertas dan pensil;
- Menuntut ada wawasan atau kecerdikan pada bagian dari manusia melaksanakannya.
Alan Turing dan Church Alonzo baik diformalkan definisi di atas oleh memperkenalkan konsep komputabilitas dengan mesin Turing dan konsep matematis setara dengan fungsi rekursif dengan kesimpulan sebagai berikut: Tesis LCMs Turing [mesin komputasi logis yaitu mesin Turing] dapat melakukan apa pun yang bisa digambarkan sebagai "rule of thumb" atau "murni mekanis". Tesis fungsi Church bilangan bulat positif secara efektif dihitung hanya jika rekursif. Seperti perintah diatas adalah sama, mereka sering disebut sebagai Tesis Church-Turing yang mendefinisikan ruang lingkup komputasi klasik ilmu pengetahuan.
2.1.2 Mesin Komputasi
Meskipun pendekatan operationalistic, konsep komputabilitas di atas tidak memiliki banyak kesamaan dengan sifat kontinyu fisika, agar dapat membangun sebuah mesin komputasi M, kita harus memperkenalkan fungsi pelabelan m yang memetakan analog keadaan fisik S (t) (misalnya ketegangan kapasitor) ke digital states komputasi s = (S (t)) (misalnya nilai sedikit) digital states harus string atas beberapa alfabet Σ terbatas. Karena definisi di atas computability membutuhkan jumlah terbatas kedua, simbol dan petunjuk, fungsi label hanya perlu untuk diterapkan pada diskrit antara states mesin S (t 0 ), S (t 1 ),. . . sehingga evolusi temporal mesin states S (t) dipetakan ke urutan komputasi states {s 0 , s 1 ,. . . s n } Di mana setiap transisi s i → s i +1 sesuai dengan salah satu fungsi saya i: Σ * → Σ * dari I set enumerable dari (sederhana) instruksi. 1 itu urutan π = {I 0 , saya 1 ,. . . saya n-1 } Disebut Program. States-states s 0 dan s n disebut input-output dan states. itu mesin M = (S, m, Σ, π) sehingga menerapkan fungsi f (s 0 ) = (I 0 ◦ I 1 ◦. . . ◦ I n-1 ) (s 0 ) Dengan s 0 = m (S (0)) ∈ Σ * (2.1) .
2.1.3 Perhitungan sebagai Proses Fisik Definisi
Di atas mesin komputasi menimbulkan pembatasan pada interpretasi keadaan fisik. Jika kita mempertimbangkan perhitungan sebagai fisik proses, bukan "mekanik" manipulasi simbol sebagaimana dimaksud dalam 2.1.1, kita bisa drop semua pembatasan dalam definisi di atas yang tidak memiliki ujud fisik.
2.1.4 Indeterminism
Seperti yang telah kami tunjukkan di 1.3.2.3, pengukuran O diamati dengan menurut Operator O hanya deterministik, jika sistem berada dalam eigenstate dari O. Untuk menjelaskan sifat stokastik pengukuran kuantum, kita memiliki untuk menggantikan fungsi pelabelan m oleh probabilistik Operator M: H → Σ * yang memilih secara acak string s menurut beberapa distribusi probabilitas δ Ψ : S → [0, 1] dengan P s δ Ψ (s) = 1.
2.1.5 Temporal Evolution
Karena tidak mungkin untuk non-destruktif mengukur sistem kuantum dan kami hanya tertarik pada hasil perhitungan, bagaimanapun, itu tidak perlu bahwa pelabelan didefinisikan untuk langkah-langkah perantara Ψ (t 1 ) Untuk Ψ (t n-1 ) dari perhitungan yaitu tidak diperlukan untuk "menonton" evolusi temporal sistem, selama sebagai label untuk input dan output-states Ψ 0 dan Ψ n diberikan. Sementara transisi Ψ (t i ) → Ψ (t i +1 ) Masih harus sesuai dengan (sederhana) operasi Ui dari set instruksi enumerable transformasi kuantum, operator Ui, tidak perlu secara langsung sesuai dengan fungsi dalam Σ * . 2 Pada 1.3.2.6 kami telah menunjukkan bahwa evolusi temporal sistem kuantum secara matematis digambarkan oleh operator kesatuan, sehingga π Program quantum = {U0, U 1,. . . U n-1 } Adalah komposisi transformasi kesatuan dasar.
2.2 Komponen-komponen Komputer Quantum
serta sebuah komputer kuantum klasik, pada dasarnya terdiri dari 3 bagian: a memori, yang memegang keadaan mesin saat ini, prosesor, yang melakukan operasi dasar pada keadaan mesin, dan beberapa jenis input / output yang memungkinkan untuk mengatur keadaan awal dan ekstrak keadaan akhir dari perhitungan.
2.2.1 Memory Quantum
Analogi kuantum untuk bit klasik adalah bit kuantum atau qubit. Sama seperti sedikit klasik diwakili oleh suatu sistem yang dapat mengadopsi salah satu dari dua yang berbeda menyatakan "0" dan "1" kita dapat mendefinisikan sedikit kuantum sebagai berikut: Definisi 1 (qubit) Sebuah qubit atau bit kuantum adalah sistem kuantum yang States dapat sepenuhnya dijelaskan oleh superposisi dari dua eigenstates orthonormal berlabel | 0i dan | 1i. Keadaan umum | Ψ> ∈ H dari qubit diberikan oleh
Nilai qubit adalah diamati N dengan Hermitian Operator N | ii = i | ii atas ruang Hilbert H = C 2 , Atau dalam representasi matriks
Nilai harapan N diberikan oleh
dengan demikian, hn i memberikan probabilitas untuk menemukan sistem dalam keadaan | 1i jika pengukuran dilakukan pada qubit.
2.2.2 Kombinasi Qubit
Jika kita menggabungkan 2 qubit, keadaan umum sistem yang dihasilkan adalah
Sementara kita masih dapat menentukan diamati berbeda N (1) dan N (2) untuk nilai setiap qubit dengan operator N (1) | ij i = i | ij i dan N (2) | ij i = j | ij i, mereka nilai harapan
tidak memungkinkan kita untuk merekonstruksi distribusi probabilitas yang sebenarnya antara eigenvalues. Untuk menggambarkan hal ini, pertimbangkan States
Semua States-States ini memiliki nilai harapan Hn (1) i = Hn (2) i = 1/2, yaitu jika kita mengukur qubit tunggal, kita mendapatkan salah | 0i atau | 1i dengan probabilitas yang sama; kami mendapatkan, bagaimanapun, benar-benar berbeda States-States pasca-pengukuran. Jika kita mengukur | 1i dalam qubit pertama, sehingga States-States pasca-pengukuran adalah
2.2.3 State Machine
Sementara keadaan komputer klasik dapat diberikan sebagai States yang berbeda dari semua bit dalam memori dan prosesor register, "keadaan qubit" adalah istilah yang tidak berarti, jika keadaan mesin adalah States gabungan lebih dari satu sistem. Definisi 2 (State Machine) Keadaan mesin Ψ dari sebuah komputer kuantum n-qubit adalah keadaan saat ini sistem gabungan n qubit identik subsistem. Umumnya, Ψ keadaan mesin dari komputer kuantum n-qubit diberikan oleh
Gabungan ruang Hilbert H dengan demikian komposisi n 1-qubit-Hilbert spasi Hi = C 2 , Yaitu
Jika kita menginterpretasikan vektor eigen | d 0 . . . d n-1 i sebagai digit biner, dengan d 0 karena setidaknya bit signifikan, kita dapat menulis ini sebagai
Operator Ni museruntuk nilai Ni muserdari-i th qubit diberikan oleh
Dan nilai harapannya
2.2.4 Subsistem
Seperti yang telah kita ditunjukkan di atas, memori komputer kuantum n-qubit adalah sistem gabungan n identik qubit-subsistem. Karena partisi ke subsistem hanyalah metodis, kita dapat mempertimbangkan m qubit pertama (m <n) sebagai subsistem tunggal dan menulis Ψ sebagai
Sebagai vektor basis | i, ji adalah States produk | i, ji = | ii | ji, ruang Hilbert H dapat ditulis sebagai kombinasi dari
Ini berarti bahwa transformasi kesatuan diterapkan pada subset yang berbeda dari qubit independen. Sebuah transformasi kesatuan U 0 atas m qubit pertama juga tidak mempengaruhi pengukuran qubit yang masih tersisa sejak probabilitas p 00 j untuk mengukur j dalam n tersisa - m qubit, yaitu untuk mendapatkan States pasca-pengukuran Formulir | Ψ 0 i = | ψj i | j i, adalah invarian ke U 0 , sebagai
2.2.5 Quantum Register
5 Quantum Register Gagasan di atas subsistem m-qubit dapat dengan mudah diperluas untuk sewenang-wenang urutan qubit. Definisi 3 (Quantum Register) Sebuah m qubit kuantum Register s adalah urutan qubit berbasis nol saling berbeda posisi hs 0 , s 1 . . . sm-1 i dari beberapa States mesin | Ψ> ∈ C 2 m dengan n ≥ m. Pengubahan urutan Operator Biarkan s menjadi daftar m qubit States n qubit | Ψ>. Menggunakan permutasi π sewenang-wenang lebih n elemen dengan π i = s i untuk i <m, kita dapat membuat operator penataan kembali kesatuan Πs dengan permutating qubit.
BPerhatikan bahwa terdapat (n - m)! permutasi Π (k) s yang cocok dengan di atas definisi, karena π i hanya didefinisikan untuk i <m. Operator kesatuan sesuai dengan mendasarkan transformasi (lihat 1.3.2.6), jadi kami dapat menulis | ~ Ψ> = Πs | Ψ> sebagai
Seperti di atas, ruang Hilbert yang berubah H dapat ditulis sebagai kombinasi
Register Observable Sama seperti dengan qubit tunggal, kita dapat mendefinisikan sebuah S diamati untuk suatu m-qubit mendaftar dengan operator
atau, jika kita menafsirkan vektor biner sebagai bilangan bulat,
2.3 Unit Pengolahan
Dalam n-bit komputer klasik, setiap langkah komputasi dapat dijelaskan oleh fungsi transisi I: B n → B n yang mengambil state S saat semua bit sebagai input dan mengembalikan sesuai States pasca-instruksi S 0 . Seperti yang telah kita ditunjukkan dalam 1.3.2.6, evolusi temporal sistem kuantum dapat dijelaskan oleh operator kesatuan. Bentuk umum dari sebuah kesatuan n-qubit Operator U atas ruang Hilbert H = C 2 n adalah
Jika kita membandingkan fungsi boolean operator kesatuan dari sudut ketat fungsional pandang kita dapat mengidentifikasi tiga perbedaan utama antara klasik dan operasi kuantum:
- Pembatalan: Sejak operator kesatuan, menurut definisi, sesuai dengan kondisi U † U = I, untuk setiap transformasi U terdapat invers transformasi U † . Akibatnya, perhitungan kuantum dibatasi untuk fungsi reversibel. 4
- Superposisi: Sebuah eigenstate | Ψ> = | ki dapat diubah menjadi superposisi eigenstates
Penjelasan matematis dari fitur ini terletak pada kenyataan bahwa Persyaratan hi | U † U | j i = δ ij lebih lemah dibandingkan dengan pseudo-klasik (lihat 2.2.2.4) Kondisi
yang membutuhkan eigenstates berubah tidak hanya menjadi ortonormal, tapi juga menjadi bentuk U | ki = | π k i dengan beberapa permutasi yang sesuai (yaitu fungsi reversibel) π lebih Z2 n.
- Paralelisme: Jika keadaan mesin | Ψ> sudah merupakan superposisi beberapa eigenstates, maka U transformasi diterapkan untuk semua eigenstates secara bersamaan.
Fitur ini komputasi kuantum disebut paralelisme kuantum dan merupakan konsekuensi dari linearitas transformasi kesatuan.
2.3.1 Daftar Operator
Instruksi dasar dari sebuah komputer klasik biasanya hanya beroperasi pada sangatsejumlah kecil bit dan biasanya independen dari jumlah total memori yang tersedia. Oleh karena itu lebih berguna untuk menggambarkan instruksi tersebut tidak sebagai fungsi boolean F atas seluruh States ruang B n (dalam kasus n bit mesin), tetapi berfungsi sebagai parameter f x lebih B m , Dimana vektor x ∈ Z n hanya memegang sedikit-posisi argumen yang relevan. Akibatnya kami mengacu pada hasil instruksi F sebagai "menerapkan f untuk bit x 0 , x 1 . . . x n-1 ". Meskipun jelas apa yang kita maksud dengan misalnya "Swapping bit 3 dan 5" pada komputer klasik, kita tidak bisa begitu saja mengadopsi konsep ini untuk kuantum komputasi, karena operator kesatuan beroperasi pada States dan qubit tunggal tidak memiliki States. 5 Pada 2.2.1.5 kami telah membuat sebuah daftar kuantum sebagai urutan (saling berbeda) qubit-posisi s = hs 0 , s 1 . . . sm-1 i, yang merupakan analogon kuantum di atas argumen vektor v, dan kelas (n - m)! penataan operator Π (k) s yang memenuhi kondisi
Definisi 4 (Daftar Operator) Operator mendaftar U (s) untuk mqubit kesatuan Operator U: C 2 m → C 2 m dan register kuantum m-qubit s on komputer kuantum n-qubit adalah operator n-qubit
dengan operator penataan sewenang-wenang Πs Jadi U (s) | Ψ> adalah apa yang kita benar-benar berarti, dengan "aplikasi operator U untuk kuantum mendaftar s ". Karena ada n! (n-m)! mungkin register m-qubit pada mesin n-qubit, yang diberikan operator yang m-qubit U dapat menggambarkan n! (n-m)! berbeda Transformasi U (s). Dalam analogi jaringan boolean, operator kesatuan yang dapat diterapkan untuk sewenang-wenang set qubit juga disebut sebagai gerbang kuantum.
2.3.2 Universal Quantum Gates
Hasil terkenal dari logika boolean klasik, adalah bahwa setiap fungsi mungkin f: B n → B m dapat dibangun sebagai komposisi dari universal kecil set operator jika kita bisa "kawat" input dan output untuk bit sewenang-wenang dalam jaringan umpan-maju. Contoh untuk set universal gerbang logis {∨ ¬}, {→, ¬} atau {¯ ∧}. Seperti disebutkan dalam 1.3.2.6, operasi kesatuan dapat digambarkan sebagai abstrak "Rotasi" di ruang Hilbert. Sebuah rotasi kompleks qubit tunggal memiliki bentuk umum.
Jika operator ini dapat diterapkan untuk sewenang-wenang subruang 2-dimensi H 0 = C 2 H = H 0 × H 00 , Maka setiap transformasi kesatuan dapat dibangun oleh komposisi paling banyak ³ redup H 2 ’langkah [14], sangat banyak seperti rotasi umum di R n dapat didekomposisi menjadi ³ n 2 ’rotasi sederhana dalam bidang-bidang koordinat. Dalam definisi kita tentang gerbang kuantum, bagaimanapun, kita dibatasi untuk ruang bagian sesuai dengan register kuantum (lihat 2.2.1.5), sehingga dalam kasus komputer kuantum n-qubit (dim H = 2 n ), Ini meninggalkan kita dengan hanya n mungkin subruang 1-qubit H 0 dan set yang sesuai dari operator daftar U 2 (i) (ω, α, β, φ). Sejak [U 2 (i) , U 2 (j) ] = 0, setiap komposisi U U 2 gerbang, akan menghasilkan transformasi bentuk.
Jadi hanya sebagai gerbang NOT sendiri tidak universal untuk logika boolean, untuk membangun satu set universal gerbang kuantum, kita memerlukan tambahan 2-qubit operasi, untuk menciptakan States multi-qubit terjerat. Salah satu kemungkinan untuk operator 2-qubit trivial adalah XOR yang didefinisikan sebagai XOR: | x, yi → | x, x ⊕ yi atau dalam notasi matriks:
Deutsch [6] telah menunjukkan bahwa himpunan {U 2 (ω, α, β, φ), XOR} sebenarnya universal untuk transformasi kesatuan. Selain itu, karena {U 2 (ω 0 , α 0 , β 0 , φ 0 ) n } adalah padat dalam {U 2 (ω, α, β, φ)} untuk hampir semua 6 set parameter, {U 2, XOR} adalah universal untuk sebagian U 2 dalam arti bahwa setiap transformasi kesatuan U dapat didekati dengan presisi sewenang-wenang. Deutsch juga mengusulkan 3-qubit gerbang D (θ) yang bersifat universal, sementara hanya membutuhkan satu parameter:
2.3.3 Pseudo-classical Operators
Bentuk umum dari operator kesatuan U atas n qubit adalah
Jika elemen matriks u ij adalah bentuk u ij = δ iπj dengan beberapa permutasi π, maka efeknya pada States dasar dapat digambarkan dalam hal klasik reversibel logika boolean. Definisi 5 (Operator Pseudo-klasik) A n-qubit Operator pseudo-klasik adalah operator kesatuan dari bentuk U: | ii → | π i i dengan beberapa permutasi π lebih Z 2 n . Untuk θ = π / 2 universal Deutsch gerbang D (θ) (2.36) berdegenerasi ke Operator pseudo-klasik
T adalah 3-bit dikendalikan-tidak atau Toffoli gerbang, yang merupakan gerbang universal untuk reversibel logika boolean. Misalkan f: Z2 n → Z2 n menjadi fungsi bijektif, maka sesuai pseudoclassical Operator F diberikan sebagai
2.3.4 Fungsi Quantum
Salah satu masalah yang jelas dari komputasi kuantum adalah pembatasan terhadap reversibel perhitungan. Pertimbangkan operasi aritmatika sederhana seperti pembagian integer oleh 2 (div2 0 | ii = | i/2i bahkan i dan | (i - 1) / 2i untuk aneh i). Jelas, ini operasi non-reversibel sejak div2 0 | 0i = div2 0 | 1i, sehingga tidak ada yang sesuai Operator pseudo-klasik ada. Namun, jika kita menggunakan register kedua dengan nilai awal | 0i, maka kita dapat mendefinisikan div2 Operator yang sesuai dengan kondisi div2 | x, 0i = | x, x/2i atau | x, (x - 1) / 2i masing-masing. Perilaku div2 | x, y = 6 0i tidak terdefinisi dan dapat diatur sewenang-wenang selama div2 tetap pseudo-klasik. 7 . Definisi 6 (Quantum Fungsi) Untuk setiap fungsi f: B n → B m (atau ekuivalen f: Z2 n → Z2 m) terdapat kelas operator pseudo-klasik F: C 2 n + m → C 2 n + m bekerja pada input n-qubit dan output m-qubit mendaftar dengan F | x, 0i = | x, f (x) i. Operator semacam itu disebut sebagai fungsi kuantum. Untuk fungsi boolean f: B n → B m terdapat (2 n + m - 2 n )! berbeda fungsi kuantum F.
2.3.5 Operator Bersyarat
Program klasik memungkinkan eksekusi kondisional kode dalam ketergantungan pada isi dari variabel boolean (bersyarat percabangan). Sebuah operator kesatuan, di sisi lain, adalah statis dan tidak memiliki flowcontrol intern. Namun demikian, kita kondisional dapat menerapkan operator n qubit U ke daftar kuantum dengan menggunakan memungkinkan qubit dan tentukan n +1 Operator qubit U 0
Jadi U hanya diterapkan untuk mendasarkan-vektor di mana memungkinkan bit diatur. Hal ini dapat mudah diperluas untuk mengaktifkan register panjang sewenang-wenang. Definisi 7 (Conditional Operator) Sebuah operator bersyarat U [[e]] dengan mengaktifkan mendaftar e adalah operator kesatuan bentuk
Operator kondisional yang sering digunakan dalam fungsi kuantum aritmatika dan operator pseudo-klasik lainnya. Jika arsitektur memungkinkan implementasi yang efisien dari controllednot gerbang C: | x, y 1 , y 2 . . . i → | (x ⊕ V i y i ), Y 1 , y 2 . . . i, maka operator pseudoclassical bersyarat dapat diwujudkan dengan hanya menambahkan memungkinkan string ke register kontrol dari semua operasi yang dikontrol-tidak.
2.4 Input dan Output
2.4.1 Quantum Computing dan Informasi
Pengolahan Dalam 2.1.3 kami telah menunjukkan bahwa penafsiran komputasi sebagai proses fisik, bukan manipulasi abstrak simbol, mengarah ke diperpanjang gagasan komputabilitas. Kami juga telah mengidentifikasi konsep kesatuan transformasi sebagai paradigma memadai untuk "komputabilitas fisik". Transformasi Kesatuan menggambarkan transisi antara States-States mesin dan dengan demikian evolusi temporal sistem kuantum. Gagasan tentang a (quantum) komputer sebagai "mesin komputasi" membutuhkan, bagaimanapun, bahwa evolusi sistem fisik sesuai dengan pengolahan informasi. Teori informasi klasik mensyaratkan bahwa setiap "masuk akal" informasi dapat dinyatakan sebagai serangkaian jawaban ya-tidak pertanyaan, yaitu string bit. Tapi tidak seperti perhitungan simbolik klasik, di mana setiap langkah tunggal dari perhitungan dapat dipetakan ke sedikit-string, perhitungan fisik memerlukan pelabelan tersebut hanya untuk awal dan keadaan mesin akhir (lihat 2.1.3.2), label yang membentuk input dan output dari perhitungan. Persyaratan ini sesuai penuh dengan interpretasi Copenhagen fisika kuantum, yang menyatakan bahwa setup dan hasil dari setiap eksperimen harus dijelaskan dalam istilah klasik.
2.4.2 Labeling States
Sebagai Ψ keadaan mesin tidak langsung dapat diakses, setiap realisasi fisik label harus sesuai dengan yang diamati O. Seperti yang telah ditunjukkan dalam 1.3.2.2, dalam fisika kuantum, O diamati diungkapkan oleh operator Hermitian O. Sebuah pilihan yang alami untuk O pada komputer kuantum n-qubit akan menjadi nilai-nilai klasik N = (N0 , N1 ,. . . Nn-1 ) Dari qubit menghanguskan dengan Hermitian operator
Seperti N hanya didefinisikan untuk eigenstates dari N (lihat 1.3.2.3), pelabelan m: H → B n hanya didefinisikan untuk states Ψ ∈ H dalam bentuk
2.4.3 Inisialisasi
Untuk mengatur komputer kuantum ke keadaan awal yang diinginkan | Ψ0 i = | s 0 i sesuai dengan boolean masukan string s 0 , Itu sudah cukup untuk menyediakan sarana untuk awalnya "Keren" semua qubit untuk | 0i dan kemudian menerapkan transformasi kesatuan U yang sesuai dengan kondisi U | 0i = | s 0 i. Definisi 8 Operator ulang R adalah operator konstan selama H dan didefinisikan sebagai R | Ψi = | 0i.
2.4.4 Pengukuran
Seperti telah dijelaskan dalam 1.3.2.3, adalah mustahil untuk mengamati keadaan kuantum ψ tanpa, pada saat yang sama, memaksa sistem untuk mengadopsi ψ states 0 yang adalah eigenstate dari Hermitian Operator O sesuai dengan yang diamati kuantitas O. Probabilitas transisi sehingga diberikan sebagai
2.4.5 Pengukuran Partial
Pengukuran tidak perlu menutupi keadaan mesin keseluruhan, tetapi juga bisa terbatas pada qubit tunggal atau register kuantum. Pertimbangkan dua register kuantum dengan n dan m qubit di states bagian
2.4.6 Model Quantum Computation
Dalam teori informasi klasik, konsep komputer yang universal dapat diwakili oleh beberapa model yang sama, yang berbeda sesuai dengan ilmiah pendekatan. Dari sudut pandang matematika, komputer yang universal adalah mesin yang mampu menghitung fungsi rekursif parsial, ilmuwan komputer sering menggunakan mesin Turing sebagai model favorit mereka, elektro-engineer mungkin akan berbicara tentang sirkuit logika sementara seorang programmer pasti akan lebih memilih bahasa pemrograman universal. Adapun perhitungan kuantum, masing-masing konsep klasik memiliki mitra kuantum:
2.4.7 Mathematical Model of QC
Paradigma perhitungan sebagai proses fisik mengharuskan QC bisa - pada prinsipnya - digambarkan dengan cara yang sama seperti realitas fisik lainnya, yang, untuk bidang fisika kuantum, adalah formalisme matematis Hilbert Operator ruang aljabar. Dasar-dasar dari formalisme ini, sejauh mereka yang relevan dengan QC, telah menjadi topik 1.3 dan bab 2. Setara moral dalam QC fungsi rekursif parsial, konsep matematika computability klasik, adalah operator kesatuan. Karena setiap Masalah klasik dihitung dapat dirumuskan sebagai menghitung nilai dari fungsi rekursif parsial, masing-masing perhitungan kuantum harus memiliki operator kesatuan yang sesuai. Deskripsi matematis dari operator secara inheren deklaratif; implementasi aktual untuk arsitektur kuantum tertentu yaitu dekomposisi algoritmik ke dalam operasi dasar, adalah di luar lingkup formalisme ini. Juga, karena model matematika memperlakukan operator kesatuan sebagai kotak hitam, tidak ada ukuran kompleksitas disediakan.
2.4.8 Quantum Turing Machines
Dalam analogi klasik Turing Machine (TM) beberapa proposisi Quantum Mesin Turing (QTM), sebagai model dari sebuah komputer kuantum yang universal telah dibuat [3, 1]. Mesin-keadaan lengkap | Ψi dengan demikian diberikan oleh superposisi dasar-states | l, j, si, di mana l adalah keadaan batin kepala, j posisi kepala dan s representasi biner dari pita-konten. Untuk menjaga H dipisahkan, yang (tak terbatas) bit-string s harus memenuhi kondisi states nol ekor yaitu hanya jumlah terbatas bit dengan sm 6 = 0 diperbolehkan. The analogi kuantum untuk fungsi transisi dari probabilistik klasik TM adalah operator T langkah, yang telah menjadi kesatuan untuk memungkinkan keberadaan dari Hamiltonian yang sesuai (lihat 1.3.2.5) dan memenuhi kondisi lokalitas yang dilakukan pita-qubit, serta untuk gerakan kepala. QTMs memberikan ukuran untuk eksekusi kali, tapi - seperti dengan klasik TM - menemukan operator langkah yang tepat bisa sangat sulit dan runtimecomplexity (yaitu jumlah aplikasi dari T dalam kaitannya dengan masalah size) tetap menjadi masalah. Di luar teori kompleksitas kuantum, QTMs adalah dari kurang penting.
2.4.9 Quantum Sirkuit
Sirkuit Quantum adalah setara QC untuk feed-forward boolean klasik jaringan, dengan satu perbedaan utama: karena semua perhitungan kuantum memiliki menjadi kesatuan, semua sirkuit kuantum dapat dievaluasi dalam dua arah (seperti dengan logika klasik reversibel). Sirkuit Quantum terdiri dari SD gerbang dan beroperasi pada qubit, sehingga dim (H) = 2 n dimana n adalah (tetap) nomor qubit. The "kabel" antara gerbang sehingga sesuai dengan kesatuan penataan operator Π s (lihat 2.2.1.5). Dibandingkan dengan jaringan umpan-maju boolean klasik, ini membebankan pembatasan.
2.5 KOMPUTER DAN PEMROGRAMAN
Seperti yang telah diilustrasikan dalam 2.1.2, perangkat komputer
- machine state S
- mampu melakukan satu set instruksi dengan baik antara mesin state
- menyediakan sarana untuk menginisialisasi dan mengukur keadaan mesin state
Urutan instruksi ¼ = Hi1, I2,. . . untuk mengubah keadaan awal S ke Sn akhir . Cara ¼ sebenarnya telah ditentukan, tergantung pada model komputasinya. kemungkinan bervariasi dari eksplisit, melalui jaringan maju (logical circuit) dan pohon keputusan pada otomata (Mesin Turing).
2.5.1 PERSYARATAN KOMPLEKSITAS
Seperti yang telah ditunjukkan dalam 2.3.4, QPLs menggunakan bahasa pemrograman universal yang klasik untuk menentukan urutan yang sebenarnya instruksi ¼ untuk kuantum komputer. Menurut kriteria di atas, pendekatan ini berguna jika komputer kuantum setidaknya sama seperti komputer klasik universal. Jika kita mempertimbangkan sebuah komputer kuantum dengan Toffoli gate (lihat 2.2.2.4) sebagai satu-satunya instruksi yang tersedia, maka setiap keadaan mesin harus bertransformasi. |ªi = |ii −! |g(i)i = |ªi with g : Bn ! Bn (3.1) Karena Toffoli gate adalah universal untuk reversibel logika boolean, maka setiap bijective Fungsi Boolean g dapat langsung diimplementasikan pada sebuah komputer kuantum.
Sebuah fungsi umum boolean f lebih Bn, dapat diimplementasikan dengan menggunakan pseudo-classical Operator F. F |i, 0i = |i, f(i)i with F†F = I (3.2) Jadi fungsi f dapat diimplementasikan pada komputer kuantum. Selain itu, C.H. Bennet telah menunjukkan bahwa reversible pelaksanaan f dapat dilakukan dalam waktu maksimal O (2) dan O (p n) di ruang kompleksitas (lihat 3.5.2). [8] Di sisi lain, sebagai quantum state n-qubit umum terdiri dari maksimal Eigenstates 2n dengan amplitudo tidak nol dan mengambil bentuk operator linear komputer klasik dapat mensimulasikan semua operator kesatuan dengan presisi , dan dengan pengkodean amplitudo kompleks seperti bilangan biner titik tetap. Namun, ini akan memerlukan waktu overhead eksponensial serta kompleksitas ruang. Karena sifat stokastik pengukuran kuantum, meniru komputer dan juga akan membutuhkan sumber yang benar secara acak (seperti misalnya probabilistik pada Mesin Turing).
2.5.2 Arsitektur Hybrid
Jadi QPLs dapat dianggap sebagai pemrograman meta-bahasa, seperti program yang tidak dimaksudkan untuk dijalankan pada komputer kuantum itu sendiri, tetapi pada (probabilistik) komputer klasik yang pada gilirannya akan mengontrol komputer kuantum.
Dalam istilah ilmu komputer klasik, Anda bisa menggambarkan pengaturan ini sebagai universal komputer dengan oracle kuantum. Gambar diatas mengilustrasikan arsitektur hybrid. Dari perspektif pengguna, program kuantum sama persis seperti program klasik lainnya, dalam arti bahwa dibutuhkan masukan klasik seperti parameter startup atau data interaktif, dan menghasilkan output klasik. Keadaan komputer pengendali (yaitu program counter, nilai-nilai variabel, namun juga pemetaan register kuantum) juga klasik dan dirujuk sebagai state program. Pada program ¼ yang sebelumnya, yaitu urutan instruksi kuantum yang terdiri dari gerbang dasar, pengukuran dan instruksi tampilan didefinisikan dengan baik ke komputer kuantum, sedangkan Output kembali dibatasi untuk nilai-nilai pengukuran biner. Komputer kuantum tidak memerlukan logika kontrol, komputasi dapat sepenuhnya dijelaskan oleh keadaan kuantum umum ª qubit nya, dan juga disebut sebagai state mesin.
2.5.3 QCL sebagai Bahasa Klasik
Karena model komputasi QPLs adalah berasal dari komputer klasik dengan oracle kuantum, QCL berisi semua fitur dari pemrograman universal yang klasik, seperti variabel, loop, dan subrutin bercabang bersyarat.
2.5.4 Structure of a QCL Program
Struktur sintaksis dari program QCL digambarkan oleh konteks bebas LALR (1) tata bahasa (lihat lampiran A) dengan pernyataan dan definisi sebagai symbol atas: qcl-input à { stmt | def }
2.5.4.1 Laporan
Laporan berisi dari perintah-perintah sederhana, prosedur-panggilan ke kompleks kontrol struktur dan dieksekusi ketika bertemu qcl> if random()>=0.5 { print "red"; } else { print "black"; } : red
2.5.4.2 Definisi
Definisi berisi (variabel atau konstanta-definition) atau blok kode (rutin-definition) ke simbol (identifier). qcl> int counter=5; qcl> int fac(int n) { if n<=0 {return 1;} else {return n*fac(n-1);} } Akibatnya, masing-masing simbol memiliki tipe saling terkait, dapat menjadi jenis data atau tipe rutin dan mendefinisikan apakah simbol dapat diakses .
2.5.4.3 Ekspresi
Banyak pernyataan dan rutinitas mengambil argumen dari tipe data tertentu. Ekspresi ini dapat terdiri dari literal, referensi variabel dan sub-ekspresi dikombinasikan oleh operator dan fungsi panggilan. qcl> print "5 out of 10:",fac(10)/fac(5)^2,"combinations." : 5 out of 10: 252 combinations.
2.5.5 Tipe Data dan Variabel
Tipe data klasik QCL adalah jenis aritmatika int, nyata dan kompleks dan jenis umum boolean dan string.
2.5.6 Konstanta
Nilai-nilai yang sering digunakan dapat didefinisikan sebagai konstanta simbolis. Sintaks deklarasi konstan yaitu const-def à const identifier = expr ; Definisi pi dalam file,misalnya const pi=3.141592653589793238462643383279502884197;
2.5.7 Variabel
Definisi variabel dalam QCL sama dengan C adalah: var-def à type identifier [ = expr ] ; Jika tidak ada nilai awal yang diberikan, masing-masing variabel baru.diinisialisasi dengan nol, salah atau " " . Nilai dari variabel dapat diubah, input pengguna (lihat 3.2.4.3) dan kuantum pengukuran (lihat 3.4.1):
qcl> complex z; // declare complex variable z qcl> print z; // z was initialized with 0 : (0.000000,0.000000) qcl> z=(0,1); // setting z to i qcl> print z; : (0.000000,1.000000) qcl> z=exp(z*pi); // assignment to z may contain z qcl> print z; : (-1.000000,0.000000) qcl> input z; // ask for user input ? complex z [(Re,Im)] ? (0.8,0.6) qcl> print z; : (0.800000,0.600000)
2.5.8 Operator
Tabel 3.2 menunjukkan semua operator QCL, dimulai dari tinggi ke rendah. Semua operator biner asosiatif yang tersisa, demikian ± b ± c = (a ± b) ± c. eksplisit Pengelompokan dapat dicapai dengan menggunakan tanda kurung.
Operator aritmatika umumnya bekerja pada semua tipe data aritmatika dan kembali ke tipe yang paling umum (operator overloading), misalnya
qcl> print 2+2; // evaluates to int : 4 qcl> print 2+2.0; // evaluates to real : 4.000000 qcl> print 2+(2,0); // evaluates to complex : (4.000000,0.000000)
Untuk memungkinkan aritmatika integer ada dua pengecualian untuk menghindari typecasts, yaitu:
- Operator divisi / melakukan pembagian integer jika kedua argumen integer.
- Operator ^ untuk basis bilangan bulat hanya didefinisikan untuk non-negatif, eksponen integer. Untuk eksponen nyata.
2.5.9 Fungsi
QCL juga kemungkinan berisi panggilan atau ditetapkan pada fungsi pengguna. Tabel 3.3 menunjukkan semua fungsi aritmatika unary
Selain di atas, QCL juga mengandung fungsi n-ary seperti minimum atau FPB, fungsi konversi dan fungsi semu random () (tabel 3.4) Seperti yang sebelumnya tidak ada fungsi dalam arti matematis, hal itu mungkin tidak digunakan dalam definisi fungsi pengguna dan operator kuantum.
2.5.10 Penugasan
Nilai dari variabel klasik dapat diatur oleh operator tugas =. Nilai kanan harus dari jenis variable yang sama.
berbeda dengan operator aritmatika dan fungsi built-in, tidak ada typecasting implisit yang dilakukan. qcl> complex z; qcl> z=pi; // no typecast ! type mismatch: invalid assignment qcl> z=conj(pi); // implicit typecast
2.5.11 Panggilan
Panggilan prosedur memiliki sintaks: stmt à identifier ( [ expr { , expr }] ) ; Tidak ada typecasting yang dilakukan untuk jenis argumen klasik. Karena mengakibatkan program awal prosedur panggilan tidak terjadi pada definisi fungsi atau operator.
2.5.12 Masukan
Perintah masukan untuk meminta input pengguna dan memberikan nilai kepada variable identifier. Opsional string expr dapat cepat diberikan sebagai pengganti dari prompt standar yang menunjukkan jenis dan nama variabel. qcl> real n; qcl> input "Enter Number of iterations:",n; ? Enter Number of iterations: 1000
2.5.13 Output
Setiap output diawali oleh titik dua dan diakhiri dengan baris baru. qcl> int i=3; real x=pi; complex z=(0,1); boolean b; qcl> print i,x,z,b; : 3 3.141593 (0.000000,1.000000) false
2.5.14 Aliran kontrol
Semua pernyataan aliran kontrol beroperasi pada blok kode. Blok adalah daftar laporan yang diapit oleh tanda kurung: block à { stmt { stmt } } Blok hanya dapat berisi pernyataan yang dieksekusi, dan tidak ada definisi. Tidak seperti C, blok bukanlah pernyataan majemuk dan selalu menjadi bagian dari struktur pengendalian. Untuk menghindari kesamaan, wajib menggunakan tanda kurung, bahkan sekalipun untuk satu perintah.
2.5.15 Percabangan Bersyarat
Jika pernyataan memungkinkan untuk menjalankan kondisional blok, itu semua tergantung pada nilai dari ekspresi Boolean itu sendiri stmt à if expr block [ else block ] Jika expr bernilai true, dan if dijalankan. Jika expr mengevaluasi ke false, dan block yang lain dijalankan, maka itu semua dapat di terapkan.
2.5.16 Menghitung putaran
Putaran mengambil identifier counter tipe integer yang bertambah dari expr ke expr. Putaran dieksekusi untuk setiap nilai identifier. Stmt <- for identifier = expr from to expr to [ step expr step ] block Di dalam badan program, counter digunakan sebagai konstanta. qcl> int i; qcl> for i=10 to 2 step -2 { print i^2; } : 100 : 64 : 36 : 16 : 4 qcl> for i=1 to 10 { i=i^2; } // i is constant in body ! unknown symbol: Unknown variable i Ketika putaran selesai, identifier telah di atur untuk expr to.
2.5.17 Kondisi putaran
QCL mendukung dua jenis loop bersyarat yaitu: Stmt <- while expr block <- block until expr ; Beberapa putaran iterasi agar kondisi expr terpenuhi. Kapan expr mengevaluasi ke false, putaran berakhir. Putaran dijalankan sampai pada setidaknya sekali dan iterasi sampai kondisi expr terpenuhi.
2.5.18 Subrutin Klasik
Ditentukan fungsi pengguna, mungkin dari setiap tipe klasik dan dapat mengambil berapa saja jumlah parameter klasik. Nilai fungsi tersebut diteruskan kembali ke perintah sebelumnya. Variabel lokal dapat didefinisikan di bagian fungsi atas statement int Fibonacci(int n) { // calculate the n-th int i; // Fibonacci number int f; // by iteration for i = 1 to n { f = 2*f+i; } return f; }
QCL berfungsi untuk memiliki matematika semantik, sehingga nilai nya harus deterministik dan eksekusi nya tidak boleh mengubah state program. qcl> int randint(int n) { return floor(n*random()); } ! in function randint: illegal scope: function random is not allowed in this scope qcl> int foo=4711; qcl> int bar(int n) { foo=foo+n; return foo; } ! in function bar: unknown symbol: Unknown local variable foo Sebuah fungsi dapat memanggil fungsi-fungsi lainnya dalam bagian program. Perintah rekursif juga diperbolehkan. int fac(int n) { // calculate n! if n<2 { // by recursion return 1; } else { return n*fac(n-1); } }
2.5.19 Prosedur
Prosedur adalah tipe yang paling umum dan rutin digunakan untuk mengimplementasikan struktur kontrol klasik algoritma kuantum yang umumnya melibatkan loop evaluasi, pilihan operator yang diterapkan, penafsiran pengukuran dan elemen probabilistik klasik. Dengan pengecualian dari deklarasi rutin, prosedur memungkinkan operasi yang sama dalam lingkup global (misalnya pada prompt shell) yang memungkinkan perubahan apa saja untuk kedua program itu dan pada mesin state. operasi eksklusif untuk prosedur yaitu:
- Akses ke variabel global
- (Pseudo) nomor acak dengan menggunakan pseudo-fungsi acak ()
- Operasi non-kesatuan pada mesin state dengan menggunakan reset dan mengukur perintah
- Masukkan pengguna dengan menggunakan perintah input
Prosedur dapat mengambil sejumlah argumen klasik atau kuantum dan mungkin memanggil semua jenis subrutin.
2.6 Quantum Memory Manajemen
Memori komputer kuantum biasanya merupakan kombinasi dari 2-state subsistem, disebut bit kuantum sebagai (qubit). Seperti yang ditunjukkan dalam 2.2.1.3 "isi memori" adalah gabungan state | ª i semua qubit. Kondisi ini disebut sebagai (quantum) state mesin yang bertentangan dengan state program yang merupakan algoritma pengendalian (klasik) keadaan saat ini, (misalnya isi variabel, eksekusi stack, dll) dijelaskan oleh program QCL. Mesin state | ª i dari komputer kuantum n qubit adalah vektor dalam Hilbert ruang H = C2N, namun karena sifat destruktif pengukuran (lihat 1.3.2.3) - | ª tidak dapat langsung diamati dan akibatnya tidak dapat diakses dalam QCL. QCL berisi libqc perpustakaan yang dapat mensimulasikan kuantum komputer dengan jumlah sesuai qubit. Hal ini juga menyediakan sebuah tampilan untuk mengakses simulasi mesin state melalui perintah load, save dan menghapus.
2.6.1 Quantum Register
QCL menggunakan konsep register kuantum (lihat 2.2.1.5) sebagai tampilan antara state mesin dan komputer klasik. kuantum A register pointer ke urutan (saling berbeda) qubit, sementara variabel klasik masih mengacu pada subsistem kuantum. Semua operasi pada state mesin (kecuali untuk perintah reset, lihat 3.4.1) mengambil register kuantum sebagai operan. n qubit kuantum komputer memungkinkan untuk n! (n-m)! m qubit register yang berbeda s 2 Zmn , Setiap kesatuan atau operasi pengukuran am qubit, dapat mengakibatkan n! (n-m)! berbeda operasi pada state mesin. Ini mengharuskan semua operasi komputer kuantum dapat diterapkan pada qubit apa saja dan membutuhkan arsitektur fisik untuk memungkinkan pengukuran qubit tunggal.
2.6.2 The Quantum Heap
Di QCL, hubungan antara register dan qubit ditangani secara transparan oleh alokasi dan dealokasi qubit dari tumpukan kuantum, yang memungkinkan menggunakan variabel kuantum lokal. Semua kosong (yakni tidak terisi) memori kuantum harus kosong.
2.6.3 Alokasi Daftar
Ketika sebuah variabel kuantum didefinisikan, maka register Quantum dialokasikan. Posisi qubit untuk masing-masing register dapat diperiksa menggunakan print statement $ qcl -b10 # start qcl-interpreter with 10 qubits qcl> qureg a[4]; // allocate a 4-qubit register qcl> qureg b[3]; // allocate another 3-qubit register qcl> print a,b; // show actual qubit mappings : |......3210> |...210....> qcl> qureg c[5]; // try to allocate another 5 qubits ! memory error: not enough quantum memory Di QCL, tumpukan kuantum diatur sebagai stack: qubit didorong pada alokasi dan dealokasi poped. Ketika ruang lingkup variabel yang tersisa maka sebuah daftar kuantum akan deallocated. qcl> qureg a[3]; // allocate 3 qubits qcl> procedure foo() { qureg b[2]; print a,b; } qcl> foo(); // temp. register b gets allocated : |.......210> |.....10...> qcl> qureg c[3]; // allocate another 3 qubits qcl> print a,c; // qubits from b have been reclaimed : |.......210> |....210...>
2.6.4 Scratch Space Management
Untuk menghindari tumpukan kuantum, sebelum itu register harus kosong “deallocated”. Fungsi Quantum (lihat 2.2.2.5) memungkinkan deklarasi variabel kuantum lokal sebagai state awal (lihat 3.3.1.5), dalam hal ini "Uncomputing" dari register sementara secara transparan menggunakan prosedur berikut seperti disarankan oleh Bennet: Misalkan F fungsi kuantum dengan argumen x (tipe quconst, lihat 3.3.2.2), dan fungsi y (ketik quvoid, lihat 3.3.2.3) dan fungsi s (tipe quscratch, lihat 3.3.2.4) F(x, y, s) : |iix|0iy|0is ! |iix|f(i)iy|j(i)is
Selama penerapan F, fungsi s diisi dengan junk sementara bit j (i). QCL mengalokasikan t register tambahan dan menerjemahkan F menjadi F0 Operator yang didefinisikan sebagai: F0(x, y, s, t) = F†(x, t, s) Fanout(t, y) F(x, t, s)
2.6.5 Simulasi
Penafsir QCL dapat mensimulasikan komputer kuantum dengan nomor sesuai qubit. Menurut arsitektur hybrid seperti yang diperkenalkan pada 3.1.3, simulasi numerik ditangani oleh perpustakaan (libqc) untuk memisahkan state program klasik dari state mesin kuantum. QCL menyediakan perintah khusus untuk memeriksa keadaan mesin simulasi.
2.6.6 Quantum Variabel
Register Quantum terikat dengan nama simbolis yang disebut sebagai kuantum variabel.
2.6.7 General Register
Sebuah Daftar kuantum umum dengan n = expr qubit dapat dideklarasikan dengan var-def à qureg identifier [expr];
2.6.8 Quantum Konstanta
Register dapat dinyatakan konstan, dengan menggunakan quconst. A konstan kuantum harus invarian ke semua operator yang diterapkan. Definisi 10 (invarian dari Register) Sebuah daftar kuantum c dianggap invarian untuk operator fungsi U (s, c) jika U memenuhi kondisi U: | i, ji = | iis | jic! (Uj | iis) | jic
2.6.9 Empty Register
Jika argumen v ke operator dinyatakan quvoid, register kuantum diharapkan menjadi kosong ketika operator disebut normal, atau menjadi uncomputed jika operator disebut terbalik (lihat 3.4.3.2). Jadi, tergantung pada adjungation dari operator, state mesin | ª i harus sesuai U (v, ...): | ª i = | 0iv | AI! | ª 0i atau U † (v, ...): | ª i! | 0iv | Ã0i
2.6.10 Register Scratch
Sebagai argumen untuk operator, register jenis quscratch dianggap menjadi register awal eksplisit yang harus kosong ketika operator disebut dan harus mendapatkan uncomputed sebelum operator berakhir, sehingga Operator dan mesin state harus memenuhi kondisi U (s, ...): | ª i = | 0is | AI! | 0is | Ã0i = | ª 0i
3 BAB III
3.1 PEMBAHASAN SOFTWARE
software yang digunakan dalam memecahkan solusi quantum adalah QCL. Dimana QCL merupakan bahasa pemrograman untuk komputer kuantum. QCL adalah bahasa pemrograman tingkat tinggi, yaitu arsitektur bahasa pemrograman independen untuk komputer kuantum, dengan sintaks yang berasal dari bahasa prosedural klasik seperti C atau Pascal. Hal ini memungkinkan untuk implementasi lengkap dan simulasi algoritma kuantum (termasuk komponen klasik) dalam satu formalisme konsisten. Berikut ini adalah langkah-langkah dalam instalasi QCL : 1.Download QCL programming language http://tph.tuwien.ac.at/~oemer/tgz/qcl-0.5.1-bin.tgz
Gambar 3.1
2.Ektrak file dengan perintar tar -zxf qcl-0.5.1-bin.tgz kemudian pindah ke dierktori hasil ekstrak dengan perintah cd qcl-0.5.1-bin
3.Setelah pindah ke dalam folder qcl ketikan perintah ./qcl-static dan akan muncul command seperti gambar di bawah.
Gambar 3.2
4.Selesai
3.2 Hybrid Architecture
Meskipun banyak konsep umum dengan ilmu komputer klasik, komputasi kuantum masih luas dianggap sebagai suatu disiplin khusus dalam bidang luas teori fisika. Salah satu alasan untuk adopsi QC oleh komunitas ilmu komputer adalah berbagai formalisme yang membingungkan (notasi Dirac, matriks, gerbang, operator, dll), tidak ada yang mempunyai kesamaan dengan bahasa pemrograman klasik, seperti C atau Pascal, serta agak ‘‘fisik’’ terminologi di sebagian besar literatur yang ada.
Jadi bahasa pemrograman kuantum dapat dianggap sebagai pemrograman meta-bahasa, karena program ini tidak dimaksudkan untuk berjalan pada komputer kuantum itu sendiri, tetapi pada (probabilistic) komputer klasik yang pada gilirannya mengontrol komputer kuantum. Dalam istilah ilmu komputer klasik, Anda bisa menggambarkan pengaturan ini sebagai komputer yang universal dengan oracle kuantum. Gambar dibawah ini menggambarkan arsitektur hybrid.
Gambar 3.3
pemrograman kuantum berperilaku persis seperti program klasik lainnya, dalam arti bahwa dibutuhkan masukan klasik seperti parameter startup atau data interaktif, dan menghasilkan output klasik. Keadaan komputer pengendali (yaitu program counter, nilai-nilai variabel, tetapi juga pemetaan register kuantum) juga sangat klasik dan disebut sebagai program state.
urutan instruksi kuantum yang terdiri dari gerbang dasar, pengukuran dan inisialisasi-instruksi dilewatkan melalui antarmuka yang didefinisikan dengan baik ke komputer kuantum, sedangkan output kembali dari dibatasi untuk nilai-nilai pengukuran biner. Komputer kuantum tidak memerlukan control logic, itu negara komputasi bisa untuk itu sepenuhnya dijelaskan oleh umum kuantum state Ψ qubit nya, juga disebut sebagai machine state.
3.3 Bahasa Pemrograman Kuantum sebagai Bahasa Pemrograman Klasik
Karena model komputasi kuantum adalah bahwa dari komputer klasik dengan oracle kuantum, QCL berisi semua fitur dari bahasa pemrograman universal yang klasik, seperti variabel,loop,dan subrutin bersyarat percabangan.
3.4 Stuktur dari Pemrograman Kuantum
struktur dari pemrograman kuantum adalah contex free LALR(1) grammar dengan statement dan definisi top simbol :
qcl-input← {stmt|def}
3.4.1 Statement
statement range dari perintah sederhana dari pemanggilan prosedur sampai dengan struktur kontrol yang kompleks dieksekusi ketika perintah tersebut disatukan.
qcl> if random()>=0.5 { print "red"; } else { print "black"; } : red
3.4.2 Definisi
Definisi tidak dijalankan tetapi mengikat nilai (variabel atau konstanta-definition) atau blok kode (rutin-definition) ke simbol (identifier).
qcl> int counter=5; qcl> int fac(int n) { if n<=0 {return 1;} else {return n*fac(n-1);} }
masing-masing simbol memiliki tipe yang terkait, yang dapat menjadi tipe data atau tipe rutin dan mendefinisikan apakah simbol diakses oleh referensi atau panggilan.
3.4.3 Ekspresi
Banyak statement dan rutin mengambil argumen dari tipe data tertentu. Ekspresi ini dapat terdiri dari literal, referensi variabel dan sub-ekspresi gabungan oleh operator dan fungsi panggilan.
qcl> print "5 out of 10:",fac(10)/fac(5)^2,"combinations." : 5 out of 10: 252 combinations.
3.4.4 Tipe Data dan Variabel
Tipe data klasik dari kuantum programming adalah aritmatika seperti int, real dan standart kompleks boolean dan string.
Gambar 3.4
3.4.5 Konstanta
Nilai-nilai yang sering digunakan dapat didefinisikan sebagai konstanta simbolis. Sintaks dari deklarasi konstanya adalah :
const-def←const identifier = expr;
standart definisi dari nilai pi adalah :
const pi=3.141592653589793238462643383279502884197;
3.4.6 Variabel
Definisi dari variabel dalam kuantum programing dianalogikan sama dengan bahasa C :
var-def←type identifier[=expr];
Jika tidak ada nilai awal yang diberikan, variabel baru diinisialisasi dengan nol, false atau "", masing-masing. Nilai dari variabel dapat diubah oleh user input, dan pengukuran kuantumnya.
Gambar 3.5
3.4.7 Ekspresi
Tabel dibawah menunjukkan semua operator QCL memerintahkan dari tinggi ke rendah didahulukan. 1 Semua operator biner asosiatif yang tersisa, sehingga a◦b◦c= (a◦b)◦c. Pengelompokan eksplisit dapat dicapai dengan menggunakan tanda kurung.
Gambar 3.6
Untuk memungkinkan untuk aritmatika integer ada dua pengecualian untuk menghindari jenis cast:
a. Operator divisi / melakukan pembagian integer jika kedua argumen integer
b. Kekuatan Operator ^ untuk basis bilangan bulat hanya didefinisikan untuk non-negatif, eksponen integer. Untuk eksponen nyata, basis harus non-negatif,
3.4.8 Fungsi
Ekspresi QCL juga mungkin berisi panggilan ke built-in atau ditetapkan pengguna fungsi. Tabel dibawah menunjukkan semua fungsi aritmatika unary built-in.
Gambar 3.7
Selain di atas, kuantum programming juga mengandung n-ary fungsi seperti minimum atau gcd, fungsi konversi dan fungsi semu acak (). Seperti yang terakhir ini tidak ada fungsi dalam arti matematis, hal itu mungkin tidak digunakan dalam definisi user-fungsi dan operator kuantum.
3.5 STATEMENT SEDERHANA
3.5.1 Penugasan
Nilai dari variabel klasik dapat diatur oleh operator penugasan =. Nilai kanan harus dari jenis yang sama seperti variabel.
Gambar 3.8
operator aritmatika dan fungsi built-in, tidak ada typecasting implisit yang dapat dilakukan.
qcl> complex z; qcl> z=pi; // no typecast ! type mismatch: invalid assignment qcl> z=conj(pi); // implicit typecast
3.5.2 Call
sintaks dari prosedur call :
stmt←identifier([expr{,expr}]) ;
Seperti tugas, tidak ada typecasting dilakukan untuk jenis argumen klasik. Karena potensi efek samping pada statement program, prosedur-call tidak mungkin terjadi dalam definisi fungsi atau operator.
3.5.3 Input
Perintah masukan untuk meminta input pengguna dan memberikan nilai ke variabel identifier. Opsional string expr cepat dapat diberikan sebagai pengganti prompt standar yang menunjukkan jenis dan nama variabel.
qcl> real n; qcl> input "Enter Number of iterations:",n; ? Enter Number of iterations: 1000
Output
Perintah cetak mengambil daftar dipisahkan koma dari ekspresi dan mencetak mereka ke konsol. Setiap output didahului oleh titik dua dan diakhiri dengan baris baru.
qcl> int i=3; real x=pi; complex z=(0,1); boolean b; qcl> print i,x,z,b; : 3 3.141593 (0.000000,1.000000) false
3.6 Manajemen Memori Kuantum
3.6.1 Machine State dan Program State
Memori komputer kuantum biasanya merupakan kombinasi dari 2-state subsistem, disebut bit kuantum sebagai (qubit). Seperti yang ditunjukkan dalam 2.2.1.3 "isi memori" adalah gabungan negara | Ψ> semua qubit. Kondisi ini disebut sebagai (quantum) mesin negara yang bertentangan dengan program negara yang merupakan keadaan saat ini mengendalikan (klasik) algoritma (misalnya isi dari variabel, eksekusi stack, dll) dijelaskan oleh program QCL. Keadaan mesin | Ψ> dari n qubit komputer kuantum adalah vektor di ruang Hilbert H = C2N, namun - karena sifat merusak pengukurannya - | Ψ> tidak dapat langsung diamati dan akibatnya tidak dapat diakses dari dalam QCL. Karena kurangnya saat komputer kuantum real-hidup, QCL juru berisi libqc perpustakaan persaingan yang dapat mensimulasikan sebuah komputer kuantum dengan jumlah sewenang-wenang qubit. Hal ini juga menyediakan sebuah antarmuka untuk mengakses keadaan mesin simulasi melalui beban, menyimpan dan membuang perintah
3.6.2 Kuantum Register
QCL menggunakan konsep register kuantum sebagai antarmuka antara keadaan mesin dan komputer klasik pengendali. Sebuah daftar kuantum adalah pointer ke urutan (saling berbeda) qubit dan dengan demikian, sementara mengacu pada subsistem kuantum, masih merupakan variabel klasik. Semua operasi pada keadaan mesin (kecuali untuk perintah reset,) mengambil register kuantum sebagai operan. Karena sebuah komputer kuantum n qubit memungkinkan untuk m qubit register yang berbeda s ∈ Z mn, setiap operasi kesatuan atau pengukuran pada pagi qubit mendaftar, dapat mengakibatkan
operasi yang berbeda pada keadaan mesin: ini mengharuskan semua operasi kesatuan dasar dari komputer kuantum dapat diterapkan pada qubit sewenang-wenang dan membutuhkan arsitektur fisik untuk memungkinkan pengukuran qubit tunggal.
3.6.2.1 Subrutin
Selain jenis subroutine prosedur klasik dan fungsi, QCL menyediakan dua jenis rutin kuantum untuk operator kesatuan umum (operator) dan operator pseudo-klasik (qufunct). QCL memungkinkan untuk membalikkan operator dan dapat melakukan manajemen awal-ruang untuk fungsi kuantum, sehingga memungkinkan efek samping pada program negara klasik serta pada keadaan mesin kuantum harus benar-benar ditentukan.
Gambar 3.9
Jenis rutin 4 QCL membentuk hierarki panggilan, yang berarti bahwa rutinitas dapat memanggil subrutin hanya dari tingkat yang lebih rendah atau sama. Semantik matematika operator QCL dan fungsi mengharuskan setiap panggilan yang direproduksi. Ini berarti, bahwa tidak hanya program negara tidak boleh diubah oleh rutinitas, tetapi juga bahwa eksekusi mereka mungkin sekali tidak tergantung pada keadaan program global yang meliputi variabel global, pilihan dan keadaan internal nomor acak generator.
3.6.2.2 General Operator
Operator tipe rutin digunakan untuk operator kesatuan umum. Sesuai dengan gagasan matematika dari operator, panggilan dengan parameter yang sama harus menghasilkan persis transformasi yang sama, sehingga tidak ada referensi variabel global, unsur-unsur acak atau ketergantungan pada masukan yang diperbolehkan. Karena operator tipe dibatasi untuk transformasi reversibel dari keadaan mesin, reset dan mengukur perintah juga dilarang
3.6.2.3 Design Algoritma Kuantum
komputer kuantum dan komputer klasik probabilistik setara komputasi, tapi untuk tugas-tugas tertentu, algoritma kuantum dapat memberikan solusi yang lebih efisien daripada implementasi klasik. Untuk mencapai setiap speedup atas algoritma klasik, perlu untuk mengambil keuntungan dari fitur unik dari komputasi kuantum yaitu
• Superpositioning • Quantum Paralelisme • Interferensi
Sementara Superpositioning dan paralelisme kuantum memungkinkan kita untuk melakukan sejumlah besar perhitungan secara eksponensial klasik secara paralel, satu-satunya cara untuk membacakan hasil apapun adalah dengan melakukan pengukuran dimana semua kecuali satu dari eigenstates superpositioned bisa dibuang. Karena tidak ada bedanya jika jalur komputasi ditentukan selama perhitungan (seperti dengan probabilistik TM) atau-posteriori (berdasarkan pengukuran kuantum), penggunaan komputer kuantum tidak akan memberikan keuntungan apapun atas komputer klasik probabilistik
Jadi sementara jalur komputasi pada TM probabilistik independen, gangguan memungkinkan perhitungan pada negara superpositioned untuk berinteraksi dan interaksi ini yang memungkinkan sebuah komputer kuantum untuk memecahkan masalah-masalah tertentu lebih efisien daripada komputer klasik. Prinsip desain utama untuk algoritma kuantum apapun untuk itu adalah dengan menggunakan interferensi untuk meningkatkan kemungkinan "menarik" eigenstates ketika mencoba untuk mengurangi kemungkinan "membosankan" negara, dalam rangka untuk meningkatkan kemungkinan bahwa pengukuran akan memilih salah satu dari mantan.
4 BAB IV
4.1 STUDI KASUS
Bab ini memperkenalkan dua "aplikasi pembunuh" kuantum - Grover’s fast quantum search dan Shor’s factorization algorithm - yang keduanya memecahkan masalah tradisional dalam ilmu komputer dan memberikan percepatan substansial yang dikenal solusi klasik.
4.1.1 Grover’s Database Search
Banyak masalah dalam ilmu komputer klasik dapat dirumuskan sebagai pencarian daftar untuk elemen yang unik yang sesuai dengan beberapa kondisi yang telah ditetapkan. jika pengetahuan tambahan tentang pencarian kondisi C tersedia, yang terbaik algoritma klasik adalah pencarian brute-force yaitu elemen yang berurutan diuji terhadap C dan segera setelah unsur sesuai kondisi, algoritma berakhir. Untuk daftar unsur N, ini membutuhkan rata-rata perbandingan N/2.
4.1.1.1 Memformulasi sebuah Query
Cara yang paling mudah, meskipun bukan yang paling nyaman untuk algoritma, untuk menerapkan kondisi pencarian sebagai fungsi kuantum
Gambar 4.1
karena hal ini memungkinkan kita untuk merumuskan masalah dalam alam klasik logika boolean.
Algoritma Grover kemudian dapat digunakan untuk memecahkan persamaan C (x) = 1 sementara selain fakta bahwa solusi ada dan bahwa itu adalah unik, tidak ada tambahan pengetahuan tentang C (x) diperlukan. Biasanya, pelaksanaan permintaan akan cukup rumit karena tidak untuk memungkinkan solusi aljabar yang efisien, tetapi karena struktur dalam C (x) tidak masalah untuk algoritma, kita dapat dengan mudah menerapkan query uji dengan solusi n sebagai
qufunct query(qureg x,quvoid f,int n) { int i;
for i=0 to #x-1 { // x -> NOT (x XOR n) if not bit(n,i) { Not(x[i]);
} }
CNot(f,x);
// flip f if x=1111.. for i=0 to #x-1 { // x <- NOT (x XOR n) if not bit(n,i) { !Not(x[i]);
} } }
Sebuah aplikasi yang lebih realistis akan mencari kunci enkripsi dalam serangan dikenal-plaintext. Dengan p menjadi plaintext diketahui ciphertext c, implementasi QCL bisa terlihat seperti ini:
qufunct encrypt(int p,quconst key,quvoid c) { ... }
qufunct query(int c,int p,quconst key,quvoid f) { int i; quscratch s[blocklength];
encrypt(p,key,s);
for i=0 to #s-1 { // s -> NOT (s XOR p) if not bit(p,i) { Not(x[i]);
} }
CNot(f,x); // flip f if s=1111.. }
Perhatikan bahwa, tidak seperti contoh di atas, fungsi query ini menggunakan awal mendaftar lokal, sehingga tidak perlu secara eksplisit uncompute s, karena hal ini akan diasuh oleh manajemen ruang awal intern QCL ini.
4.1.2 Algorithm
4.1.2.1 Setting up the Search Space
Ruang solusi dari kondisi bit permintaan C adalah Bn. Pada kuantum komputer, ruang pencarian ini dapat diimplementasikan sebagai superposisi dari semua eigenstates dari register n qubit, yaitu:
Gambar 4.2
kami telah menunjukkan bagaimana negara tersebut dapat dibuat oleh n-qubit Hadamard transform
Gambar 4.3
4.1.2.2 The Main Loop Loop utama dari algoritma terdiri dari dua langkah
1. Lakukan pergeseran fasa bersyarat yang berputar fase semua vektor eigen yang sesuai dengan kondisi C oleh ¼ radian.
Gambar 4.4
2. Apply a diffusion operator
Gambar 4.5
Karena hanya satu vektor eigen | i0i seharusnya cocok dengan kondisi pencarian C, pergeseran fasa bersyarat akan mengubah bahkan superposisi awal menjadi
Gambar 4.6
Pengaruh operator difusi pada vektor eigen sewenang-wenang | ii adalah
Gambar 4.7
jadi satu iterasi pada keadaan bentuk
Gambar 4.8
adalah sebesar
Gambar 4.9
4.1.2.3 Jumlah dari Iterations
Jika di atas lingkaran Operator DQ berulang kali diterapkan pada awal superposisi
Gambar 4.10
maka bagian-bagian yang dihasilkan masih dalam bentuk | ª (k, l) i dan amplitudo kompleks k dan l dijelaskan oleh sistem berikut recursions:
Gambar 4.11
di atas dapat ditulis dalam bentuk tertutup.
Gambar 4.12
4.1.3 Implementasi
4.1.3.1 The Query Operator
Jika kita memilih untuk merumuskan query sebagai fungsi kuantum dengan qubit flag f untuk memungkinkan implementasi ketat klasik, seperti yang disarankan dalam 4.1.1, maka operator Q dapat dibangun sebagai
Gambar 4.13
dengan menggunakan fase bersyarat gerbang V (Á) dan mempertimbangkan flag mendaftar f ruang awal sementara.
4.1.3.2 The Diffusion Operator
Menggunakan Hadamard Transform H (lihat 3.4.4.3) dan rotasi fase bersyarat R: | ii = - (-1) ± I0 | ii, operator difusi
Gambar 4.14
dapat juga ditulis sebagai D = HRH sejak
Gambar 4.15
Menggunakan operator yang bukan fase bersyarat gerbang V (Á) kita dapat menerapkan operator difusi sebagai
operator diffuse(qureg q) { Mix(q);
// Hadamard Transform Not(q);
// Invert q CPhase(pi,q);
// Rotate if q=1111.. !Not(q);
// undo inversion !Mix(q);
// undo Hadamard Transform }
Bahkan, operator di atas mengimplementasikan-D, tapi karena fase keseluruhan membuat perbedaan fisik, ini tidak masalah.
4.1.3.3 The Procedure grover
Dengan menggunakan di atas, kita sekarang dapat memberikan implementasi dari QCL lengkap algoritma:
procedure grover(int n) { int l=floor(log(n,2))+1;
// no. of qubits int m=ceil(pi/8*sqrt(2^l));
// no. of iterations int x;
int i;
qureg q[l];
qureg f[1];
{ reset;
Mix(q);
// prepare superposition for i= 1 to m { // main loop query(q,f,n);
// calculate C(q) CPhase(pi,f);
// negate |n> !query(q,f,n);
// undo C(q) diffuse(q);
// diffusion operator } measure q,x;
// measurement print "measured",x;
} until x==n;
}
Argumen Prosedur n adalah jumlah yang akan ditemukan; ukuran register kuantum serta jumlah iterasi ditetapkan sesuai:
qcl> grover(500);
: 9 qubits, using 9 iterations
: measured 500
qcl> grover(123);
: 7 qubits, using 5 iterations
: measured 74
: measured 123
qcl> grover(1234);
: 11 qubits, using 18 iterations
: measured 1234
4.2 Shor’s Algorithm for Quantum Factorization
4.2.1 Motivasi
Berbeda dengan mencari dan mengalikan bilangan prima besar, tidak efisien algoritma klasik untuk faktorisasi sejumlah besar dikenal. sebuah algoritma disebut efisien jika waktu pelaksanaannya yaitu jumlah SD operasi ini assymtotically polinomial dalam panjang input diukur dalam bit. Yang paling terkenal (atau setidaknya dipublikasikan) algoritma klasik (saringan kuadrat) membutuhkan O ³exp ³( 64 )1/3N 1/3(ln N )2/3 operasi untuk anjak biner jumlah N bit [12] yaitu skala eksponensial dengan ukuran input. Oleh karena itu, perkalian bilangan prima besar adalah fungsi satu arah yaitu fungsi yang dapat dengan mudah dievaluasi dalam satu arah, sementara yang inversi secara praktis tidak mungkin. Fungsi satu arah memainkan roll besar dalam kriptografi dan sangat penting untuk kunci kripto-sistem publik di mana kunci untuk encoding publik dan hanya kunci untuk decoding tetap rahasia. Pada tahun 1978, Rivest, Shamir dan Adleman mengembangkan algoritma kriptografi didasarkan pada satu arah karakter mengalikan dua besar (biasanya di atas 100 digit desimal) bilangan prima. Metode RSA (dinamai inisial penemu mereka) menjadi sistem kunci publik yang paling populer dan diimplementasikan dalam berbagai program komunikasi. Meskipun umumnya percaya (meskipun tidak secara resmi terbukti) yang efisien faktorisasi prima pada komputer klasik adalah mustahil, efisien algoritma untuk komputer kuantum telah diusulkan pada tahun 1994 oleh PW Shor
4.2.2 The Algorithm
Bagian ini menjelaskan algoritma Shor dari sudut pandang fungsional yang berarti bahwa hal itu tidak berhubungan dengan implementasi untuk hardware tertentu arsitektur. Implementasi yang rinci untuk gerbang Cirac-Zoller.
4.2.2.1 Modular Exponentiation
Biarkan N = n1n2 dengan terbesar umum gcd pembagi (n1, n2) = 1 menjadi nomor yang akan difaktorkan, XA dipilih secara acak jumlah relatif prima terhadap N (yaitu gcd (x, N) = 1) dan expn fungsi eksponensial modular dengan periode r:
Gambar 4.16
)
Periode r adalah urutan x modN. Jika r bahkan, kita dapat mendefinisikan y = xr / 2, yang memenuhi kondisi y2 ’1 modN dan karena itu adalah solusi dari salah satu sistem berikut persamaan:
Gambar 4.17
Kedua sistem pertama memiliki solusi sepele y1 = 1 dan y2 = -1 yang tidak berbeda dari orang-orang dari kuadrat persamaan y2 = 1 di Z atau Galois bidang GF (p) (yakni Zp dengan prima p). Kedua sistem terakhir memiliki trivial solusi y3 = a, y4 =-a, sebagaimana didalilkan oleh sisa Cina teorema yang menyatakan bahwa sistem k congruences simultan (yaitu sistem persamaan dari bentuk y ’ai modmi) dengan modulus coprime m1,. . . , mk (yaitu FPB (mi, mj) = 1 untuk semua i 6 = j) memiliki solusi unik y dengan 0 • x < m1m2. . . mk.
4.2.2.2 Mencari sebuah Factor
Jika r bahkan dan y = ± dengan 6 = 1 dan 6 = N - 1, maka (a + 1) atau (a - 1) harus memiliki pembagi umum dengan N karena a2 ’1 modN yang berarti a2 itu = cN + 1 dengan c 2 N dan karena itu a2 - 1 = (a + 1) (a - 1) = cN. Faktor dari N kemudian dapat ditemukan dengan menggunakan algoritma Euclid untuk menentukan FPB (N, a + 1) dan FPB (N, a - 1) yang didefinisikan sebagai
Gambar 4.18
Hal ini dapat ditunjukkan bahwa x acak sesuai dengan kondisi yang disebutkan di atas dengan probabilitas p> 1/2 jika N tidak dalam bentuk karena ada algoritma klasik efisien untuk pd kekuatan utama murni (dan tentu saja untuk mengenali faktor 2), sebuah algoritma probabilistik yang efisien untuk faktorisasi dapat ditemukan jika r periode eksponensial modular dapat ditentukan dalam waktu polinomial.
4.2.2.3 Period dari sebuah Function
Misalkan F fungsi kuantum F : |x, 0i → |x, f (x)i dari fungsi bilangan bulat f : Z → Z2m dengan periode r < 2n. Untuk menentukan r, kita perlu dua register, dengan ukuran 2n dan m qubit, yang harus diatur ulang ke | 0, 0i. Sebagai langkah awal kami memproduksi superposisi homogen dari semua dasar-vektor dalam register pertama dengan menerapkan operator U dengan
Gambar 4.19
Hal ini dapat mis dicapai oleh Hadamard transform H. Menerapkan F untuk kondisi yang dihasilkan memberikan
Gambar 4.20
Sebuah pengukuran register kedua dengan hasil k = f (s) dengan s <r mengurangi bagian untuk
Gambar 4.21
Keadaan pasca-pengukuran dari register pertama hanya terdiri dari basevectors formulir |rj + si since f (rj + s) = f (s) untuk semua j. Oleh karena itu memiliki diskrit, spektrum homogen. Hal ini tidak mungkin untuk langsung mengekstrak r periode atau kelipatan dengan pengukuran dari register pertama karena random offset s. masalah ini dapat diselesaikan dengan melakukan Transformasi Fourier diskrit.
Gambar 4.22
pada register, sebagai spektrum probabilitas keadaan berubah adalah invarian untuk offset (yaitu hanya fase tapi tidak nilai absolut dari amplitudo kompleks dilakukan).
Gambar 4.23
Jika N = 22n merupakan kelipatan dari r kemudian jika i merupakan kelipatan dari N / r dan 0 sebaliknya. Tetapi bahkan jika r bukan kekuatan 2, spektrum menunjukkan puncak yang berbeda dengan periode N / r karena
Gambar 4.24
Ini juga merupakan alasan mengapa kita menggunakan register pertama qubit 2n ketika r < 2n karena menjamin setidaknya elemen 2n dalam jumlah di atas dan dengan demikian puncak lebar agar O (1). Jika sekarang kita mengukur pertama kali mendaftar, kita akan mendapatkan nilai c dekat dengan. Hal ini dapat ditulis sebagai c/N = c •Kita bisa berpikir ini sebagai menemukan pendekatan rasional a / b dengan a, b < 2n untuk tetap titik bilangan biner c • 2-2n. Sebuah algoritma klasik yang efisien untuk memecahkan masalah ini dengan menggunakan pecahan lanjutan dijelaskan dalam [16] dan diimplementasikan dalam fungsi denominator (Lampiran B.2). Karena bentuk bilangan rasional tidak unik, ¸ dan r hanya ditentukan oleh a/b =lambda/r jika FPB (lambda, r) = 1. Probabilitas bahwalambda dan r adalah coprime lebih besar maka 1/ln r, sehingga hanya O (n) mencoba diperlukan untuk konstan probabilitas keberhasilan sedekat pada 1 sebagai desired.
4.2.3 Quantum Fourier Transform
Untuk vektor dimensi |spectrumi, transformasi Fourier diskrit didefinisikan sebagai
Gambar 4.25
Karena |spectrumi adalah bagian gabungan qubit n, N selalu kekuatan dari 2. Fourier cepat klasik Transform (FFT) menggunakan dekomposisi biner dari eksponen untuk melakukan transformasi di O(n2n) langkah. Seperti yang disarankan oleh Coppersmith, prinsip yang sama dapat diadaptasi adalah untuk komputer kuantum dengan menggunakan kombinasi dari Hadamard Transformasi H dan fase bersyarat gerbang V. Indeks-indeks di bawah ini mengindikasikan qubit dioperasikan pada:
Gambar 4.26
DFT 0 iterates qubit membentuk MSB ke LSB, "perpecahan" qubit dengan transformasi Hadamard dan kemudian kondisional berlaku fase sesuai dengan posisi biner relatif mereka(e 2i−j+1 ) untuk setiap qubit sudah berpisah. Basis-vektor keadaan berubah|spectrum˜0i = DFT 0 |spectrumi diberikan dalam membalik urutan bit, sehingga untuk mendapatkan DFT yang sebenarnya, bit harus membalik.
operator dft(qureg q)
{
// main operator const n=#q;
// set n to length of input int i;
int j;
// declare loop counters for i=0 to n-1
{
for j=0 to i-1
{
// apply conditional phase gates CPhase(2*pi/2^(i-j+1),q[n-i-1] & q[n-j-1]);
}
Mix(q[n-i-1]);
// qubit rotation
}
flip(q);
// swap bit order of the output
}
4.2.4 Modular Arithmetic
Bagian yang paling sulit dalam menerapkan algoritma Shor adalah konstruksi dari fungsi kuantum yang efisien untuk exponentiation modular.
Gambar 4.27
Dengan asumsi kita sudah memiliki sebuah implementasi untuk penambahan modular, kita bisa menggunakannya untuk membangun perkalian modular dan akhirnya eksponensial karena
Gambar 4.28
4.2.4.1 Modular Addition
Penambahan modulo n dari bilangan bulat klasik dan register kuantum b dapat hasil baik a + b atau (a-n) + b), tergantung pada dasar-vektor tertentu | bi. Sedangkan untuk b <n operasi adalah revertible, hal ini tidak terjadi untuk b ¸ n, jadi, jika n tidak terjadi untuk menjadi kekuatan dari 2, selain ys sasaran resister untuk jumlah itu, kita membutuhkan tambahan bendera-qubit yy untuk memungkinkan fungsi kuantum addn yang baik, kesatuan dan invarian ke b:
Gambar 4.29
Implementasi sebenarnya addn dapat ditemukan dalam lampiran B.5. Sejak addnn−a,n merupakan fungsi kuantum untuk pengurangan modular dan dengan demikian mengimplementasikan fungsi invers f −1(b) = b − a mod n to fa,n = a + b mod n,, kita dapat membangun sebuah versi oaddn Timpa penambahan modular, dengan menggunakan metode :
Gambar 4.30
addnn−a,n tidak membalikkan overflow flag yf, jadi kita harus beralih secara manual:
Gambar 4.31
Target awal register ys dan yf sekarang dapat dialokasikan sebagai unmanaged awal local
qufunct oaddn(int a,int n,qureg sum,quconst e)
{
qureg j[#sum];
qureg f[1];
addn(a,n,sum,f,j,e);
// junk -> a+b mod n Swap(sum,j);
// swap junk and sum CNot(f,e);
// toggle flag !addn(n-a,n,sum,f,j,e);
// uncompute b to zero
}
4.2.4.2 Modular Multiplication
Perkalian modular hanyalah komposisi tambahan bersyarat untuk setiap qubit b. The peubah pertama dapat sedikit dioptimalkan, karena akumulator (prod) masih kosong
qufunct muln(int a,int n,quconst b,qureg prod,quconst e)
{ int i;
for i=0 to #prod-1
{
if bit(a,i)
{
CNot(prod[i],b[0] & e);
}
}
for i=1 to #b-1
{
oaddn(2^i*a mod n,n,prod,b[i] & e);
}
}
Seperti di atas, kita dapat membangun sebuah versi Timpa, jika pelaksanaan fungsi invers ada. Hal ini terjadi jika gcd (a, n) = 1 sehingga dan n adalah relatif prima, karena kemudian terbalik modular a-1 dengan-1a mod n = 1 ada. Karena kita berniat untuk menggunakan operator untuk algoritma Shor yang menuntut bahwa gcd (ak, n) = 1, ini cukup baik bagi kita. Dengan menggunakan dua gerbang XOR bersyarat didefinisikan sebagai
Gambar 4.32
untuk swapping registers2 kita dapat menerapkan versi Timpa bersyarat dari muln didefinisikan sebagai
Gambar 4.33
qufunct omuln(int a,int n,qureg b,quconst e)
{
qureg j[#b];
muln(a,n,b,j,e);
!muln(invmod(a,n),n,j,b,e);
cxor(j,b,e);
cxor(b,j,e);
}
4.2.4.3 Modular Exponentiation
Seperti muln, kita dapat membangun eksponensial modular dengan kondisional menerapkan omuln dengan qubit eksponen sebagai memungkinkan tali. sebelum kita dapat memulai iterasi, akumulator (ex) harus diinisialisasi oleh 1.
qufunct expn(int a,int n,quconst b,quvoid ex)
{
int i;
Not(ex[0]);
// start with 1 for i=0 to #b-1
{
omuln(powmod(a,2^i,n),n,ex,b[i]);
// ex -> ex*a^2^i mod n
}
}
4.2.5 Implementation
4.2.5.1 Auxiliary Functions
Pelaksanaan algoritma Shor menggunakan fungsi berikut:
• boolean testprime(int n) Tests whether n is a prime number • boolean testprimepower(int n) Tests whether n is a prime power3 • int powmod(int x,int a,int n) Calculates xa mod n • int denominator(real x,int qmax) Returns the denominator q of the best rational approximation p ≈ x with p, q < qmax
4.2.5.2 The Procedure shor
Prosedur shor memeriksa apakah nomor integer cocok untuk quantum faktorisasi, dan kemudian mengulangi algoritma Shor sampai faktor telah ditemukan.
procedure shor(int number)
{
int width=ceil(log(number,2));
// size of number in bits qureg reg1[2*width];
// first register qureg reg2[width];
// second register int qmax=2^width; int factor;
// found factor int m; real c;
// measured value int x;
// base of exponentiation int p;
int q;
// rational approximation p/q int a;
int b;
// possible factors of number int e;
// e=x^(q/2) mod number
if number mod 2 == 0
{
exit "number must be odd";
}
if testprime(number)
{
exit "prime number";
}
if testprimepower(number)
{
exit "prime power";
}
;
{
{
// generate random base x=floor(random()*(number-3))+2;
}
until gcd(x,number)==1;
print "chosen random x =",x; Mix(reg1);
// Hadamard transform expn(x,number,reg1,reg2);
// modular exponentiation measure reg2;
// measure 2nd register dft(reg1);
// Fourier transform measure reg1,m;
// measure 1st register reset;
// clear local registers if m==0
{
// failed if measured 0 print "measured zero in 1st register. trying again ...";
}
else { c=m*0.5^(2*width);
// fixed point form of m q=denominator(c,qmax);
// find rational approximation p=floor(q*m*c+0.5);
print "measured",m,", approximation for",c,"is",p,"/",q; if q mod 2==1 and 2*q<qmax
{
// odd q ? try expanding p/q print "odd denominator, expanding by 2"; p=2*p; q=2*q;
}
if q mod 2==1
{
// failed if odd q print "odd period. trying again ...";
}
else
{
print "possible period is",q;
e=powmod(x,q/2,number);
// calculate candidates for a=(e+1) mod number;
// possible common factors b=(e+number-1) mod number;
// with number print x,"^",q/2,"+ 1 mod",number,"=",a,",", x,"^",q/2,"- 1 mod",number,"=",b;
factor=max(gcd(number,a),gcd(number,b));
}
}
}
until factor>1 and factor<number; print number,"=",factor,"*",number/factor;
}
4.2.5.3 Factoring 15
15 adalah jumlah terkecil yang dapat difaktorkan dengan algoritma Shor, karena itu produk dari bilangan prima terkecil ganjil 3 dan 5. implementasi kami dari exponentiation modular kebutuhan 2l + 1 qubit menggores ruang dengan l=dld(15 + 1)e = 4. Algoritma itu sendiri membutuhkan qubit 3l, sehingga total 21 qubit harus disediakan.
$ qcl -b21 -i shor.qcl
qcl> shor(15)
: chosen random x = 4
: measured zero in 1st register. trying again ...
: chosen random x = 11
: measured 128 , approximation for 0.500000 is 1 / 2
: possible period is 2
: 11 ^ 1 + 1 mod 15 = 12 , 11 ^ 1 - 1 mod 15 = 10
: 15 = 5 * 3
Percobaan pertama gagal karena 0 diukur dalam daftar pertama | spectrum0i dan lambda / r = 0 tidak memberikan informasi tentang periode r. Orang mungkin berpendapat bahwa hal ini tidak mungkin terjadi, karena daftar pertama memiliki 8 qubit dan 256 kemungkinan dasar-vektor, namun, jika nomor n adalah menjadi terfaktor, salah satu mungkin berharap periode tentang √ n dengan asumsi bahwa faktor-prime tor n adalah dari urutan yang sama besarnya. Hal ini akan mengakibatkan q periode setelah DFT dan probabilitas p = 1 sengaja memilih basevector yang | 0i, akan menjadi p = 25,8%. Dalam kasus khusus dari awal nilai x = 4 periode modular eksponensial adalah 2 sejak 42 mod 15 = 1, akibatnya spektrum Fourier menunjukkan 2 puncak pada | 0i dan | 128i dan p = 1/2. Kedua mencoba juga memiliki probabilitas yang sama kegagalan sejak 112 15 mod =
1, tapi kali ini, pengukuran mengambil puncak kedua dalam spektrum at | 128i. Dengan 128/28 = 1/2 = lambda / r, periode r = 2 diidentifikasi dengan benar dan faktor FPB (112/2 ± 1, 15) = {3, 5} ke 15 telah ditemukan.
5 BAB V
PENUTUP
Berdasarkan uraian diatas dapat disimpulkan bahwa sistem pada komputer konvensional (komputer digital) sangat berbeda. Untuk komputer konvensional menggunakan bit 0 dan 1. Untuk komputer kuantum menggunakan qubit 0 , 1 dan superposisi 0 dan 1. Kecepatan komputer quantum lebih cepat dari pada komputer konvensional (komputer digital) karena melakukan proses secara simultan tidak secara linear seperti komputer konvensional. Saat ini perkembangan teknologi sudah menghasilkan komputer kuantum sampai 7 qubit, tetapi menurut penelitian dan analisa yang ada, dalam beberapa tahun mendatang teknologi komputer kuantum bisa mencapai 100 qubit. Kita bisa membayangkan betapa cepatnya komputer masa depan nanti. Semua perhitungan yang biasanya butuh waktu berbulan-bulan, bertahun-tahun, bahkan berabad-abad pada akhirnya bisa dilaksanakan hanya dalam hitungan menit.
Bibliography
[1] Bernhard ¨Omer, “Structured Quantum Programming”, http://tph.tuwien.ac.at/~oemer/doc/structquprog.pdf
[2] Bernhard ¨Omer, “A Procedural Formalism for Quantum Computing”, http://tph.tuwien.ac.at/~oemer/doc/qcldoc.pdf
[3] Bernhard ¨Omer, “Quantum Programming in QCL”, http://tph.tuwien.ac.at/~oemer/doc/quprog.pdf
[4] Herlambang Saputra, “Kajian Tentang Komputer Kuantum Sebagai Pengganti Komputer Konvensional Di Masa Depan”, http://uppm.ilkom.unsri.ac.id/userfiles/JurnalVol_4_No_2_Juli_2009/3-Herlambang.pdf
