QAOA berskala utiliti

Tonton video tentang QAOA berskala utiliti daripada Olivia Lanes, atau buka video dalam tetingkap berasingan di YouTube.

Gambaran pelajaran:

Setakat ini dalam kursus ini, kita berharap telah memberi anda asas yang kukuh bagi rangka kerja dan alat yang diperlukan untuk menyelesaikan masalah berskala utiliti pada komputer kuantum. Sekarang, akhirnya kita akan melihat alat-alat ini beraksi.

Dalam pelajaran ini, kita akan mengotorkan tangan kita dengan contoh berskala utiliti bagi masalah Max-Cut, yang merupakan masalah terkenal dalam teori graf yang melibatkan cara terbaik untuk membahagikan graf kepada dua. Kita akan mulakan dengan graf lima-nod yang mudah untuk membina intuisi kita tentang cara komputer kuantum boleh membantu kita menyelesaikan masalah, kemudian menggunakannya pada versi berskala utiliti masalah.

Pelajaran ini akan berfungsi sebagai gambaran luas tentang pendekatan yang kita ambil untuk menyelesaikan masalah ini. Ini bukan panduan kod. Mengiringi pelajaran ini, bagaimanapun, terdapat tutorial dengan kod sebenar yang boleh anda jalankan untuk menyelesaikan masalah Max-Cut pada komputer kuantum.

Masalah

Sebagai peringatan, tidak semua masalah pengkomputeran sesuai untuk pengkomputeran kuantum. "Masalah mudah" tidak akan mendapat sebarang kelebihan daripada teknologi ini kerana komputer klasik sudah cukup baik untuk menyelesaikannya.

Tiga kes penggunaan yang paling kita optimistik untuk diterokai adalah:

1. mensimulasi alam semesta
2. memproses data dengan struktur yang kompleks
3. pengoptimuman

Hari ini, kita akan memberi tumpuan kepada kes penggunaan ketiga, pengoptimuman. Dalam masalah pengoptimuman, kita secara amnya mencari nilai terbesar atau terkecil yang mungkin bagi fungsi yang diberikan. Kesukaran mencari nilai ekstrem ini dengan kaedah klasik boleh meningkat secara eksponen apabila saiz masalah berkembang.

Masalah pengoptimuman yang diminati hari ini dipanggil Max-Cut, yang akan kita selesaikan menggunakan algoritma yang dipanggil Quantum Approximate Optimization Algorithm (QAOA).

Apakah Max-Cut?

Kita mulakan dengan graf, yang terdiri daripada koleksi bucu (atau nod), sesetengahnya disambungkan oleh tepi. Dalam masalah, kita diminta untuk membahagikan nod graf kepada dua subset dengan "memotong" tepi yang menyambungkan mereka. Kita ingin mencari pembahagian yang memaksimumkan bilangan tepi yang dipotong dengan cara ini — oleh itu nama, "Max-Cut."

Sebagai contoh, rajah di atas menunjukkan graf lima-nod dengan penyelesaian Max-cut di sebelah kanan. Ia memotong melalui lima tepi, yang merupakan yang terbaik yang boleh dilakukan dengan graf ini.

Oleh kerana graf lima-nod begitu kecil, tidak terlalu sukar untuk mengira Max-Cut dalam kepala anda atau dengan mencuba beberapa potongan pada sekeping kertas. Tetapi seperti yang boleh anda bayangkan, masalah menjadi semakin sukar apabila bilangan bucu bertambah — sebahagiannya kerana bilangan potongan yang mungkin untuk dipertimbangkan berkembang secara eksponen dalam bilangan nod. Dan pada titik tertentu, ini menjadi sukar walaupun untuk superkomputer dengan mana-mana algoritma klasik yang diketahui.

Kita mahukan cara untuk menyelesaikan masalah Max-Cut untuk graf yang lebih besar dan lebih rumit ini, kerana masalah ini mempunyai banyak aplikasi praktikal, termasuk pengesanan penipuan dalam kewangan, pengelompokan graf, reka bentuk rangkaian, dan analisis media sosial. Max-Cut sering ditemui sebagai submasalah dalam pendekatan tertentu kepada masalah yang lebih besar. Jadi, ia jauh lebih biasa daripada yang kita mungkin fikir secara naif.

