QAOA skala utilitas

Tonton video tentang QAOA skala utilitas dari Olivia Lanes, atau buka video di jendela terpisah di YouTube.

Gambaran umum pelajaran:

Sejauh ini dalam kursus ini, kami berharap telah memberimu fondasi yang kuat tentang kerangka dan alat yang diperlukan untuk memecahkan masalah skala utilitas pada komputer kuantum. Sekarang, kita akhirnya akan melihat alat-alat ini beraksi.

Dalam pelajaran ini, kita akan kotor tangan dengan contoh skala utilitas dari masalah Max-Cut, yang merupakan masalah terkenal dalam teori graf yang melibatkan cara terbaik untuk mempartisi graf menjadi dua. Kita akan mulai dengan graf lima simpul sederhana untuk membangun intuisi tentang bagaimana komputer kuantum bisa membantu kita memecahkan masalah, kemudian terapkan ini ke versi skala utilitas dari masalah tersebut.

Pelajaran ini akan berfungsi sebagai gambaran umum yang luas tentang pendekatan yang kita ambil untuk memecahkan masalah ini. Ini bukan panduan kode. Menyertai pelajaran ini, bagaimanapun, ada tutorial dengan kode aktual yang bisa kamu jalankan untuk memecahkan masalah Max-Cut pada komputer kuantum.

Masalahnya

Sebagai pengingat, tidak semua masalah komputasi cocok untuk komputasi kuantum. "Masalah mudah" tidak akan mendapatkan keuntungan apa pun dari teknologi ini karena komputer klasik sudah sangat baik dalam menyelesaikannya.

Tiga kasus penggunaan yang paling kita optimis untuk dieksplorasi adalah:

1. mensimulasikan alam
2. memproses data dengan struktur yang kompleks
3. optimasi

Hari ini, kita akan berfokus pada kasus penggunaan ketiga, optimasi. Dalam masalah optimasi, kita umumnya mencari nilai terbesar atau terkecil yang mungkin untuk fungsi yang diberikan. Kesulitan menemukan ekstrem ini dengan metode klasik bisa meningkat secara eksponensial seiring ukuran masalah tumbuh.

Masalah optimasi yang menarik hari ini disebut Max-Cut, yang akan kita selesaikan menggunakan algoritma bernama Quantum Approximate Optimization Algorithm (QAOA).

Apa itu Max-Cut?

Kita mulai dengan sebuah graf, yang terdiri dari kumpulan simpul (atau node), beberapa di antaranya terhubung oleh tepi. Dalam masalah ini, kita diminta untuk membagi node dari graf menjadi dua himpunan bagian dengan "memotong" tepi yang menghubungkannya. Kita ingin menemukan partisi yang memaksimalkan jumlah tepi yang dipotong dengan cara ini – karenanya nama, "Max-Cut."

Misalnya, gambar di atas menunjukkan graf lima simpul dengan solusi Max-cut di sebelah kanan. Ini memotong melalui lima tepi, yang merupakan yang terbaik yang bisa dilakukan dengan graf ini.

Karena graf lima simpul sangat kecil, tidak terlalu sulit untuk mengerjakan Max-Cut di kepala kamu atau dengan mencoba beberapa potongan di selembar kertas. Tapi seperti yang bisa kamu bayangkan, masalah ini menjadi semakin sulit seiring jumlah simpul tumbuh — sebagian karena jumlah kemungkinan potongan yang perlu dipertimbangkan tumbuh secara eksponensial dalam jumlah node. Dan pada titik tertentu, ini menjadi sulit bahkan untuk superkomputer dengan algoritma klasik mana pun yang diketahui.

Kita ingin cara untuk memecahkan masalah Max-Cut untuk graf yang lebih besar dan lebih rumit ini, karena masalah memiliki banyak aplikasi praktis, termasuk deteksi penipuan dalam keuangan, pengelompokan graf, desain jaringan, dan analisis media sosial. Max-Cut sering ditemui sebagai submasalah dalam pendekatan tertentu untuk masalah yang lebih besar. Jadi, ini jauh lebih umum dari yang mungkin kita pikirkan secara naif.

Solusinya

Sekarang, kita akan memandu pendekatan yang kita gunakan untuk memecahkan masalah Max-Cut pada komputer kuantum. Kita akan melakukan ini dengan graf lima simpul sederhana. Kamu bisa mengikuti menggunakan tutorial notebook python. Setelah contoh sederhana itu, tutorial akan memandumu melalui contoh skala utilitas dari masalah tersebut.

