Demistifikasi prinsip-prinsip komputasi kuantum

"Saya pikir saya bisa mengatakan bahwa tidak ada yang mengerti mekanika kuantum," kata Richard Feynman

Topik komputasi kuantum selalu menarik penulis teknis dan jurnalis. Potensi dan kompleksitas komputasinya memberinya semacam lingkaran mistis. Terlalu sering artikel tematik dan infografis menjelaskan secara rinci semua jenis prospek untuk industri ini, sementara hampir tidak menyentuh masalah penerapan praktisnya: ini mungkin menyesatkan pembaca yang tidak terlalu berhati-hati.

Dalam artikel sains populer, deskripsi sistem kuantum dihilangkan dan pernyataan seperti:

Bit reguler dapat sama dengan "1" atau "0", tetapi qubit dapat secara bersamaan sama dengan "1" dan "0".

Jika Anda sangat beruntung (yang saya tidak yakin), maka mereka akan memberi tahu Anda bahwa:

Qubit berada dalam superposisi antara "1" dan "0".

Tidak satu pun dari penjelasan ini yang masuk akal, karena kami mencoba merumuskan fenomena kuantum-mekanis menggunakan alat bahasa yang dibuat dalam dunia yang sangat tradisional. Untuk menjelaskan dengan jelas prinsip-prinsip komputasi kuantum, perlu menggunakan bahasa lain - matematika.

Dalam panduan ini, saya akan berbicara tentang alat matematika yang diperlukan untuk memodelkan dan memahami sistem komputasi kuantum, dan bagaimana mengilustrasikan dan menerapkan logika komputasi kuantum. Selain itu, saya akan memberikan contoh algoritma kuantum dan memberi tahu apa keunggulannya dibandingkan komputer tradisional.

Saya akan melakukan yang terbaik untuk membicarakan semua ini dalam bahasa yang dapat dimengerti, tetapi saya tetap berharap para pembaca artikel ini memiliki ide dasar tentang aljabar linier dan logika digital (aljabar linier dijelaskan di sini , logika digital ada di sini ).

Untuk memulai, mari kita membahas prinsip-prinsip logika digital. Ini didasarkan pada penggunaan sirkuit listrik untuk perhitungan. Untuk membuat uraian kami lebih abstrak, kami menyederhanakan status kawat menjadi "1" atau "0", yang akan sesuai dengan status "hidup" atau "mati". Setelah membangun transistor dalam urutan tertentu, kami akan membuat apa yang disebut elemen logika yang mengambil satu atau lebih nilai dari sinyal input dan mengubahnya menjadi sinyal output berdasarkan aturan logika Boolean tertentu.

Elemen logika umum dan tabel status

Atas dasar rantai elemen-elemen dasar seperti itu, dimungkinkan untuk membuat elemen-elemen yang lebih kompleks, dan atas dasar rantai elemen-elemen yang lebih kompleks pada akhirnya kita dapat mengandalkan untuk mendapatkan analog dari prosesor sentral dengan tingkat abstrak yang tinggi.

Seperti yang saya sebutkan sebelumnya, kita perlu cara untuk memetakan 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 adalah notasi vektor Dirac . Dengan mewakili bit kami dengan cara ini, kami dapat memodelkan operasi logis pada bit menggunakan transformasi vektor. Harap dicatat: terlepas dari kenyataan bahwa ketika menggunakan dua bit dalam elemen logika, Anda dapat melakukan banyak operasi ("DAN" (DAN), "Tidak" (TIDAK), "Kecualikan Atau" (XOR), dll.), Saat menggunakan satu bit dimungkinkan untuk melakukan hanya empat operasi: konversi identitas, negasi, perhitungan konstanta "0" dan perhitungan konstanta "1". Selama konversi yang identik, bit tetap tidak berubah, ketika dinegasikan, nilai bit dibalik (dari "0" menjadi "1" atau dari "1" ke "0"), dan perhitungan konstanta "1" atau "0" mengatur bit ke "1" atau "0" terlepas dari nilai sebelumnya.