Penyelesaian

Sekarang, kita akan menjalani pendekatan yang kita gunakan untuk menyelesaikan masalah Max-Cut pada komputer kuantum. Kita akan melakukan ini dengan graf lima-nod yang mudah. Anda boleh mengikut menggunakan tutorial buku nota python. Selepas contoh mudah itu, tutorial akan membawa anda melalui contoh berskala utiliti masalah.

Langkah pertama adalah untuk mencipta graf kita dengan mentakrifkan bilangan nod dan tepi yang menyambungkan dua nod. Anda boleh melakukan ini dengan mengimport pakej yang dipanggil rustworkx, seperti yang ditunjukkan dalam tutorial. Hasilnya akan menjadi graf yang kelihatan seperti ini:

Kita akan menggunakan rangka kerja corak Qiskit untuk mencari penyelesaian Max-Cut untuk graf ini pada komputer kuantum kita.

Peta

Kita perlu memetakan masalah ke komputer kuantum kita. Untuk melakukan ini, mari kita perhatikan terlebih dahulu bahawa memaksimumkan bilangan potongan dalam graf boleh ditulis secara matematik sebagai:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

Di mana $i$ dan $j$ adalah nod dalam graf, dan $x_i$ dan $x_j$ adalah sama ada 0 atau 1, bergantung pada sisi pembahagian mana setiap nod berada (satu kumpulan dilabelkan "0" dan satu dilabelkan "1"). Apabila $x_i$ dan $x_j$ berada pada sisi pembahagian yang sama, ungkapan dalam jumlah adalah sama dengan sifar. Apabila mereka berada pada sisi yang bertentangan, jadi ada potongan di antara mereka, ungkapan adalah sama dengan satu. Jadi, memaksimumkan bilangan potongan akan memaksimumkan jumlah.

Kita juga boleh membalikkan ini, dan mencari minimum dengan mendarabkan setiap nilai dengan negatif satu.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

Sekarang, kita bersedia untuk memetakan. Agak menakutkan untuk memikirkan cara pergi dari graf seperti yang baru kita lukis ke Circuit kuantum. Tetapi kita akan ambil satu langkah pada satu masa.

Ingat, kita akan cuba menyelesaikan Max-Cut menggunakan QAOA. Dalam metodologi QAOA, kita akhirnya ingin mempunyai operator (atau dengan kata lain Hamiltonian) yang akan digunakan untuk mewakili fungsi kos algoritma hibrid kita, serta Circuit berparameter (ansatz) yang kita gunakan untuk mewakili penyelesaian yang mungkin kepada masalah.

QUBO

Kita boleh mengambil sampel dari penyelesaian calon ini dan kemudian menilainya menggunakan fungsi kos. Untuk melakukan ini, kita mengambil kesempatan daripada siri reformulasi matematik, termasuk notasi Quadratic Unconstrained Binary Optimization — atau QUBO dalam ringkasan — yang merupakan cara yang berguna untuk mengekod masalah pengoptimuman kombinatorial. Dalam QUBO, kita ingin mencari:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

di mana $Q$ adalah matriks $n\times n$ bagi nombor nyata, $n$ sepadan dengan bilangan nod dalam graf kita, di sini, lima.

Untuk menggunakan QAOA, kita perlu memformulasikan masalah kita sebagai Hamiltonian — yang merupakan fungsi atau matriks yang mewakili jumlah tenaga sistem. Secara khusus, kita ingin mencipta Hamiltonian fungsi kos yang mempunyai sifat bahawa keadaan dasar sepadan dengan nilai minimum fungsi. Jadi, untuk menyelesaikan masalah pengoptimuman kita, kita akan cuba menyediakan keadaan dasar $H$ pada komputer kuantum. Kemudian, pensampelan dari keadaan ini akan menghasilkan penyelesaian untuk $\min 𝑓(𝑥)$ dengan kebarangkalian yang tinggi.