Langkah pertama adalah membuat graf kita dengan mendefinisikan jumlah node dan tepi yang menghubungkan dua node. Kamu bisa melakukan ini dengan mengimpor paket yang disebut rustworkx, seperti yang didemonstrasikan dalam tutorial. Hasilnya akan berupa graf yang terlihat seperti ini:

Kita akan menggunakan kerangka Qiskit patterns untuk menemukan solusi Max-Cut untuk graf ini pada komputer kuantum kita.

Peta

Kita perlu memetakan masalah ke komputer kuantum kita. Untuk melakukan ini, mari kita catat terlebih dahulu bahwa memaksimalkan jumlah potongan dalam sebuah graf bisa ditulis secara matematis 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 node dalam graf, dan $x_i$ dan $x_j$ adalah 0 atau 1, bergantung pada sisi partisi mana setiap node berada (satu grup diberi label "0" dan satu diberi label "1"). Ketika $x_i$ dan $x_j$ berada di sisi yang sama dari partisi, ekspresi dalam jumlah sama dengan nol. Ketika mereka berada di sisi yang berlawanan, sehingga ada potongan di antara mereka, ekspresinya sama dengan satu. Jadi, memaksimalkan jumlah potongan akan memaksimalkan jumlahnya.

Kita juga bisa membalikkan ini, dan mencari minimum dengan mengalikan 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 siap untuk memetakan. Bisa sedikit menakutkan untuk memikirkan cara pergi dari graf seperti yang baru kita gambar ke Circuit kuantum. Tapi kita akan melakukannya satu langkah pada satu waktu.

Ingat, kita akan mencoba memecahkan Max-Cut menggunakan QAOA. Dalam metodologi QAOA, kita pada akhirnya ingin memiliki operator (atau dengan kata lain Hamiltonian) yang akan digunakan untuk mewakili fungsi biaya dari algoritma hibrida kita, serta Circuit yang diparametrikan (ansatz) yang kita gunakan untuk mewakili solusi yang mungkin untuk masalah tersebut.

QUBO

Kita bisa mengambil sampel dari solusi kandidat ini dan kemudian mengevaluasinya menggunakan fungsi biaya. Untuk melakukan ini, kita memanfaatkan serangkaian reformulasi matematis, termasuk notasi Quadratic Unconstrained Binary Optimization — atau QUBO singkatnya — yang merupakan cara berguna untuk mengkodekan masalah optimasi kombinatorial. Dalam QUBO, kita ingin menemukan:

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

di mana $Q$ adalah matriks $n\times n$ dari bilangan real, $n$ sesuai dengan jumlah node dalam graf kita, di sini, lima.

Untuk menerapkan QAOA, kita perlu memformulasikan masalah kita sebagai Hamiltonian — yang merupakan fungsi atau matriks yang mewakili total energi dari suatu sistem. Secara khusus, kita ingin membuat Hamiltonian fungsi biaya yang memiliki sifat bahwa ground state sesuai dengan nilai minimum fungsi. Jadi, untuk memecahkan masalah optimasi kita, kita akan mencoba menyiapkan ground state dari $H$ pada komputer kuantum. Kemudian, mengambil sampel dari keadaan ini akan menghasilkan solusi untuk $\min 𝑓(𝑥)$ dengan probabilitas tinggi.

Pemetaan ke Hamiltonian fungsi biaya

Ternyata, kita beruntung, karena masalah QUBO sangat erat kaitannya dengan, dan sebenarnya setara secara komputasi dengan, salah satu Hamiltonian yang paling terkenal dan ada di mana-mana dalam fisika: Hamiltonian Ising.

Untuk menulis masalah QUBO sebagai Hamiltonian Ising, yang sebenarnya kita lakukan hanyalah melakukan perubahan variabel sederhana:

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

Kita tidak akan membahas semua langkah di sini, tetapi dijelaskan dalam notebook yang terlampir. Pada akhirnya, minimasi ekspresi QUBO sama dengan minimasi ekspresi ini:

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

Menulis ulang sedikit lagi dan kita memiliki Hamiltonian fungsi biaya, di mana minimum ekspresi mewakili ground state, Z adalah operator Pauli Z, dan $b$ adalah koefisien skalar real:

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

Sekarang kita memiliki Hamiltonian, kita perlu menulisnya ulang dalam hal operator Pauli ZZ dua-lokal, yang bisa dengan mudah kita konversi ke Gate dua qubit dalam Circuit kuantum kita. Kita akan berakhir dengan enam objek — atau string Pauli — di mana masing-masing sesuai dengan setiap enam tepi dalam graf. Setiap elemen dari lima elemen dalam string mewakili operasi pada node — identitas jika node tidak terhubung ke tepi tertentu tersebut, dan operator Pauli Z jika ya. Dalam Qiskit, bitstring yang mewakili qubit diindeks terbalik. Misalnya, tepi antara node 0 dan 1 dikodekan sebagai IIIZZ, dan tepi antara 2 dan 4 dikodekan sebagai ZIZII.