Berdasarkan representasi bit baru kami, sangat mudah untuk melakukan operasi pada bit yang sesuai menggunakan transformasi vektor:



Sebelum melanjutkan, mari kita lihat konsep komputasi reversibel , yang hanya menyiratkan bahwa untuk memastikan reversibilitas suatu operasi atau elemen logis, perlu untuk menentukan daftar nilai sinyal input berdasarkan sinyal output dan nama-nama operasi yang digunakan. Dengan demikian, kita dapat menyimpulkan bahwa transformasi identitas dan negasi dapat dibalik, tetapi operasi penghitungan konstanta "1" dan "0" tidak. Karena keunikan mekanika kuantum, komputer kuantum menggunakan operasi yang dapat dibalik secara eksklusif, itulah sebabnya kami akan fokus pada mereka. Selanjutnya, kita akan mengonversi elemen ireversibel menjadi yang reversibel untuk memastikan bahwa elemen tersebut dapat digunakan oleh komputer kuantum.

Menggunakan produk tensor dari bit individual, banyak bit dapat direpresentasikan:

Sekarang kita memiliki hampir semua konsep matematika yang diperlukan, kita akan beralih ke elemen logika kuantum pertama kita. Ini adalah operator CNOT , atau "TIDAK" yang dikendalikan, yang sangat penting dalam komputasi reversibel dan kuantum. Elemen CNOT diterapkan pada dua bit dan mengembalikan dua bit. Bit pertama ditugaskan sebagai "kontrol", dan yang kedua - "kontrol". Jika bit kontrol diatur ke "1", bit kontrol mengubah nilainya; jika bit kontrol diatur ke “0”, bit kontrol tidak berubah.

Operator ini dapat direpresentasikan sebagai vektor transformasi berikut:

Untuk mendemonstrasikan semua yang telah kita bahas, saya akan menunjukkan kepada Anda bagaimana menggunakan elemen CNOT sehubungan dengan banyak bit:

Kami meringkas apa yang telah dikatakan: dalam contoh pertama, kami menguraikan | 10⟩ menjadi bagian-bagian dari produk tensornya dan menggunakan matriks CNOT untuk mendapatkan keadaan produk yang sesuai baru; maka kita faktor ke | 11⟩ sesuai dengan tabel nilai CNOT yang diberikan sebelumnya.

Jadi, kami mengingat semua aturan matematika yang akan membantu kami menangani perhitungan tradisional dan bit biasa, dan akhirnya kami dapat beralih ke komputasi kuantum dan qubit modern.

Jika Anda membaca di tempat ini, maka saya punya kabar baik untuk Anda: qubit dapat dengan mudah diungkapkan secara matematis. Secara umum, jika bit klasik (cbit) dapat diatur ke | 1⟩ atau | 0⟩, qubit hanya dalam superposisi dan dapat sama dengan | 0⟩ dan | 1⟩ sebelum pengukuran. Setelah pengukuran, itu runtuh di | 0⟩ atau | 1⟩. Dengan kata lain, qubit dapat direpresentasikan sebagai kombinasi linear dari | 0⟩ dan | 1⟩ sesuai dengan rumus di bawah ini:

di mana a₀ dan a₁ masing-masing mewakili amplitudo | 0⟩ dan | 1⟩. Mereka dapat dianggap sebagai "probabilitas kuantum", yang mewakili probabilitas qubit runtuh ke salah satu negara setelah pengukurannya, karena dalam mekanika kuantum objek dalam superposisi runtuh menjadi salah satu keadaan setelah diperbaiki. Luaskan ekspresi ini dan dapatkan yang berikut:

Untuk menyederhanakan penjelasan saya, saya akan menggunakan gagasan ini dalam artikel ini.

Untuk qubit ini, peluang jebol ke a₀ setelah pengukuran adalah | a ₀ | ², dan kemungkinan jatuh menjadi ₁ sama dengan | a ₁ | ². Misalnya, untuk qubit berikut:

peluang runtuhnya "1" adalah | 1 / √2 | ², atau ½, yaitu, 50/50.

Karena dalam sistem klasik semua probabilitas dalam penjumlahan harus memberikan kesatuan (untuk distribusi probabilitas penuh), kita dapat menyimpulkan bahwa kuadrat dari nilai absolut amplitudo | 0⟩ dan | 1⟩ harus berjumlah satu. Berdasarkan informasi ini, kita dapat menyusun persamaan berikut:

Jika Anda terbiasa dengan trigonometri, Anda akan melihat bahwa persamaan ini sesuai dengan teorema Pythagoras (a² + b² = c²), yaitu, kita dapat secara grafik mewakili kemungkinan keadaan qubit dalam bentuk titik pada lingkaran unit, yaitu:

Operator dan elemen logis diterapkan pada qubit dan juga dalam kasus bit klasik - berdasarkan transformasi matriks. Semua operator matriks reversibel yang kita ingat sampai saat ini, khususnya, CNOT, dapat digunakan untuk bekerja dengan qubit. Operator matriks semacam itu memungkinkan untuk menggunakan masing-masing amplitudo suatu qubit tanpa mengukur dan menciutkannya. Biarkan saya memberi Anda contoh menggunakan operator negasi untuk qubit:

Sebelum kita melanjutkan, saya ingat bahwa amplitudo a ₀ dan ₁ sebenarnya adalah bilangan kompleks , sehingga keadaan qubit dapat paling akurat ditampilkan pada unit sphere tiga dimensi, juga dikenal sebagai sphere Bloch :

Namun, untuk menyederhanakan penjelasan, di sini kita membatasi diri pada bilangan real.

Tampaknya sudah tiba saatnya untuk membahas beberapa elemen logis yang masuk akal secara eksklusif 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 menciutkannya menjadi "1" atau "0" setelah pengukuran.

Perhatikan bahwa ada angka negatif di sisi kanan bawah operator Hadamard. Ini disebabkan oleh fakta bahwa hasil penggunaan operator tergantung pada nilai sinyal input: - | 1⟩ atau | 0⟩, dan oleh karena itu perhitungannya dapat dibalik.

Poin penting lain yang terkait dengan elemen Hadamard adalah reversibilitasnya, yaitu dapat mengambil qubit di superposisi yang sesuai dan mengubahnya menjadi | 0⟩ atau | 1⟩.

Ini sangat penting karena memungkinkan kita untuk berubah dari keadaan kuantum tanpa menentukan keadaan qubit - dan, dengan demikian, tanpa menciutkannya. Jadi, kita dapat menyusun komputasi kuantum berdasarkan prinsip deterministik dan bukan probabilistik.

Operator kuantum yang berisi bilangan real eksklusif adalah kebalikannya, sehingga kami dapat menyajikan hasil penerapan operator ke qubit sebagai transformasi dalam lingkaran unit dalam bentuk mesin keadaan:

Dengan demikian, qubit, keadaan yang ditunjukkan pada diagram di atas, setelah menerapkan operasi Hadamard dikonversi ke keadaan yang ditunjukkan oleh panah yang sesuai. Demikian pula, kita dapat membangun mesin negara lain yang akan menggambarkan transformasi qubit menggunakan operator negasi, seperti yang ditunjukkan di atas (juga dikenal sebagai operator negasi Pauli, atau bit inversi), seperti yang ditunjukkan di bawah ini:

Untuk melakukan operasi yang lebih kompleks dengan qubit kami, Anda dapat menggunakan rantai banyak operator atau menerapkan elemen berkali-kali. Contoh transformasi serial berdasarkan representasi rantai kuantum adalah sebagai berikut:

Yaitu, jika kita mulai dengan bit | 0⟩, menerapkan kebalikan dari bit, dan kemudian operasi Hadamard, lalu inversi bit lain, dan lagi operasi Hadamard, setelah inversi bit terakhir, kita mendapatkan vektor di sisi kanan rantai. Dengan menempatkan berbagai mesin negara di atas satu sama lain, kita bisa mulai dengan | 0⟩ dan melacak panah berwarna yang sesuai dengan masing-masing transformasi untuk memahami bagaimana semua ini bekerja.

Karena kita sudah sejauh ini, saatnya untuk mempertimbangkan salah satu jenis algoritma kuantum, yaitu algoritma Deutsch-Joji , dan menunjukkan keunggulannya dibandingkan komputer klasik. Perlu dicatat bahwa algoritma Deutsch-Yogi sepenuhnya deterministik, yaitu, ia mengembalikan jawaban yang benar dalam 100% kasus (tidak seperti banyak algoritma kuantum lainnya berdasarkan pada penentuan probabilistik qubit).

Mari kita bayangkan bahwa Anda memiliki kotak hitam yang berisi fungsi / operator pada satu bit (ingat - ketika menggunakan satu bit, hanya empat operasi yang mungkin: secara identik mengubah, meniadakan, menghitung konstanta "0" dan menghitung konstanta "1"). Fungsi apa yang dilakukan dalam kotak? Anda tidak tahu yang mana, namun, Anda dapat memilah sebanyak varian nilai input yang Anda inginkan dan mengevaluasi hasilnya pada output.


Berapa banyak sinyal input dan output yang harus didorong melalui kotak hitam untuk mengetahui fungsi mana yang digunakan? Pikirkan sebentar.

Dalam kasus komputer klasik, Anda harus membuat 2 kueri untuk menentukan fungsi yang digunakan. Misalnya, jika ketika Anda memasukkan "1" kita mendapatkan "0" pada output, menjadi jelas bahwa fungsi untuk menghitung konstanta "0" atau fungsi negasi digunakan, setelah itu Anda harus mengubah nilai sinyal input menjadi "0" dan melihat apa yang terjadi di pintu keluar.

Dalam kasus komputer kuantum, Anda juga akan memerlukan dua kueri, karena Anda masih membutuhkan dua nilai output yang berbeda untuk menentukan fungsi persis yang berlaku pada nilai input. Namun, jika kita merumuskan kembali sedikit pertanyaan, ternyata komputer kuantum masih memiliki keunggulan yang serius: jika Anda ingin mengetahui apakah fungsi yang digunakan adalah konstan atau variabel, keunggulan akan berada di sisi komputer kuantum.

Fungsi yang digunakan dalam kotak adalah variabel, jika nilai yang berbeda dari sinyal input memberikan hasil yang berbeda pada output (misalnya, konversi dan inversi bit yang identik), dan jika nilai output tidak berubah terlepas dari nilai input, maka fungsinya konstan (misalnya, menghitung konstanta "1" atau perhitungan konstanta "0").

Dengan menggunakan algoritma kuantum, Anda dapat menentukan apakah fungsi dalam kotak hitam adalah konstan atau variabel berdasarkan hanya satu permintaan. Tetapi sebelum kita memeriksa secara terperinci bagaimana melakukan ini, kita perlu menemukan cara yang akan memungkinkan kita untuk menyusun masing-masing fungsi ini pada komputer kuantum. Karena setiap operator kuantum harus dapat dibalik, kami segera menghadapi masalah: fungsi untuk menghitung konstanta "1" dan "0" tidak.

Dalam komputasi kuantum, solusi berikut sering digunakan: qubit output tambahan ditambahkan, yang mengembalikan nilai sinyal input yang diterima oleh fungsi.
Dengan demikian, kita dapat menentukan nilai input hanya berdasarkan nilai yang diperoleh pada output, dan fungsi menjadi tidak dapat dibalik. Struktur sirkuit kuantum menciptakan kebutuhan akan bit input tambahan. Demi mengembangkan operator yang sesuai, kami mengasumsikan bahwa input qubit tambahan diatur ke | 0⟩.