Pemetaan ke Hamiltonian fungsi kos

Rupanya, kita bernasib baik, kerana masalah QUBO sangat berkaitan rapat dengan, dan sebenarnya setara secara pengkomputeran dengan, salah satu Hamiltonian yang paling terkenal dan lazim dalam fizik: Hamiltonian Ising.

Untuk menulis masalah QUBO sebagai Hamiltonian Ising, yang sebenarnya perlu kita lakukan hanyalah melakukan perubahan pemboleh ubah yang mudah:

$$x_i = \frac{1-z_i}{2}.$$

Kita tidak akan menjalani semua langkah di sini, tetapi ia diterangkan dalam buku nota yang dilampirkan. Akhirnya, minimisasi ungkapan QUBO adalah sama dengan minimisasi ungkapan ini:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Menulis semula sedikit lagi dan kita mempunyai Hamiltonian fungsi kos kita, di mana minimum ungkapan mewakili keadaan dasar, Z adalah operator Pauli Z, dan $b$ adalah pekali skalar nyata:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Kini setelah kita mempunyai Hamiltonian kita, kita perlu menulisnya semula dalam terma operator Pauli ZZ dua-setempat, yang boleh kita tukar dengan mudah ke Gate dua-qubit dalam Circuit kuantum kita. Kita akan berakhir dengan enam objek — atau rentetan Pauli — di mana setiap satu sepadan dengan setiap enam tepi dalam graf. Setiap daripada lima elemen dalam rentetan mewakili operasi pada nod — identiti jika nod tidak disambungkan ke tepi tertentu, dan operator Pauli Z jika ia. Dalam Qiskit, rentetan bit yang mewakili qubit diindeks secara terbalik. Sebagai contoh, tepi antara nod 0 dan 1 dikodkan sebagai IIIZZ, dan tepi antara 2 dan 4 dikodkan sebagai ZIZII.

Bina Circuit kuantum

Dengan Hamiltonian kita ditulis dalam terma operator Pauli, kita bersedia untuk membina Circuit kuantum kita, yang membolehkan kita mengambil sampel penyelesaian yang baik menggunakan komputer kuantum:

Algoritma QAOA mengambil inspirasi daripada Teorem Adiabatik, yang menyatakan bahawa jika kita bermula dalam keadaan dasar Hamiltonian yang bergantung masa, jika Hamiltonian berevolusi dengan cukup perlahan, dan diberi masa yang cukup, keadaan akhir akan menjadi keadaan dasar Hamiltonian akhir. QAOA boleh difikirkan sebagai versi diskret, trotterisasi dari Algoritma Adiabatik Kuantum ini, di mana setiap langkah trotter mewakili lapisan algoritma QAOA. Jadi daripada berevolusi dari satu keadaan ke yang lain, dalam setiap lapisan, kita akan bertukar antara Hamiltonian fungsi kos kita dan apa yang dipanggil Hamiltonian "pengadun", yang akan kita liputi kemudian dalam pelajaran ini.

Kelebihan QAOA adalah bahawa ia lebih cepat daripada algoritma adiabatik kuantum, tetapi ia mengembalikan penyelesaian yang hampir dan bukannya optimum. Dalam had di mana bilangan lapisan pergi ke infiniti, QAOA menumpu ke kes QAA, tetapi tentu saja ini sangat mahal dari segi pengkomputeran.

Untuk mencipta Circuit kuantum kita, kita akan menggunakan operator berselang-seli, yang diparameterkan oleh $\gamma$ dan $\beta$, yang akan mewakili diskretisasi evolusi masa.

Jadi, tiga bahagian utama Circuit QAOA adalah:

1. keadaan percubaan awal, dalam kelabu, yang merupakan keadaan dasar pengadun, dicipta dengan menggunakan Gate Hadamard yang digunakan pada setiap qubit
2. evolusi fungsi kos, yang telah kita bincangkan sebelumnya, dalam ungu gelap
3. evolusi di bawah Hamiltonian pengadun, yang belum kita liputi lagi, dalam ungu cerah.