Bangun Circuit kuantum

Dengan Hamiltonian yang ditulis dalam hal operator Pauli, kita siap untuk membangun Circuit kuantum, yang memungkinkan kita mengambil sampel solusi yang baik menggunakan komputer kuantum:

Algoritma QAOA mengambil inspirasi dari Teorema Adiabatik, yang menyatakan bahwa jika kita mulai dalam ground state dari Hamiltonian yang bergantung waktu, jika Hamiltonian berevolusi cukup lambat, dan dengan cukup waktu, keadaan akhir akan menjadi ground state dari Hamiltonian akhir. QAOA bisa dianggap sebagai versi diskrit dan trotterisasi dari Algoritma Adiabatik Kuantum ini, di mana setiap langkah trotter mewakili lapisan dari algoritma QAOA. Jadi alih-alih berevolusi dari satu keadaan ke yang lain, di setiap lapisan, kita akan beralih bolak-balik antara Hamiltonian fungsi biaya kita dan apa yang disebut Hamiltonian "mixer", yang akan kita bahas nanti dalam pelajaran ini.

Keunggulan QAOA adalah lebih cepat dari algoritma adiabatik kuantum, tetapi mengembalikan solusi perkiraan bukan yang optimal. Dalam batas di mana jumlah lapisan mendekati tak terhingga, QAOA menyatu ke kasus QAA, tetapi tentu saja ini sangat mahal secara komputasi.

Untuk membuat Circuit kuantum kita, kita akan menerapkan operator bergantian, yang diparametrikan oleh $\gamma$ dan $\beta$, yang akan mewakili diskritisasi evolusi waktu.

Jadi, tiga bagian utama dari Circuit QAOA adalah:

1. keadaan percobaan awal, dalam abu-abu, yang merupakan ground state dari mixer, dibuat dengan menerapkan Gate Hadamard ke setiap qubit
2. evolusi fungsi biaya, yang telah kita bahas sebelumnya, dalam ungu gelap
3. evolusi di bawah Hamiltonian mixer, yang belum kita bahas, dalam ungu muda.

Hamiltonian awal kita disebut Mixer karena ground state-nya adalah superposisi dari semua bitstring yang mungkin diminati: karenanya memaksakan campuran dari semua solusi yang mungkin di awal.

Hamiltonian mixer adalah jumlah sederhana dari operasi Pauli-X pada setiap node dari graf. Qiskit memungkinkan kamu menggunakan operator mixer kustom yang berbeda jika kamu mau, tetapi kita akan menggunakan yang standar di sini. Jadi sekali lagi, kamu bisa melihat bahwa dengan Qiskit, banyak pekerjaan dihilangkan untuk kita, membuat pembuatan Hamiltonian mixer dan keadaan awal menjadi mudah. Satu-satunya pekerjaan yang harus kita lakukan adalah menemukan fungsi biaya.

Setiap iterasi dari operator-operator ini disebut lapisan. Lapisan-lapisan ini bisa dilihat sebagai diskritisasi dari evolusi waktu sistem, seperti yang dijelaskan sebelumnya. Pola bergantian berasal dari dekomposisi trotter dan mendekati fungsi eksponensial dari matriks yang tidak komut. Secara umum, semakin banyak lapisan atau langkah yang kita sertakan, semakin dekat kita akan ke evolusi waktu kontinu, seperti dalam QAA, sehingga secara teoritis, semakin akurat hasilnya. Tapi untuk contoh ini, kita akan mulai dengan mengambil sampel dengan satu lapisan. Ingat, baik Hamiltonian fungsi biaya maupun mixer diparametrikan, kita masih perlu menemukan nilai optimal untuk $\gamma$ dan $\beta.$

Optimalkan

Sementara Circuit yang baru saja kita buat terlihat cukup sederhana dan berguna untuk membangun pemahaman intuitif, ingat, chip kuantum tidak memahami apa itu Gate QAOA. Kita perlu mengubah ini menjadi serangkaian Gate satu dan dua qubit "native" yang bisa dilakukan langsung pada perangkat keras. Gate native adalah yang bisa dilakukan langsung pada qubit. Circuit seperti itu dikatakan ditulis dalam Instruction Set Architecture (ISA) Backend.

Pustaka Qiskit menawarkan serangkaian pass transpilasi yang melayani berbagai transformasi Circuit. Kita ingin memastikan bahwa Circuit dioptimalkan untuk tujuan kita.

