"Saya rasa saya boleh mengatakan dengan selamat bahawa tiada siapa yang memahami mekanik kuantum." - Richard Feynman
Topik pengkomputeran kuantum sentiasa menarik minat penulis dan wartawan teknologi. Potensi pengiraan dan kerumitannya memberikan aura mistik tertentu. Terlalu kerap, artikel ciri dan maklumat grafik menerangkan secara terperinci pelbagai prospek industri ini, sementara hampir tidak menyentuh aplikasi praktikalnya: ini boleh mengelirukan pembaca yang kurang prihatin.
Artikel sains popular meninggalkan penerangan tentang sistem kuantum dan membuat pernyataan seperti:
Bit biasa boleh menjadi 1 atau 0, tetapi qubit boleh menjadi 1 dan 0 pada masa yang sama.
Jika anda sangat bertuah (yang saya tidak pasti), anda akan diberitahu bahawa:
Qubit berada dalam superposisi antara "1" dan "0".
Tiada satu pun daripada penjelasan ini kelihatan munasabah, kerana kami cuba merumuskan fenomena mekanik kuantum menggunakan bahasa yang dibangunkan dalam dunia yang sangat tradisional. Untuk menerangkan dengan jelas prinsip pengkomputeran kuantum, perlu menggunakan bahasa lain - matematik.
Dalam tutorial ini, saya akan membincangkan alat matematik yang diperlukan untuk memodelkan dan memahami sistem pengkomputeran kuantum, serta cara untuk menggambarkan dan menggunakan logik pengkomputeran kuantum. Selain itu, saya akan memberikan contoh algoritma kuantum dan memberitahu anda apa kelebihannya berbanding komputer tradisional.
Saya akan melakukan yang terbaik untuk menerangkan semua ini dalam bahasa yang jelas, tetapi saya masih berharap pembaca artikel ini mempunyai pemahaman asas tentang algebra linear dan logik digital (algebra linear dilindungi , tentang logik digital - ).
Mula-mula, mari kita bincangkan prinsip logik digital. Ia berdasarkan penggunaan litar elektrik untuk menjalankan pengiraan. Untuk menjadikan penerangan kami lebih abstrak, mari kita ringkaskan keadaan wayar elektrik kepada "1" atau "0", yang sepadan dengan keadaan "hidup" atau "mati". Dengan menyusun transistor dalam urutan tertentu, kami akan mencipta unsur logik yang dipanggil yang mengambil satu atau lebih nilai isyarat input dan menukarnya menjadi isyarat keluaran berdasarkan peraturan logik Boolean tertentu.
Gerbang logik biasa dan jadual keadaannya
Berdasarkan rantaian unsur-unsur asas tersebut, unsur-unsur yang lebih kompleks boleh dicipta, dan berdasarkan rantaian unsur-unsur yang lebih kompleks, kita akhirnya boleh, dengan tahap abstraksi yang besar, mengharapkan untuk mendapatkan analog pemproses pusat.
Seperti yang saya nyatakan sebelum ini, kita memerlukan cara untuk mewakili logik digital secara matematik. Mula-mula, mari kita perkenalkan logik tradisional matematik. Menggunakan algebra linear, bit klasik dengan nilai "1" dan "0" boleh diwakili sebagai dua vektor lajur:
di mana nombor di sebelah kiri adalah vektor. Dengan mewakili bit kami dengan cara ini, kami boleh memodelkan operasi logik pada bit menggunakan transformasi vektor. Sila ambil perhatian: walaupun menggunakan dua bit dalam get logik boleh melakukan banyak operasi (AND, NOT, XOR, dll.), apabila menggunakan satu bit, hanya empat operasi boleh dilakukan: penukaran identiti, penolakan, pengiraan pemalar "0" dan pengiraan pemalar "1". Dengan penukaran identiti, bit kekal tidak berubah, dengan penafian, nilai bit berubah kepada sebaliknya (dari "0" kepada "1" atau dari "1" kepada "0"), dan pengiraan pemalar "1" atau "0" menetapkan bit kepada "1" atau "0" tanpa mengira nilai sebelumnya.
| Identiti | Transformasi identiti |
| Penafian | Penafian |
| Malar-0 | Pengiraan pemalar "0" |
| Malar-1 | Pengiraan pemalar "1" |
Berdasarkan cadangan perwakilan baharu kami tentang bit, agak mudah untuk melaksanakan operasi pada bit yang sepadan menggunakan transformasi vektor:
Sebelum melangkah lebih jauh, mari kita lihat konsepnya , yang hanya membayangkan bahawa untuk memastikan keterbalikan operasi atau elemen logik, adalah perlu untuk menentukan senarai nilai isyarat input berdasarkan isyarat output dan nama operasi yang digunakan. Oleh itu, kita boleh membuat kesimpulan bahawa transformasi identiti dan penolakan boleh diterbalikkan, tetapi operasi untuk mengira pemalar "1" dan "0" tidak. Terima kasih kepada mekanik kuantum, komputer kuantum menggunakan operasi boleh balik secara eksklusif, jadi itulah yang akan kami fokuskan. Seterusnya, kami menukar unsur tak boleh balik kepada unsur boleh balik untuk membolehkan ia digunakan oleh komputer kuantum.
Dengan bit individu boleh diwakili oleh banyak bit:
Sekarang kita mempunyai hampir semua konsep matematik yang diperlukan, mari kita beralih ke gerbang logik kuantum pertama kita. Ini adalah pengendali , atau Tidak dikawal (NOT), yang sangat penting dalam pengkomputeran boleh balik dan kuantum. Elemen CNOT digunakan untuk dua bit dan mengembalikan dua bit. Bit pertama ditetapkan sebagai bit "kawalan", dan bit kedua sebagai bit "kawalan". Jika bit kawalan ditetapkan kepada "1", bit kawalan menukar nilainya; Jika bit kawalan ditetapkan kepada "0", bit kawalan tidak diubah.
Operator ini boleh diwakili sebagai vektor transformasi berikut:
Untuk menunjukkan semua yang telah kami bincangkan setakat ini, saya akan menunjukkan kepada anda cara menggunakan elemen CNOT pada berbilang bit:
Untuk meringkaskan perkara yang telah diperkatakan: dalam contoh pertama kita menguraikan |10β© ke dalam bahagian hasil tensornya dan menggunakan matriks CNOT untuk mendapatkan keadaan produk sepadan baharu; kita kemudian memfaktorkannya kepada |11β© mengikut jadual nilai CNOT yang diberikan sebelum ini.
Jadi, kami telah mengingati semua peraturan matematik yang akan membantu kami memahami pengkomputeran tradisional dan bit biasa, dan akhirnya kami boleh beralih kepada pengkomputeran kuantum moden dan qubit.
Jika anda telah membaca sejauh ini, maka saya mempunyai berita baik untuk anda: qubit boleh dinyatakan dengan mudah secara matematik. Secara umum, jika bit klasik (cbit) boleh ditetapkan kepada |1β© atau |0β©, qubit hanyalah dalam superposisi dan boleh kedua-duanya |0β© dan |1β© sebelum pengukuran. Selepas pengukuran, ia runtuh menjadi |0β© atau |1β©. Dalam erti kata lain, qubit boleh diwakili sebagai gabungan linear |0β© dan |1β© mengikut formula di bawah:
mana aβ ΠΈ aβ mewakili, masing-masing, amplitud |0β© dan |1β©. Ini boleh dianggap sebagai "kebarangkalian kuantum", yang mewakili kebarangkalian qubit runtuh ke dalam salah satu keadaan selepas ia diukur, kerana dalam mekanik kuantum objek dalam superposisi runtuh ke salah satu keadaan selepas ditetapkan. Mari kembangkan ungkapan ini dan dapatkan yang berikut:
Untuk memudahkan penjelasan saya, inilah representasi yang akan saya gunakan dalam artikel ini.
Untuk qubit ini, peluang untuk runtuh kepada nilai aβ selepas pengukuran adalah sama dengan |aβ|Β², dan peluang untuk runtuh kepada nilai aβ adalah sama dengan |aβ|Β². Sebagai contoh, untuk qubit berikut:
peluang untuk runtuh menjadi β1β adalah bersamaan dengan |1/ β2|Β², atau Β½, iaitu, 50/50.
Memandangkan dalam sistem klasik semua kebarangkalian mesti ditambah sehingga satu (untuk taburan kebarangkalian lengkap), kita boleh membuat kesimpulan bahawa kuasa dua nilai mutlak amplitud |0β© dan |1β© mesti ditambah sehingga satu. Berdasarkan maklumat ini kita boleh merumuskan persamaan berikut:
Jika anda biasa dengan trigonometri, anda akan dapati bahawa persamaan ini sepadan dengan teorem Pythagoras (aΒ²+bΒ²=cΒ²), iaitu, kita boleh mewakili secara grafik kemungkinan keadaan qubit sebagai titik pada bulatan unit, iaitu:
Operator dan elemen logik digunakan pada qubit dengan cara yang sama seperti dalam situasi dengan bit klasik - berdasarkan transformasi matriks. Semua pengendali matriks terbalik yang telah kami ingat setakat ini, khususnya CNOT, boleh digunakan untuk bekerja dengan qubit. Pengendali matriks sedemikian membolehkan anda menggunakan setiap amplitud qubit tanpa mengukur dan meruntuhkannya. Biar saya memberi anda contoh menggunakan operator penolakan pada qubit:
Sebelum kita meneruskan, izinkan saya mengingatkan anda bahawa nilai amplitud aβ dan aβ sebenarnya , jadi keadaan qubit boleh dipetakan dengan paling tepat pada sfera unit tiga dimensi, juga dikenali sebagai :
Walau bagaimanapun, untuk memudahkan penjelasan, kami akan mengehadkan diri kami di sini kepada nombor nyata.
Nampaknya masa untuk membincangkan beberapa elemen logik yang masuk akal semata-mata dalam konteks pengkomputeran kuantum.
Salah satu pengendali yang paling penting ialah "elemen Hadamard": ia memerlukan sedikit dalam keadaan "0" atau "1" dan meletakkannya dalam superposisi yang sesuai dengan peluang 50% untuk runtuh menjadi "1" atau "0" selepas pengukuran.
Perhatikan bahawa terdapat nombor negatif di sebelah kanan bawah pengendali Hadamard. Ini disebabkan oleh fakta bahawa hasil penggunaan operator bergantung pada nilai isyarat input: - |1β© atau |0β©, dan oleh itu pengiraan boleh diterbalikkan.
Satu lagi perkara penting tentang unsur Hadamard ialah kebolehbalikannya, bermakna ia boleh mengambil qubit dalam superposisi yang sesuai dan mengubahnya menjadi |0β© atau |1β©.
Ini sangat penting kerana ia memberi kita keupayaan untuk berubah daripada keadaan kuantum tanpa menentukan keadaan qubit - dan, dengan itu, tanpa meruntuhkannya. Oleh itu, kita boleh menstrukturkan pengkomputeran kuantum berdasarkan prinsip deterministik dan bukannya prinsip probabilistik.
Pengendali kuantum yang mengandungi hanya nombor nyata adalah sebaliknya, jadi kita boleh mewakili hasil penggunaan operator kepada qubit sebagai transformasi dalam bulatan unit dalam bentuk mesin keadaan:
Oleh itu, qubit, keadaan yang ditunjukkan dalam rajah di atas, selepas menggunakan operasi Hadamard, diubah menjadi keadaan yang ditunjukkan oleh anak panah yang sepadan. Begitu juga, kita boleh membina mesin keadaan lain yang akan menggambarkan transformasi qubit menggunakan pengendali penolakan seperti yang ditunjukkan di atas (juga dikenali sebagai pengendali penolakan Pauli, atau penyongsangan bit), seperti ditunjukkan di bawah:
Untuk melaksanakan operasi yang lebih kompleks pada qubit kami, kami boleh merantai berbilang operator atau menggunakan elemen beberapa kali. Contoh transformasi bersiri berdasarkan kelihatan seperti ini:
Iaitu, jika kita bermula dengan bit |0β©, gunakan sedikit penyongsangan, dan kemudian operasi Hadamard, kemudian penyongsangan bit yang lain, dan sekali lagi operasi Hadamard, diikuti dengan penyongsangan bit terakhir, kita berakhir dengan vektor yang diberikan oleh on sebelah kanan rantai. Dengan melapiskan mesin keadaan yang berbeza di atas satu sama lain, kita boleh bermula pada |0β© dan mengesan anak panah berwarna yang sepadan dengan setiap transformasi untuk memahami cara semuanya berfungsi.
Memandangkan kita telah sampai sejauh ini, sudah tiba masanya untuk mempertimbangkan salah satu jenis algoritma kuantum, iaitu - , dan tunjukkan kelebihannya berbanding komputer klasik. Perlu diingat bahawa algoritma Deutsch-Jozsa adalah benar-benar deterministik, iaitu, ia mengembalikan jawapan yang betul 100% sepanjang masa (tidak seperti kebanyakan algoritma kuantum lain berdasarkan takrifan probabilistik qubit).
Bayangkan anda mempunyai kotak hitam yang mengandungi fungsi/pengendali pada satu bit (ingat - dengan satu bit, hanya empat operasi boleh dilakukan: penukaran identiti, penolakan, penilaian pemalar "0" dan penilaian pemalar "1 "). Apakah sebenarnya fungsi yang dilakukan dalam kotak itu? Anda tidak tahu yang mana satu, tetapi anda boleh melalui seberapa banyak varian nilai input yang anda suka dan menilai hasil output.
Berapa banyak input dan output yang anda perlu jalankan melalui kotak hitam untuk mengetahui fungsi yang sedang digunakan? Fikirkan perkara ini sejenak.
Dalam kes komputer klasik, anda perlu membuat 2 pertanyaan untuk menentukan fungsi untuk digunakan. Sebagai contoh, jika input "1" menghasilkan output "0", menjadi jelas bahawa sama ada fungsi mengira pemalar "0" atau fungsi penafian digunakan, selepas itu anda perlu menukar nilai isyarat input ke "0" dan lihat apa yang berlaku di pintu keluar.
Dalam kes komputer kuantum, dua pertanyaan juga akan diperlukan, kerana anda masih memerlukan dua nilai output yang berbeza untuk menentukan dengan tepat fungsi untuk digunakan pada nilai input. Walau bagaimanapun, jika anda merumuskan semula soalan itu sedikit, ternyata komputer kuantum masih mempunyai kelebihan yang serius: jika anda ingin mengetahui sama ada fungsi yang digunakan adalah malar atau berubah-ubah, komputer kuantum akan mempunyai kelebihan.
Fungsi yang digunakan dalam kotak adalah berubah-ubah jika nilai isyarat input yang berbeza menghasilkan hasil yang berbeza pada output (contohnya, penukaran identiti dan penyongsangan bit), dan jika nilai output tidak berubah tanpa mengira nilai input, maka fungsi adalah malar (contohnya, mengira pemalar "1" atau mengira pemalar "0").
Menggunakan algoritma kuantum, anda boleh menentukan sama ada fungsi dalam kotak hitam adalah malar atau berubah berdasarkan hanya satu pertanyaan. Tetapi sebelum kita melihat cara melakukan ini secara terperinci, kita perlu mencari cara untuk menstruktur setiap fungsi ini pada komputer kuantum. Memandangkan mana-mana pengendali kuantum mesti boleh terbalik, kami serta-merta menghadapi masalah: fungsi untuk mengira pemalar "1" dan "0" tidak.
Penyelesaian biasa yang digunakan dalam pengkomputeran kuantum ialah menambah qubit keluaran tambahan yang mengembalikan apa-apa nilai input yang diterima oleh fungsi.
| Sebelum: | Selepas: |
|
|
|
Dengan cara ini, kita boleh menentukan nilai input semata-mata berdasarkan nilai output, dan fungsi menjadi boleh terbalik. Struktur litar kuantum mewujudkan keperluan untuk bit input tambahan. Demi membangunkan pengendali yang sepadan, kami akan menganggap bahawa qubit input tambahan ditetapkan kepada |0β©.
Menggunakan perwakilan litar kuantum yang sama yang kita gunakan sebelum ini, mari kita lihat bagaimana setiap empat elemen (transformasi identiti, penolakan, penilaian pemalar "0" dan penilaian pemalar "1") boleh dilaksanakan menggunakan pengendali kuantum.
Sebagai contoh, ini adalah cara anda boleh melaksanakan fungsi untuk mengira pemalar "0":
Pengiraan pemalar "0":
Di sini kami tidak memerlukan operator sama sekali. Qubit input pertama (yang kami anggap sebagai |0β©) kembali dengan nilai yang sama, dan nilai input kedua mengembalikan sendiri - seperti biasa.
Dengan fungsi untuk mengira pemalar "1" keadaannya sedikit berbeza:
Pengiraan pemalar "1":
Memandangkan kita telah mengandaikan bahawa qubit input pertama sentiasa ditetapkan kepada |0β©, hasil daripada menggunakan operator penyongsangan bit ialah ia sentiasa menghasilkan satu pada output. Dan seperti biasa, qubit kedua memberikan nilai tersendiri pada output.
Apabila memetakan pengendali transformasi identiti, tugas mula menjadi lebih rumit. Begini cara melakukannya:
Transformasi yang sama:
Simbol yang digunakan di sini menandakan elemen CNOT: baris atas menandakan bit kawalan, dan garis bawah menandakan bit kawalan. Biar saya ingatkan anda bahawa apabila menggunakan operator CNOT, nilai bit kawalan berubah jika bit kawalan sama dengan |1β©, tetapi kekal tidak berubah jika bit kawalan sama dengan |0β©. Memandangkan kita mengandaikan bahawa nilai baris atas sentiasa sama dengan |0β©, nilainya sentiasa diberikan kepada garis bawah.
Kami meneruskan dengan cara yang sama dengan pengendali penolakan:
Penafian:
Kami hanya menyongsangkan bit pada penghujung baris keluaran.
Memandangkan kita telah mendapat pemahaman awal itu, mari kita lihat kelebihan khusus komputer kuantum berbanding komputer tradisional apabila ia datang untuk menentukan ketekalan atau kebolehubahan fungsi yang tersembunyi dalam kotak hitam menggunakan hanya satu pertanyaan.
Untuk menyelesaikan masalah ini menggunakan pengkomputeran kuantum dalam satu permintaan, adalah perlu untuk meletakkan qubit input ke dalam superposisi sebelum menghantarnya ke fungsi, seperti ditunjukkan di bawah:
Elemen Hadamard digunakan semula pada hasil fungsi untuk mengeluarkan qubit daripada superposisi dan menjadikan algoritma deterministik. Kami memulakan sistem dalam keadaan |00β© dan, atas sebab-sebab yang saya akan terangkan sebentar lagi, dapatkan keputusan |11β© jika fungsi yang digunakan adalah malar. Jika fungsi di dalam kotak hitam berubah, maka selepas pengukuran sistem mengembalikan hasil |01β©.
Untuk memahami artikel yang lain, mari lihat ilustrasi yang saya tunjukkan sebelum ini:
Dengan menggunakan operator penyongsangan bit dan kemudian menggunakan elemen Hadamard pada kedua-dua nilai input yang sama dengan |0β©, kami memastikan ia diterjemahkan ke dalam superposisi yang sama bagi |0β© dan |1β©, seperti berikut:
Menggunakan contoh menghantar nilai ini kepada fungsi kotak hitam, adalah mudah untuk menunjukkan bahawa kedua-dua fungsi nilai malar mengeluarkan |11β©.
Pengiraan pemalar "0":
Begitu juga, kita melihat bahawa fungsi untuk mengira pemalar "1" juga menghasilkan |11β© sebagai output, iaitu:
Pengiraan pemalar "1":
Ambil perhatian bahawa output ialah |1β©, kerana -1Β² = 1.
Dengan prinsip yang sama, kita boleh membuktikan bahawa apabila menggunakan kedua-dua fungsi pembolehubah, kita akan sentiasa mendapat |01β© pada output (dengan syarat kita menggunakan kaedah yang sama), walaupun semuanya lebih rumit sedikit.
Transformasi yang sama:
Memandangkan CNOT ialah pengendali dua qubit, ia tidak boleh diwakili sebagai mesin keadaan mudah, dan oleh itu adalah perlu untuk menentukan dua isyarat keluaran berdasarkan hasil tensor kedua-dua qubit input dan pendaraban dengan matriks CNOT seperti yang diterangkan sebelum ini:
Dengan kaedah ini, kami juga boleh mengesahkan bahawa nilai output |01β© diterima jika fungsi penafian disembunyikan dalam kotak hitam:
Penafian:
Oleh itu, kami baru sahaja menunjukkan situasi di mana komputer kuantum jelas lebih cekap daripada komputer konvensional.
Apa yang akan datang?
Saya cadangkan kita berakhir di sini. Kami sudah melakukan kerja yang hebat. Jika anda telah memahami semua yang telah saya bincangkan, saya fikir anda kini mempunyai pemahaman yang baik tentang asas pengkomputeran kuantum dan logik kuantum, dan mengapa algoritma kuantum boleh menjadi lebih cekap daripada pengkomputeran tradisional dalam situasi tertentu.
Penerangan saya hampir tidak boleh dipanggil panduan lengkap untuk pengkomputeran kuantum dan algoritma - sebaliknya, ia adalah pengenalan ringkas kepada matematik dan notasi, yang direka untuk menghilangkan idea pembaca tentang subjek yang dikenakan oleh sumber sains popular (serius, ramai yang benar-benar tidak faham keadaan!). Saya tidak sempat menyentuh banyak topik penting seperti , kerumitan nilai amplitud |0β© dan |1β© dan fungsi pelbagai elemen logik kuantum semasa penjelmaan oleh sfera Bloch.
Jika anda ingin menyusun dan menstruktur pengetahuan anda tentang komputer kuantum, dengan segera Saya syorkan anda membaca Emma Strubel: walaupun terdapat banyak formula matematik, buku ini membincangkan algoritma kuantum dengan lebih terperinci.
Sumber: www.habr.com