“Saya rasa saya dapat dengan aman mengatakan bahwa tidak ada seorang pun yang memahami mekanika kuantum.” - Richard Feynman
Topik komputasi kuantum selalu membuat terpesona para penulis dan jurnalis teknologi. Potensi komputasi dan kompleksitasnya memberinya aura mistis tertentu. Terlalu sering, artikel unggulan dan infografis menjelaskan secara rinci berbagai prospek industri ini, namun hampir tidak menyentuh penerapan praktisnya: hal ini dapat menyesatkan pembaca yang kurang perhatian.
Artikel sains populer menghilangkan deskripsi sistem kuantum dan membuat pernyataan seperti:
Bit biasa bisa bernilai 1 atau 0, tetapi qubit bisa bernilai 1 dan 0 sekaligus.
Jika Anda sangat beruntung (yang saya tidak yakin), Anda akan diberitahu bahwa:
Qubit berada dalam superposisi antara "1" dan "0".
Tak satu pun dari penjelasan ini yang masuk akal, karena kami mencoba merumuskan fenomena mekanika kuantum menggunakan bahasa yang dikembangkan di dunia yang sangat tradisional. Untuk menjelaskan dengan jelas prinsip-prinsip komputasi kuantum, perlu menggunakan bahasa lain - matematika.
Dalam tutorial ini, saya akan membahas alat matematika yang diperlukan untuk memodelkan dan memahami sistem komputasi kuantum, serta cara mengilustrasikan dan menerapkan logika komputasi kuantum. Selain itu, saya akan memberikan contoh algoritma kuantum dan memberi tahu Anda apa kelebihannya dibandingkan komputer tradisional.
Saya akan berusaha semaksimal mungkin untuk menjelaskan semua ini dalam bahasa yang jelas, namun saya tetap berharap pembaca artikel ini memiliki pemahaman dasar tentang aljabar linier dan logika digital (tercakup dalam aljabar linier. , tentang logika digital - ).
Pertama, mari kita bahas prinsip logika digital. Hal ini didasarkan pada penggunaan rangkaian listrik untuk melakukan perhitungan. Untuk membuat uraian kita lebih abstrak, mari kita sederhanakan keadaan kabel listrik menjadi “1” atau “0”, yang sesuai dengan keadaan “hidup” atau “mati”. Dengan menyusun transistor dalam urutan tertentu, kita akan membuat apa yang disebut elemen logika yang mengambil satu atau lebih nilai sinyal masukan dan mengubahnya menjadi sinyal keluaran berdasarkan aturan logika Boolean tertentu.
Gerbang logika umum dan tabel statusnya
Berdasarkan rantai elemen dasar tersebut, elemen yang lebih kompleks dapat dibuat, dan berdasarkan rantai elemen yang lebih kompleks, pada akhirnya kita dapat, dengan tingkat abstraksi yang besar, mengharapkan untuk mendapatkan analog dari prosesor pusat.
Seperti yang saya sebutkan sebelumnya, kita memerlukan cara untuk merepresentasikan logika digital secara matematis. Pertama, mari kita perkenalkan logika matematika tradisional. Menggunakan aljabar linier, bit klasik dengan nilai "1" dan "0" dapat direpresentasikan sebagai dua vektor kolom:
di mana angka-angka di sebelah kiri berada vektor. Dengan merepresentasikan bit-bit kita dengan cara ini, kita dapat memodelkan operasi logis pada bit-bit tersebut menggunakan transformasi vektor. Harap dicatat: meskipun menggunakan dua bit di gerbang logika dapat melakukan banyak operasi (DAN, BUKAN, XOR, dll.), bila menggunakan satu bit, hanya empat operasi yang dapat dilakukan: konversi identitas, negasi, perhitungan konstanta “0” dan perhitungan konstanta “1”. Dengan konversi identitas, bit tetap tidak berubah, dengan negasi, nilai bit berubah ke arah sebaliknya (dari “0” menjadi “1” atau dari “1” menjadi “0”), dan perhitungan konstanta “1” atau “0” menyetel bit ke “1” atau “0” terlepas dari nilai sebelumnya.
| identitas | Transformasi identitas |
| yang negasi | Penyangkalan |
| Konstan-0 | Perhitungan konstanta "0" |
| Konstan-1 | Perhitungan konstanta "1" |
Berdasarkan representasi bit baru yang kami usulkan, cukup mudah untuk melakukan operasi pada bit terkait menggunakan transformasi vektor:
Sebelum melangkah lebih jauh, mari kita lihat konsepnya , yang secara sederhana menyiratkan bahwa untuk memastikan reversibilitas suatu operasi atau elemen logika, perlu ditentukan daftar nilai sinyal masukan berdasarkan sinyal keluaran dan nama operasi yang digunakan. Dengan demikian, kita dapat menyimpulkan bahwa transformasi identitas dan negasi bersifat reversibel, tetapi operasi untuk menghitung konstanta “1” dan “0” tidak dapat dibalik. Terimakasih untuk mekanika kuantum, komputer kuantum hanya menggunakan operasi reversibel, jadi itulah yang akan kita fokuskan. Selanjutnya, kami mengubah elemen ireversibel menjadi elemen reversibel agar dapat digunakan oleh komputer kuantum.
Dengan bit individual dapat diwakili oleh banyak bit:
Sekarang kita memiliki hampir semua konsep matematika yang diperlukan, mari kita beralih ke gerbang logika kuantum pertama kita. Ini adalah operatornya , atau controlled Not (NOT), yang sangat penting dalam komputasi reversibel dan kuantum. Elemen CNOT berlaku untuk dua bit dan mengembalikan dua bit. Bit pertama ditetapkan sebagai bit “kontrol”, dan bit kedua sebagai bit “kontrol”. Jika bit kontrol disetel ke "1", bit kontrol mengubah nilainya; Jika bit kontrol disetel ke "0", bit kontrol tidak diubah.
Operator ini dapat direpresentasikan sebagai vektor transformasi berikut:
Untuk mendemonstrasikan semua yang telah kita bahas sejauh ini, saya akan menunjukkan cara menggunakan elemen CNOT pada banyak bit:
Untuk meringkas apa yang telah dikatakan: pada contoh pertama kita menguraikan |10⟩ menjadi beberapa bagian produk tensornya dan menggunakan matriks CNOT untuk mendapatkan status produk baru yang sesuai; kita kemudian memfaktorkannya menjadi |11⟩ sesuai tabel nilai CNOT yang diberikan sebelumnya.
Jadi, kita telah mengingat semua aturan matematika yang akan membantu kita memahami komputasi tradisional dan bit biasa, dan akhirnya kita dapat beralih ke komputasi kuantum dan qubit modern.
Jika Anda sudah membaca sejauh ini, saya punya kabar baik untuk Anda: qubit dapat dengan mudah dinyatakan secara matematis. Secara umum, jika bit klasik (cbit) dapat diatur ke |1⟩ atau |0⟩, qubit berada dalam superposisi dan dapat berupa |0⟩ dan |1⟩ sebelum pengukuran. Setelah diukur, ia diciutkan menjadi |0⟩ atau |1⟩. Dengan kata lain, qubit dapat direpresentasikan sebagai kombinasi linier dari |0⟩ dan |1⟩ sesuai dengan rumus di bawah ini:
dimana a₀ и a₁ masing-masing mewakili amplitudo |0⟩ dan |1⟩. Hal ini dapat dianggap sebagai "probabilitas kuantum", yang mewakili probabilitas sebuah qubit runtuh ke salah satu keadaan setelah diukur, karena dalam mekanika kuantum sebuah objek dalam superposisi runtuh ke salah satu keadaan setelah diperbaiki. Mari perluas ekspresi ini dan dapatkan yang berikut:
Untuk menyederhanakan penjelasan saya, representasi inilah yang akan saya gunakan dalam artikel ini.
Untuk qubit ini, kemungkinan jatuh ke nilainya a₀ setelah pengukuran sama dengan |a₀|², dan kemungkinan jatuhnya nilai tersebut a₁ sama dengan |a₁|². Misalnya, untuk qubit berikut:
peluang terpecah menjadi “1” sama dengan |1/ √2|², atau ½, yaitu 50/50.
Karena dalam sistem klasik semua probabilitas harus berjumlah satu (untuk distribusi probabilitas yang lengkap), kita dapat menyimpulkan bahwa kuadrat nilai absolut amplitudo |0⟩ dan |1⟩ harus berjumlah satu. Berdasarkan informasi tersebut kita dapat merumuskan persamaan berikut:
Jika Anda familiar dengan trigonometri, Anda akan melihat bahwa persamaan ini sesuai dengan teorema Pythagoras (a²+b²=c²), yaitu, kita dapat secara grafis merepresentasikan kemungkinan keadaan qubit sebagai titik-titik pada lingkaran satuan, yaitu:
Operator dan elemen logika diterapkan pada qubit dengan cara yang sama seperti pada bit klasik - berdasarkan transformasi matriks. Semua operator matriks yang dapat dibalik yang telah kita ingat sejauh ini, khususnya CNOT, dapat digunakan untuk bekerja dengan qubit. Operator matriks semacam itu memungkinkan Anda menggunakan setiap amplitudo qubit tanpa mengukur dan mengecilkannya. Izinkan saya memberi Anda contoh penggunaan operator negasi pada qubit:
Sebelum kita melanjutkan, izinkan saya mengingatkan Anda tentang nilai amplitudo a₀ dan a₁ sebenarnya , sehingga keadaan qubit dapat dipetakan secara paling akurat ke dalam satuan bola tiga dimensi, yang juga dikenal sebagai :
Namun, untuk menyederhanakan penjelasannya, kami akan membatasi diri pada bilangan real saja.
Tampaknya sudah waktunya untuk membahas beberapa elemen logika yang masuk akal hanya dalam konteks komputasi kuantum.
Salah satu operator yang paling penting adalah "elemen Hadamard": dibutuhkan sedikit dalam keadaan "0" atau "1" dan menempatkannya dalam superposisi yang sesuai dengan kemungkinan 50% untuk diciutkan menjadi "1" atau "0" setelah pengukuran.
Perhatikan ada angka negatif di sisi kanan bawah operator Hadamard. Hal ini disebabkan karena hasil penerapan operator bergantung pada nilai sinyal input: - |1⟩ atau |0⟩, sehingga perhitungannya dapat dibalik.
Poin penting lainnya tentang elemen Hadamard adalah sifat invertibilitasnya, artinya elemen ini dapat mengambil qubit dalam superposisi yang sesuai dan mengubahnya menjadi |0⟩ atau |1⟩.
Hal ini sangat penting karena memberi kita kemampuan untuk bertransformasi dari keadaan kuantum tanpa menentukan keadaan qubit - dan, karenanya, tanpa meruntuhkannya. Dengan demikian, kita dapat menyusun komputasi kuantum berdasarkan prinsip deterministik, bukan prinsip probabilistik.
Operator kuantum yang hanya berisi bilangan real merupakan kebalikannya, sehingga kita dapat merepresentasikan hasil penerapan operator pada qubit sebagai transformasi dalam lingkaran satuan dalam bentuk mesin keadaan:
Jadi, qubit, keadaan yang ditunjukkan pada diagram di atas, setelah menerapkan operasi Hadamard, diubah menjadi keadaan yang ditunjukkan oleh panah yang sesuai. Demikian pula, kita dapat membuat mesin status lain yang akan mengilustrasikan transformasi qubit menggunakan operator negasi seperti yang ditunjukkan di atas (juga dikenal sebagai operator negasi Pauli, atau inversi bit), seperti yang ditunjukkan di bawah ini:
Untuk melakukan operasi yang lebih kompleks pada qubit, kita dapat merangkai beberapa operator atau menerapkan elemen beberapa kali. Contoh transformasi serial berdasarkan adalah sebagai berikut:
Artinya, jika kita memulai dengan bit |0⟩, menerapkan sedikit inversi, lalu operasi Hadamard, lalu inversi bit lainnya, dan lagi operasi Hadamard, diikuti dengan inversi bit terakhir, kita akan mendapatkan vektor yang diberikan oleh on sisi kanan rantai. Dengan melapisi mesin negara yang berbeda di atas satu sama lain, kita dapat memulai dari |0⟩ dan menelusuri panah berwarna yang sesuai dengan setiap transformasi untuk memahami cara kerjanya.
Karena kita telah sampai sejauh ini, sekarang saatnya untuk mempertimbangkan salah satu jenis algoritma kuantum, yaitu - , dan tunjukkan keunggulannya dibandingkan komputer klasik. Perlu dicatat bahwa algoritma Deutsch-Jozsa sepenuhnya deterministik, yaitu, ia mengembalikan jawaban yang benar 100% setiap saat (tidak seperti banyak algoritma kuantum lainnya yang didasarkan pada definisi probabilistik qubit).
Bayangkan Anda memiliki kotak hitam yang berisi fungsi/operator pada satu bit (ingat - dengan satu bit, hanya empat operasi yang dapat dilakukan: konversi identitas, negasi, evaluasi konstanta "0" dan evaluasi konstanta "1 "). Apa sebenarnya fungsi yang dilakukan di dalam kotak? Anda tidak tahu yang mana, tetapi Anda dapat menelusuri varian nilai masukan sebanyak yang Anda suka dan mengevaluasi hasil keluarannya.
Berapa banyak input dan output yang harus Anda jalankan melalui kotak hitam untuk mengetahui fungsi mana yang digunakan? Pikirkan tentang ini sejenak.
Dalam kasus komputer klasik, Anda perlu membuat 2 kueri untuk menentukan fungsi yang akan digunakan. Misalnya, jika input "1" menghasilkan output "0", menjadi jelas bahwa fungsi menghitung konstanta "0" atau fungsi negasi digunakan, setelah itu Anda harus mengubah nilai sinyal input ke "0" dan lihat apa yang terjadi di pintu keluar.
Dalam kasus komputer kuantum, dua kueri juga diperlukan karena Anda masih memerlukan dua nilai keluaran yang berbeda untuk secara tepat menentukan fungsi yang akan diterapkan pada nilai masukan. Namun, jika Anda merumuskan kembali pertanyaannya sedikit, ternyata komputer kuantum masih memiliki keunggulan yang serius: jika Anda ingin mengetahui apakah fungsi yang digunakan konstan atau variabel, komputer kuantum akan memiliki keunggulan.
Fungsi yang digunakan dalam kotak adalah variabel jika nilai sinyal masukan yang berbeda menghasilkan hasil yang berbeda pada keluarannya (misalnya konversi identitas dan inversi bit), dan jika nilai keluaran tidak berubah berapa pun nilai masukannya, maka fungsi tersebut fungsinya konstan (misalnya menghitung konstanta "1" atau menghitung konstanta "0").
Dengan menggunakan algoritma kuantum, Anda dapat menentukan apakah suatu fungsi dalam kotak hitam bersifat konstan atau variabel hanya berdasarkan satu kueri. Namun sebelum kita melihat cara melakukan ini secara mendetail, kita perlu menemukan cara untuk menyusun masing-masing fungsi ini pada komputer kuantum. Karena operator kuantum mana pun harus dapat dibalik, kita segera menghadapi masalah: fungsi untuk menghitung konstanta “1” dan “0” tidak ada.
Solusi umum yang digunakan dalam komputasi kuantum adalah menambahkan qubit keluaran tambahan yang mengembalikan nilai masukan apa pun yang diterima fungsi.
| Kepada: | Setelah: |
|
|
|
Dengan cara ini, kita dapat menentukan nilai masukan hanya berdasarkan nilai keluaran, dan fungsinya menjadi dapat dibalik. Struktur rangkaian kuantum menciptakan kebutuhan akan bit masukan tambahan. Demi mengembangkan operator terkait, kita asumsikan bahwa qubit masukan tambahan disetel ke |0⟩.
Dengan menggunakan representasi rangkaian kuantum yang sama yang kita gunakan sebelumnya, mari kita lihat bagaimana masing-masing dari empat elemen (transformasi identitas, negasi, evaluasi konstanta "0" dan evaluasi konstanta "1") dapat diimplementasikan menggunakan operator kuantum.
Misalnya, ini adalah bagaimana Anda dapat mengimplementasikan fungsi untuk menghitung konstanta “0”:
Perhitungan konstanta "0":
Di sini kita tidak membutuhkan operator sama sekali. Qubit masukan pertama (yang kita asumsikan |0⟩) kembali dengan nilai yang sama, dan nilai masukan kedua kembali sendiri - seperti biasa.
Dengan fungsi menghitung konstanta “1”, situasinya sedikit berbeda:
Perhitungan konstanta "1":
Karena kita berasumsi bahwa qubit masukan pertama selalu disetel ke |0⟩, hasil penerapan operator inversi bit adalah selalu menghasilkan satu pada keluaran. Dan seperti biasa, qubit kedua memberikan nilai tersendiri pada outputnya.
Saat memetakan operator transformasi identitas, tugasnya mulai menjadi lebih rumit. Berikut cara melakukannya:
Transformasi identik:
Simbol yang digunakan di sini menunjukkan elemen CNOT: baris atas menunjukkan bit kontrol, dan garis bawah menunjukkan bit kontrol. Izinkan saya mengingatkan Anda bahwa saat menggunakan operator CNOT, nilai bit kontrol berubah jika bit kontrol sama dengan |1⟩, tetapi tetap tidak berubah jika bit kontrol sama dengan |0⟩. Karena kita berasumsi bahwa nilai baris teratas selalu sama dengan |0⟩, nilainya selalu ditetapkan ke baris terbawah.
Kami melanjutkan dengan cara yang sama dengan operator negasi:
Penyangkalan:
Kami cukup membalikkan bit di akhir jalur keluaran.
Sekarang setelah kita mendapatkan pemahaman awal tersebut, mari kita lihat keunggulan spesifik komputer kuantum dibandingkan komputer tradisional dalam menentukan keteguhan atau variabilitas suatu fungsi yang disembunyikan dalam kotak hitam hanya dengan menggunakan satu kueri.
Untuk mengatasi masalah ini dengan menggunakan komputasi kuantum dalam satu permintaan, qubit masukan perlu dimasukkan ke dalam superposisi sebelum meneruskannya ke fungsi, seperti yang ditunjukkan di bawah ini:
Elemen Hadamard diterapkan kembali ke hasil fungsi untuk memecah qubit dari superposisi dan menjadikan algoritme deterministik. Kita memulai sistem dalam keadaan |00⟩ dan, untuk alasan yang akan saya jelaskan segera, dapatkan hasil |11⟩ jika fungsi yang diterapkan adalah konstan. Jika fungsi di dalam kotak hitam adalah variabel, maka setelah pengukuran sistem mengembalikan hasil |01⟩.
Untuk memahami artikel selanjutnya, mari kita lihat ilustrasi yang saya tunjukkan sebelumnya:
Dengan menggunakan operator inversi bit dan kemudian menerapkan elemen Hadamard ke kedua nilai input yang sama dengan |0⟩, kami memastikan bahwa keduanya diterjemahkan ke dalam superposisi yang sama dari |0⟩ dan |1⟩, sebagai berikut:
Dengan menggunakan contoh meneruskan nilai ini ke fungsi kotak hitam, mudah untuk menunjukkan bahwa kedua fungsi nilai konstan menghasilkan |11⟩.
Perhitungan konstanta "0":
Demikian pula kita melihat bahwa fungsi untuk menghitung konstanta “1” juga menghasilkan |11⟩ sebagai keluaran, yaitu:
Perhitungan konstanta "1":
Perhatikan bahwa outputnya adalah |1⟩, karena -1² = 1.
Dengan prinsip yang sama, kita dapat membuktikan bahwa ketika menggunakan kedua fungsi variabel, kita akan selalu mendapatkan |01⟩ pada output (asalkan kita menggunakan metode yang sama), meskipun semuanya sedikit lebih rumit.
Transformasi identik:
Karena CNOT adalah operator dua qubit, ia tidak dapat direpresentasikan sebagai mesin keadaan sederhana, dan oleh karena itu perlu untuk mendefinisikan dua sinyal keluaran berdasarkan produk tensor dari kedua qubit masukan dan perkaliannya dengan matriks CNOT seperti yang dijelaskan sebelumnya:
Dengan metode ini kita juga dapat memastikan bahwa nilai keluaran |01⟩ diterima jika fungsi negasi disembunyikan di kotak hitam:
Penyangkalan:
Jadi, kami baru saja mendemonstrasikan situasi di mana komputer kuantum jelas lebih efisien dibandingkan komputer konvensional.
Apa selanjutnya
Saya sarankan kita akhiri di sini. Kami sudah melakukan pekerjaan dengan baik. Jika Anda telah memahami semua yang saya bahas, saya rasa Anda sekarang memiliki pemahaman yang baik tentang dasar-dasar komputasi kuantum dan logika kuantum, dan mengapa algoritma kuantum bisa lebih efisien daripada komputasi tradisional dalam situasi tertentu.
Deskripsi saya hampir tidak dapat disebut sebagai panduan lengkap tentang komputasi dan algoritma kuantum - melainkan pengenalan singkat tentang matematika dan notasi, yang dirancang untuk menghilangkan gagasan pembaca tentang subjek yang dipaksakan oleh sumber-sumber sains populer (serius, banyak yang benar-benar tidak dapat memahaminya. situasi!). Saya tidak punya waktu untuk menyentuh banyak topik penting, seperti , kompleksitas nilai amplitudo |0⟩ dan |1⟩ dan fungsi berbagai elemen logika kuantum selama transformasi oleh bola Bloch.
Jika Anda ingin mensistematisasikan dan menyusun pengetahuan Anda tentang komputer kuantum, dengan kuat Saya sarankan Anda membaca Emma Strubel: meskipun banyak sekali rumus matematika, buku ini membahas algoritma kuantum dengan lebih detail.
Sumber: www.habr.com