Ingat dari pelajaran sebelumnya bahwa proses transpilasi melibatkan beberapa langkah:

• Pemetaan awal qubit dalam Circuit (yaitu, variabel keputusan) ke qubit fisik pada perangkat.
• Unrolling instruksi dalam Circuit kuantum ke instruksi native perangkat keras yang dipahami Backend.
• Perutean qubit mana pun dalam Circuit yang berinteraksi ke qubit fisik yang berdekatan satu sama lain.

Dan seperti biasa, lebih rinci tentang ini bisa ditemukan dalam dokumentasi.

Sebelum transpilasi, bagaimanapun, kita perlu memilih Backend mana yang akan kita jalankan Circuit kita, karena transpiler mengoptimalkan secara berbeda untuk prosesor yang berbeda. Ini adalah alasan lain mengapa penting untuk menggunakan transpiler otomatis — kamu tidak ingin melewati proses optimasi Circuit yang memakan waktu dengan tangan, hanya untuk menyadari kamu sebenarnya ingin menjalankan Circuit di prosesor berbeda dengan properti berbeda.

Lewatkan Backend pilihanmu melalui fungsi transpiler dan tentukan level optimasimu. Dalam tutorial, kamu akan memilih level 3, yang merupakan level tertinggi dan paling menyeluruh.

Dan dengan itu, kita memiliki Circuit yang ditranspilasi yang siap untuk dieksekusi pada perangkat keras!

Eksekusi

Sejauh ini, kita mentranspilasi Circuit dengan membiarkan parameter gamma dan beta sendiri — tetapi kita tidak bisa benar-benar menjalankan Circuit tanpa menentukan parameter-parameter ini. Dalam alur kerja QAOA, parameter QAOA yang optimal ditemukan dalam loop optimasi iteratif, di mana kita menjalankan serangkaian evaluasi Circuit dan kemudian menggunakan optimizer klasik untuk menemukan parameter $\beta$ dan $\gamma$ yang optimal. Namun, kita perlu memulai dari suatu tempat, jadi kita membuat tebakan awal $\gamma=\pi/2$ dan $\beta=\pi.$

Mode Eksekusi

Sekarang, kita hampir siap untuk menjalankan Circuit — saya janji! Tapi pertama, penting untuk dicatat bahwa kamu bisa mengirim pekerjaanmu dengan berbagai cara yang berbeda, yang disebut mode eksekusi.

• Mode pekerjaan: Satu permintaan primitif dari Estimator atau Sampler dibuat tanpa manajer konteks. Circuit dan input dikemas sebagai primitive unified blocs (PUBs) dan dikirimkan sebagai tugas eksekusi pada komputer kuantum.

• Mode batch: Manajer multi-pekerjaan untuk menjalankan eksperimen yang terdiri dari kumpulan pekerjaan independen secara efisien. Gunakan mode batch untuk mengirimkan beberapa pekerjaan primitif secara bersamaan.

• Mode Session: Jendela yang didedikasikan untuk menjalankan beban kerja multi-pekerjaan. Ini memungkinkan pengguna bereksperimen dengan algoritma variasional dengan cara yang lebih dapat diprediksi, dan bahkan menjalankan beberapa eksperimen secara bersamaan, memanfaatkan paralelisme dalam tumpukan. Gunakan Session untuk beban kerja iteratif atau eksperimen yang memerlukan akses khusus. Lihat Run jobs in a session untuk contoh.

Untuk eksperimen QAOA, Session akan menjadi pilihan yang baik untuk dilanjutkan jika kamu memiliki akses ke sana, karena kita perlu mengambil sampel Circuit berkali-kali dengan nilai parameter yang berbeda untuk menemukan optimalnya.

Kembali ke masalah optimasi. Kita perlu menemukan nilai gamma dan beta yang lebih baik dari sekadar tebakan awal kasar kita. Kita akan melakukan ini dengan menghubungkan fungsi biaya dan tebakan awal ini ke optimizer scipy COBYLA.

Di sini kamu bisa melihat nilai fungsi biaya selama iterasi. Dimulai sedikit tidak menentu dan naik turun, tetapi kemudian menetap pada nilai yang rendah. Kita akan menggunakan nilai yang ditemukan scipy yang sesuai dengan evaluasi terendah dari fungsi biaya.