Menerapkan representasi yang sama dari rantai kuantum yang kita gunakan sebelumnya, kita akan melihat bagaimana masing-masing dari empat elemen (transformasi identitas, negasi, perhitungan konstanta "0" dan perhitungan konstanta "1") dapat diimplementasikan menggunakan operator kuantum.

Misalnya, Anda dapat mengimplementasikan fungsi untuk menghitung konstanta “0”:

Perhitungan konstanta "0":

Di sini kita tidak perlu operator sama sekali. Input qubit pertama (yang kami ambil sama dengan | 0⟩) ​​kembali dengan nilai yang sama, dan nilai input kedua mengembalikan dirinya sendiri - seperti biasa.

Dengan fungsi untuk menghitung konstanta "1", situasinya sedikit berbeda:

Perhitungan konstanta "1":

Karena kami menerima bahwa input qubit pertama selalu diatur ke | 0⟩, sebagai hasil dari penerapan operator inversi bit, ia selalu memberikan satu pada output. Dan seperti biasa, qubit kedua memberikan nilainya sendiri pada output.

Ketika operator transformasi identitas ditampilkan, tugas mulai menjadi lebih rumit. Inilah cara melakukannya:

Transformasi Identitas:

Simbol yang digunakan di sini menunjukkan elemen CNOT: garis atas menunjukkan bit kontrol, dan garis bawah menunjukkan bit kontrol. Biarkan saya mengingatkan Anda bahwa ketika menggunakan operator CNOT, nilai bit kontrol berubah jika bit kontrol | 1⟩, tetapi tetap tidak berubah jika bit kontrol | 0⟩. Karena kami mengasumsikan bahwa nilai baris atas selalu sama dengan | 0⟩, nilainya selalu ditetapkan ke baris bawah.

Demikian pula, kami bertindak dengan operator negasi:

Bantahan:

Kami cukup membalikkan bit di akhir jalur output.

Sekarang kita telah menemukan presentasi pendahuluan, mari kita lihat kelebihan spesifik dari komputer kuantum daripada komputer tradisional ketika harus menentukan kekonstanan atau variabilitas fungsi yang disembunyikan di dalam kotak hitam menggunakan hanya satu permintaan.

Untuk mengatasi masalah ini dengan menggunakan komputasi kuantum dalam satu permintaan, perlu menerjemahkan qubit input menjadi superposisi sebelum dipindahkan ke fungsi, seperti yang ditunjukkan di bawah ini:

Elemen Hadamard diterapkan kembali ke hasil penggunaan fungsi untuk mendapatkan qubit dari superposisi dan membuat algoritma deterministik. Kami memulai sistem di negara | 00⟩ dan untuk alasan yang akan saya bicarakan sekarang, kami mendapatkan hasilnya | 11⟩ jika fungsi yang digunakan konstan. Jika fungsi di dalam kotak hitam adalah variabel, maka setelah mengukur sistem mengembalikan hasilnya | 01⟩.

Untuk membahas sisa artikel, mari kita beralih ke ilustrasi yang saya tunjukkan sebelumnya:

Menggunakan operator inversi bit, dan kemudian menerapkan elemen Hadamard untuk kedua nilai input yang sama dengan | 0⟩, kami akan memastikan terjemahannya ke dalam superposisi yang sama | 0⟩ dan | 1⟩, yaitu:

Menggunakan contoh mentransfer nilai fungsi ini ke kotak hitam, mudah untuk menunjukkan bahwa kedua fungsi nilai konstan memberikan | 11⟩ ke output.

Perhitungan konstanta "0":

, , «1» |11⟩, :

«1»:

: |1⟩, -1² = 1.

, |01⟩ ( ), .

:

CNOT , , CNOT :

|01⟩, :

:

, , , .

?

. . , , , , , .

— , , , - (, !). — , , |0⟩ |1⟩ .

, « » (An Introduction to Quantum Algorithms) : , .