Hamiltonian permulaan kita dipanggil Pengadun kerana keadaan dasarnya adalah superposisi semua rentetan bit yang mungkin diminati: oleh itu mewujudkan campuran semua penyelesaian yang mungkin pada permulaan.

Hamiltonian pengadun adalah jumlah mudah operasi Pauli-X pada setiap nod graf. Qiskit membolehkan anda menggunakan operator pengadun tersuai yang berbeza jika anda mahu, tetapi kita akan menggunakan yang standard di sini. Jadi sekali lagi, anda boleh melihat bahawa dengan Qiskit, banyak kerja dibuang untuk kita, menjadikan pencarian Hamiltonian pengadun dan keadaan permulaan adalah mudah. Satu-satunya kerja yang perlu kita lakukan adalah mencari fungsi kos.

Setiap ulangan operator-operator ini dipanggil lapisan. Lapisan-lapisan ini boleh dilihat sebagai diskretisasi evolusi masa sistem, seperti yang diterangkan sebelumnya. Corak berselang-seli datang dari penguraian trotter dan menghampiri fungsi eksponen bagi matriks yang tidak bertukar. Secara umum, semakin banyak lapisan atau langkah yang kita sertakan, semakin dekat kita dengan evolusi masa berterusan, seperti dalam QAA, jadi secara teorinya, semakin tepat hasilnya. Tetapi untuk contoh ini, kita akan mulakan dengan hanya mengambil sampel dengan satu lapisan. Ingat, kedua-dua Hamiltonian fungsi kos dan pengadun adalah berparameter, kita masih perlu mencari nilai optimum untuk $\gamma$ dan $\beta.$

Optimumkan

Walaupun Circuit yang baru kita cipta kelihatan agak mudah dan berguna untuk membina pemahaman intuitif, ingat, cip kuantum tidak faham apa itu Gate QAOA. Kita perlu mengubah ini menjadi satu siri Gate "asli" satu- dan dua-qubit yang boleh dilakukan secara langsung pada perkakasan. Gate asli adalah yang boleh dilakukan secara langsung pada qubit. Circuit sedemikian dikatakan ditulis dalam Instruction Set Architecture (ISA) Backend.

Perpustakaan Qiskit menawarkan satu siri laluan transpilasi yang memenuhi pelbagai transformasi Circuit. Kita ingin memastikan bahawa Circuit dioptimumkan untuk tujuan kita.

Ingat dari pelajaran sebelumnya kita bahawa proses transpilasi melibatkan beberapa langkah:

• Pemetaan awal qubit dalam Circuit (iaitu pemboleh ubah keputusan) ke qubit fizikal pada peranti.
• Pembongkaran arahan dalam Circuit kuantum ke arahan asli perkakasan yang difahami oleh Backend.
• Penghalaan mana-mana qubit dalam Circuit yang berinteraksi ke qubit fizikal yang bersebelahan antara satu sama lain.

Dan seperti biasa, lebih banyak butiran tentang ini boleh didapati dalam dokumentasi.

Sebelum transpilasi, bagaimanapun, kita perlu memilih Backend mana yang akan kita jalankan Circuit kita, kerana Transpiler mengoptimumkan secara berbeza untuk pemproses yang berbeza. Ini adalah sebab lain mengapa penting untuk menggunakan Transpiler automatik — anda tidak mahu melalui proses mengoptimumkan Circuit anda secara manual yang memakan masa, hanya untuk menyedari anda sebenarnya ingin menjalankan Circuit anda pada pemproses yang berbeza dengan sifat yang berbeza.

Hantar Backend pilihan anda melalui fungsi Transpiler dan tentukan tahap pengoptimuman anda. Dalam tutorial, anda akan memilih tahap 3, yang merupakan tahap tertinggi dan paling menyeluruh.

Dan dengan itu, kita mempunyai Circuit yang ditranspilasi yang bersedia untuk dilaksanakan pada perkakasan!