Sekarang setelah kita bisa mengurangi fungsi biaya dengan menemukan nilai yang lebih baik untuk parameter kita, kita akan menjalankan Circuit dengan nilai baru yang kita temukan untuk gamma dan beta. Saya mencantumkan nilai spesifik yang saya gunakan di sini, tetapi ingat, ketika kamu mencoba ini atau bahkan hanya menjalankan ulang tutorial notebook yang sama, nilai-nilai ini mungkin sedikit berubah. Sekarang kita akan menjalankan Circuit yang dioptimalkan dengan nilai-nilai ini dan menemukan solusi kandidat untuk masalah Max-Cut kita.

Dalam tahap pasca-pemrosesan, kita akan menganalisis data dan menampilkan hasil ini untuk melihat apakah algoritma kuantum kita menemukan solusi yang benar.

Pasca-proses

Sekarang mari kita plot histogram dari data untuk melihat solusi akhir:

Bitstring mewakili bagaimana setiap node dipartisi menjadi dua grup (diberi label "0" dan "1") oleh potongan tersebut. Seharusnya ada empat solusi yang semuanya memberikan nilai maksimum tepi yang dipotong. Keempat ini ditampilkan dalam ungu. Kamu bisa segera melihat bahwa 4 solusi jauh lebih mungkin dari yang lainnya. Solusi bitstring tertinggi, dan dengan demikian paling mungkin adalah 0,1,0,1,1. (Ingat – urutan qubit dibalik dalam bitstring plot!)

Dari plot ini, kita bisa mengambil bitstring yang paling mungkin dan mewakilinya sebagai graf yang dipartisi, dengan potongan melewati lima tepi:

Jadi, ini memang merupakan solusi Max-Cut. Tapi bukan satu-satunya! Karena simetri graf ini, ada beberapa solusi yang benar. Alih-alih memiliki node 0 dan 3 berada di dalam potongan, kita bisa memiliki node 2 dan 4 yang dimasukkan. Kamu bisa melihat bahwa yang harus saya lakukan hanyalah memutar potongan saya untuk menyertakan titik-titik baru ini. Jumlah tepi yang dipotong tetap lima. Ternyata ada empat solusi max cut, karena setiap solusi dari dua solusi yang kita catat juga memiliki "mitra" yang berlawanan, di mana node ungu berwarna abu-abu dan node abu-abu berwarna ungu – sehingga potongan tetap sama, tetapi setiap node secara efektif berpindah ke sisi yang berlawanan dari partisi.

Mari kita lihat lagi histogram dan empat solusi yang paling mungkin untuk sesaat. Idealnya, mereka masing-masing akan menjadi empat solusi Max-Cut yang benar. Masalahnya adalah bahwa algoritma sebenarnya tidak mengidentifikasi solusi keempat dan terakhir sebagai salah satu dari 4 jawaban yang paling mungkin. Itu adalah yang kelima paling mungkin. Solusi keempat yang diidentifikasi oleh algoritma salah--jika kamu menggambarnya, kamu akan melihat bahwa solusinya hanya memiliki empat potongan.

Tapi ingat: ini adalah algoritma perkiraan. Ini tidak sempurna, dan tidak benar 100% dari waktu. Kamu memang harus menggunakan pengetahuan dan pemahamanmu sendiri untuk memeriksa kewajarannya pada solusi.

Kesalahan ini bisa muncul dari beberapa tempat:

1. Bisa jadi sifat perkiraan dari algoritma itu sendiri, dan jumlah lapisan kecil yang saya gunakan.
2. Bisa jadi kesalahan pengambilan sampel yang terbatas, ini bisa dikurangi jika saya meningkatkan jumlah shot dalam eksperimen saya.
3. Bisa juga kesalahan readout, karena solusi nyata keempat hanya berbeda satu bit.

Jenis analisis kesalahan ini adalah yang diperlukan untuk menjadi praktisi komputasi kuantum. Kamu perlu memahami kinerja perangkat keras dan bagaimana ini bisa berkontribusi pada jenis kesalahan tertentu dan cara mengoreksinya.

Namun, jangan lupa bahwa ada 32 bitstring yang mungkin, dan bahwa empat solusi nyata termasuk dalam lima kandidat terbaik. Dan kita hanya menggunakan dua lapisan untuk menemukan ini. Secara umum, jika kita ingin meningkatkan peluang menemukan Max-Cut terbaik setiap saat, kita bisa meningkatkan kedalaman lapisan. Ada beberapa kehalusan di sini, tetapi itu untuk pelajaran berikutnya.

Pada skala utilitas

Sekarang setelah kamu mendapat gambaran tentang proses memecahkan masalah Max-Cut kecil pada komputer kuantum, saya menantang kamu untuk melakukannya pada skala. Ikuti di tutorial yang tertaut untuk melihat berapa banyak potongan yang bisa kamu dapatkan dalam graf 125 simpul.