Laksanakan

Setakat ini, kita mentranspilasikan Circuit meninggalkan parameter gamma dan beta sahaja — tetapi kita sebenarnya tidak boleh menjalankan Circuit tanpa menentukan parameter ini. Dalam aliran kerja QAOA, parameter QAOA yang optimum ditemui dalam gelung pengoptimuman berulang, di mana kita menjalankan satu siri penilaian Circuit dan kemudian menggunakan pengoptimum klasik untuk mencari parameter 𝛽 dan 𝛾 yang optimum. Walau bagaimanapun, kita perlu bermula di suatu tempat, jadi kita membuat tekaan awal $\gamma=\pi/2$ dan $\beta=\pi.$

Mod Pelaksanaan

Sekarang, kita hampir bersedia untuk menjalankan Circuit — saya janji! Tetapi pertama, adalah penting untuk ambil perhatian bahawa anda boleh menghantar kerja anda dalam pelbagai cara yang berbeza, yang dipanggil mod pelaksanaan.

• Mod kerja: Permintaan primitif tunggal bagi Estimator atau Sampler dibuat tanpa pengurus konteks. Circuit dan input dimuatkan sebagai blok bersatu primitif (PUB) dan diserahkan sebagai tugas pelaksanaan pada komputer kuantum.

• Mod kelompok: Pengurus pelbagai-kerja untuk menjalankan eksperimen dengan cekap yang terdiri daripada kumpulan kerja bebas. Gunakan mod kelompok untuk menyerahkan beberapa kerja primitif secara serentak.

• Mod Session: Tetingkap khusus untuk menjalankan beban kerja pelbagai-kerja. Ini membolehkan pengguna bereksperimen dengan algoritma variasi dengan cara yang lebih boleh diramalkan, dan malah menjalankan beberapa eksperimen secara serentak, memanfaatkan kesejarahan dalam tindanan. Gunakan Session untuk beban kerja berulang atau eksperimen yang memerlukan akses khusus. Lihat Jalankan kerja dalam Session untuk contoh.

Untuk eksperimen QAOA, Session adalah pilihan yang baik untuk diteruskan jika anda mempunyai akses kepadanya, kerana kita perlu mengambil sampel Circuit kita berkali-kali dengan nilai parameter yang berbeza untuk mencari optimum.

Kembali kepada masalah pengoptimuman. Kita perlu mencari nilai gamma dan beta yang lebih baik daripada sekadar tekaan kasar pertama kita. Kita akan melakukan ini dengan memasukkan fungsi kos kita dan tekaan awal ini ke dalam pengoptimum scipy COBYLA.

Di sini anda dapat melihat nilai fungsi kos sepanjang ulangan. Ia bermula sedikit pelik dan naik turun, tetapi kemudian menstabil kepada nilai yang rendah. Kita akan menggunakan nilai yang ditemui scipy yang sepadan dengan penilaian terendah fungsi kos.

Kini setelah kita dapat mengurangkan fungsi kos kita dengan mencari nilai yang lebih baik bagi parameter kita, kita akan menjalankan Circuit kita menggunakan nilai baharu yang kita temui untuk gamma dan beta. Saya menyenaraikan nilai khusus yang saya gunakan di sini, tetapi ingat, apabila anda mencuba ini atau malah sekadar menjalankan semula buku nota tutorial yang sama, nilai-nilai ini mungkin berubah sedikit. Sekarang kita akan menjalankan Circuit yang dioptimumkan kita dengan nilai-nilai ini dan mencari penyelesaian calon kita kepada masalah Max-Cut kita.

Dalam peringkat pasca-pemprosesan, kita akan menganalisis data dan memaparkan keputusan ini untuk melihat sama ada algoritma kuantum kita menemui penyelesaian yang betul.

Pasca-proses

Sekarang mari kita plot histogram data untuk melihat penyelesaian akhir:

Rentetan bit mewakili cara setiap nod dibahagikan kepada dua kumpulan (dilabelkan "0" dan "1") oleh potongan. Sepatutnya ada empat penyelesaian yang semuanya memberikan nilai maksimum tepi yang dipotong. Empat ini ditunjukkan dalam ungu. Anda dapat melihat serta-merta bahawa 4 penyelesaian jauh lebih mungkin berbanding yang lain. Penyelesaian rentetan bit tertinggi, dan dengan demikian paling mungkin adalah 0,1,0,1,1. (Ingat – susunan qubit adalah terbalik dalam rentetan bit plot!)

Daripada plot ini, kita boleh mengambil rentetan bit yang paling mungkin dan mewakilinya sebagai graf yang dibahagikan, dengan potongan melalui lima tepi:

Jadi, ini memang penyelesaian Max-Cut. Tetapi bukan satu-satunya! Kerana simetri graf ini, terdapat beberapa penyelesaian yang betul. Daripada mempunyai nod 0 dan 3 berada di dalam potongan, kita boleh mempunyai nod 2 dan 4 disertakan. Anda dapat melihat bahawa yang perlu saya lakukan hanyalah memutar potongan saya untuk menyertakan titik-titik baharu ini. Bilangan tepi yang dipotong kekal lima. Ternyata ada empat penyelesaian Max-Cut, kerana setiap dua penyelesaian yang kita catat juga mempunyai "pasangan" bertentangan, di mana nod ungu adalah kelabu dan nod kelabu adalah ungu — jadi potongan kekal sama, tetapi setiap nod secara berkesan bertukar ke sisi pembahagian yang bertentangan.

Mari kita lihat sekali lagi histogram dan empat penyelesaian yang paling mungkin sebentar. Sebaik-baiknya, ia akan menjadi masing-masing daripada empat penyelesaian Max-Cut yang sebenar. Masalahnya adalah bahawa algoritma sebenarnya tidak mengenal pasti penyelesaian keempat dan terakhir sebagai salah satu daripada 4 jawapan yang paling mungkin. Ia adalah yang kelima paling mungkin. Penyelesaian keempat yang dikenal pasti oleh algoritma adalah tidak betul--jika anda melukisnya, anda akan melihat bahawa penyelesaian hanya mempunyai empat potongan.

Tetapi ingat: ini adalah algoritma yang hampir. Ia tidak mudah tertipu, dan ia tidak betul 100% sepanjang masa. Anda memang perlu menggunakan beberapa pengetahuan dan pemahaman anda sendiri untuk memeriksa kesahihan penyelesaian.

Ralat ini boleh timbul dari beberapa tempat:

1. Ia mungkin sifat hampir algoritma itu sendiri, dan bilangan lapisan kecil yang saya gunakan.
2. Ia mungkin ralat pensampelan terhingga, ini boleh dikurangkan jika saya meningkatkan bilangan tembakan dalam eksperimen saya.
3. Ia juga mungkin ralat pembacaan, kerana penyelesaian sebenar keempat hanya berbeza sebanyak satu bit.

Jenis analisis ralat inilah yang diperlukan untuk menjadi pengamal pengkomputeran kuantum. Anda perlu memahami prestasi perkakasan dan bagaimana ini boleh menyumbang kepada jenis ralat tertentu dan cara membetulkannya.

Walau bagaimanapun, jangan lupa bahawa terdapat 32 rentetan bit yang mungkin, dan bahawa empat penyelesaian sebenar termasuk dalam lima calon terbaik. Dan kita hanya menggunakan dua lapisan untuk mencari ini. Secara umum, jika kita ingin meningkatkan peluang menemui Max-Cut terbaik setiap kali, kita boleh meningkatkan kedalaman lapisan. Terdapat beberapa kehalusan untuk ini, tetapi itu untuk pelajaran kemudian.

Pada skala utiliti

Kini setelah anda mendapat gambaran proses menyelesaikan masalah Max-Cut kecil pada komputer kuantum, saya mencabar anda untuk melakukannya pada skala. Ikuti dalam tutorial yang dipautkan untuk melihat berapa banyak potongan yang boleh anda dapatkan dalam graf 125-nod.