Algoritma Grover

Untuk modul Qiskit in Classrooms ini, siswa harus memiliki lingkungan Python yang berfungsi dengan paket-paket berikut terinstal:

• qiskit v2.1.0 atau lebih baru
• qiskit-ibm-runtime v0.40.1 atau lebih baru
• qiskit-aer v0.17.0 atau lebih baru
• qiskit.visualization
• numpy
• pylatexenc

Untuk mengatur dan menginstal paket-paket di atas, lihat panduan Install Qiskit. Untuk menjalankan job di komputer kuantum sungguhan, siswa perlu membuat akun di IBM Quantum® dengan mengikuti langkah-langkah dalam panduan Set up your IBM Cloud account.

Modul ini telah diuji dan menggunakan 12 detik waktu QPU. Ini adalah perkiraan itikad baik; penggunaan aktualmu bisa berbeda.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Pengantar

Algoritma Grover adalah algoritma kuantum fundamental yang menangani masalah pencarian tak terstruktur: diberikan sekumpulan $N$ item dan cara untuk memeriksa apakah suatu item adalah yang kamu cari, seberapa cepat kamu bisa menemukan item yang diinginkan? Dalam komputasi klasik, jika data tidak terurut dan tidak ada struktur yang bisa dimanfaatkan, pendekatan terbaik adalah memeriksa setiap item satu per satu, sehingga kompleksitas kueri menjadi $O(N)$ — rata-rata, kamu perlu memeriksa sekitar setengah item sebelum menemukan target.

Algoritma Grover, yang diperkenalkan oleh Lov Grover pada tahun 1996, menunjukkan bagaimana komputer kuantum bisa menyelesaikan masalah ini jauh lebih efisien, hanya membutuhkan $O(\sqrt{N})$ langkah untuk menemukan item yang ditandai dengan probabilitas tinggi. Ini merupakan percepatan kuadratik dibandingkan metode klasik, yang sangat signifikan untuk dataset besar.

Algoritma ini beroperasi dalam konteks berikut:

• Pengaturan masalah: Kamu punya fungsi $f(x)$ yang mengembalikan 1 jika $x$ adalah item yang kamu cari, dan 0 jika tidak. Fungsi ini sering disebut oracle atau kotak hitam, karena kamu hanya bisa mengetahui data dengan mengkueri $f(x)$.
• Kegunaan kuantum: Sementara algoritma klasik untuk masalah ini membutuhkan rata-rata $N/2$ kueri, algoritma Grover bisa menemukan solusi dalam sekitar $\pi\sqrt{N}/4$ kueri, yang jauh lebih cepat untuk $N$ yang besar.
• Cara kerjanya (secara garis besar):
  • Komputer kuantum pertama-tama membuat superposisi dari semua kemungkinan state, mewakili semua item yang mungkin sekaligus.
  • Kemudian secara berulang menerapkan serangkaian operasi kuantum (iterasi Grover) yang memperkuat probabilitas jawaban yang benar dan melemahkan yang lain.
  • Setelah cukup iterasi, pengukuran state kuantum menghasilkan jawaban yang benar dengan probabilitas tinggi.

Berikut adalah diagram yang sangat dasar dari algoritma Grover yang melewatkan banyak detail. Untuk diagram yang lebih rinci, lihat paper ini.

Beberapa hal yang perlu diperhatikan tentang algoritma Grover:

• Ini optimal untuk pencarian tak terstruktur: tidak ada algoritma kuantum yang bisa menyelesaikan masalah dengan kurang dari $O(\sqrt{N})$ kueri.
• Ini hanya memberikan percepatan kuadratik, bukan eksponensial — tidak seperti beberapa algoritma kuantum lainnya (misalnya, algoritma Shor untuk faktorisasi).
• Ini memiliki implikasi praktis, seperti berpotensi mempercepat serangan brute-force pada sistem kriptografi, meskipun percepatannya tidak cukup untuk memecahkan sebagian besar enkripsi modern sendirian.

Bagi mahasiswa sarjana yang familiar dengan konsep komputasi dasar dan model kueri, algoritma Grover menawarkan ilustrasi yang jelas tentang bagaimana komputasi kuantum bisa mengungguli pendekatan klasik untuk masalah tertentu, bahkan ketika peningkatannya "hanya" kuadratik. Ini juga berfungsi sebagai pintu masuk untuk memahami algoritma kuantum yang lebih canggih dan potensi lebih luas dari komputasi kuantum.

Amplifikasi amplitudo adalah algoritma kuantum serbaguna, atau subrutin, yang bisa digunakan untuk mendapatkan percepatan kuadratik atas sejumlah algoritma klasik. Algoritma Grover adalah yang pertama mendemonstrasikan percepatan ini pada masalah pencarian tak terstruktur. Memformulasikan masalah pencarian Grover membutuhkan fungsi oracle yang menandai satu atau lebih state basis komputasi sebagai state yang ingin kita temukan, dan Circuit amplifikasi yang meningkatkan amplitudo state yang ditandai, sehingga menekan state yang tersisa.

Di sini, kita mendemonstrasikan cara membuat oracle Grover dan menggunakan GroverOperator dari library Circuit Qiskit untuk dengan mudah mengatur instance pencarian Grover. Primitif Sampler runtime memungkinkan eksekusi Circuit Grover yang mulus.

Teori

Misalkan ada fungsi $f$ yang memetakan string biner ke satu variabel biner, artinya

$$f: \Sigma^n \rightarrow \Sigma$$

Satu contoh yang didefinisikan pada $\Sigma^6$ adalah

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

Contoh lain yang didefinisikan pada $\Sigma^{2n}$ adalah

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

Kamu ditugaskan untuk menemukan state kuantum yang sesuai dengan argumen $x$ dari $f(x)$ yang dipetakan ke 1. Dengan kata lain, temukan semua $\{x_1\}\in \Sigma^n$ sehingga $f(x_1)=1$ (atau jika tidak ada solusi, laporkan itu). Kita akan menyebut non-solusi sebagai $x_0$. Tentu saja, kita akan melakukan ini di komputer kuantum, menggunakan state kuantum, jadi berguna untuk mengekspresikan string biner ini sebagai state:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

Menggunakan notasi state kuantum (Dirac), kita mencari satu atau lebih state khusus $\{|x_1\rangle\}$ dalam sekumpulan $N=2^n$ state yang mungkin, di mana $n$ adalah jumlah qubit, dan dengan non-solusi yang dilambangkan $\{|x_0\rangle\}.$

Kita bisa menganggap fungsi $f$ sebagai oracle: kotak hitam yang bisa kita kueri untuk menentukan efeknya pada state $|x\rangle.$ Dalam praktiknya, kita sering tahu fungsinya, tetapi mungkin sangat rumit untuk diimplementasikan, artinya mengurangi jumlah kueri atau aplikasi $f$ bisa jadi penting. Atau, kita bisa membayangkan paradigma di mana satu orang mengkueri oracle yang dikontrol oleh orang lain, sehingga kita tidak tahu fungsi oracle, kita hanya tahu aksinya pada state tertentu dari kueri.

Ini adalah "masalah pencarian tak terstruktur", karena tidak ada yang istimewa dari $f$ yang membantu pencarian kita. Output tidak terurut dan solusi tidak diketahui mengelompok, dan seterusnya. Bayangkan buku telepon kertas lama sebagai analogi. Pencarian tak terstruktur ini seperti memindai buku itu mencari nomor tertentu, bukan seperti mencari dalam daftar nama yang diurutkan alfabetis.

Dalam kasus di mana satu solusi dicari, secara klasik, ini membutuhkan jumlah kueri yang linier terhadap $N$. Jelas kamu mungkin menemukan solusi pada percobaan pertama, atau kamu mungkin tidak menemukan solusi dalam $N-1$ tebakan pertama, sehingga kamu perlu mengkueri input ke-$N$ untuk melihat apakah ada solusi sama sekali. Karena fungsi tidak memiliki struktur yang bisa dimanfaatkan, kamu akan membutuhkan $N/2$ tebakan rata-rata. Algoritma Grover membutuhkan jumlah kueri atau komputasi $f$ yang skala seperti $\sqrt{N}.$

Sketsa Circuit dalam algoritma Grover

Panduan matematis lengkap dari algoritma Grover bisa ditemukan, misalnya, di Fundamentals of quantum algorithms, sebuah kursus oleh John Watrous di IBM Quantum Learning. Perlakuan singkat disediakan dalam lampiran di akhir modul ini. Tapi untuk sekarang, kita hanya akan meninjau struktur keseluruhan Circuit kuantum yang mengimplementasikan algoritma Grover.

Algoritma Grover bisa dipecah menjadi tahap-tahap berikut:

• Persiapan superposisi awal (menerapkan Hadamard Gate ke semua qubit)
• "Menandai" state target dengan pembalikan fase
• Tahap "difusi" di mana Hadamard Gate dan pembalikan fase diterapkan ke semua qubit.
• Kemungkinan pengulangan tahap penandaan dan difusi untuk memaksimalkan probabilitas pengukuran state target
• Pengukuran

Sering kali, Gate penanda $Z_f$ dan lapisan difusi yang terdiri dari $H,$ $Z_{\text{OR}},$ dan $H$ secara kolektif disebut sebagai "operator Grover". Dalam diagram ini, hanya satu pengulangan operator Grover yang ditampilkan.

Hadamard Gate $H$ sudah dikenal dan digunakan secara luas dalam komputasi kuantum. Hadamard Gate menciptakan state superposisi. Secara khusus, didefinisikan oleh

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

Operasinya pada state lain apa pun didefinisikan melalui linearitas. Secara khusus, lapisan Hadamard Gate memungkinkan kita untuk berpindah dari state awal dengan semua qubit dalam $|0\rangle$ (dilambangkan $|0\rangle^{\otimes n}$) ke state di mana setiap qubit memiliki beberapa probabilitas diukur dalam $|0\rangle$ atau $|1\rangle;$ ini memungkinkan kita menjelajahi ruang semua kemungkinan state secara berbeda dari komputasi klasik.

Sifat korolari penting dari Hadamard Gate adalah bahwa menerapkannya untuk kedua kali bisa membatalkan state superposisi tersebut:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Ini akan menjadi penting sebentar lagi.

Periksa pemahamanmu

Baca pertanyaan di bawah, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Dimulai dari definisi Hadamard Gate, tunjukkan bahwa penerapan Hadamard Gate kedua kali membatalkan superposisi seperti yang diklaim di atas.

Jawaban:

Ketika kita menerapkan X ke state $|+\rangle$, kita mendapatkan nilai +1 dan ke state $|-\rangle$ kita mendapatkan -1, jadi jika kita punya distribusi 50-50, kita akan mendapatkan nilai ekspektasi 0.

Gate $Z_\text{OR}$ kurang umum, dan didefinisikan menurut

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{if } x = 0^n \\ -|x\rangle & \text{if } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Terakhir, Gate $Z_f$ didefinisikan oleh

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Perhatikan efeknya adalah bahwa $Z_f$ membalik tanda pada state target di mana $f(x) = 1$ dan membiarkan state lain tidak terpengaruh.

Pada tingkat yang sangat tinggi dan abstrak, kamu bisa memikirkan langkah-langkah dalam Circuit dengan cara berikut:

• Lapisan Hadamard pertama: menempatkan qubit ke dalam superposisi semua kemungkinan state.
• $Z_f$: tandai state target dengan menambahkan tanda "-" di depan. Ini tidak langsung mengubah probabilitas pengukuran, tetapi mengubah bagaimana state target akan berperilaku pada langkah selanjutnya.
• Lapisan Hadamard lain: Tanda "-" yang diperkenalkan pada langkah sebelumnya akan mengubah tanda relatif antara beberapa suku. Karena Hadamard Gate mengubah satu campuran state komputasi $(|0\rangle+|1\rangle)/\sqrt{2}$ menjadi satu state komputasi, $|0\rangle,$ dan mengubah $(|0\rangle-|1\rangle)/\sqrt{2}$ menjadi $|1\rangle$, perbedaan tanda relatif ini sekarang mulai berperan dalam state apa yang diukur.
• Satu lapisan akhir Hadamard Gate diterapkan, lalu pengukuran dilakukan. Kita akan melihat secara lebih rinci bagaimana ini bekerja di bagian berikutnya.

Contoh

Untuk lebih memahami cara kerja algoritma Grover, mari kita berjalan melalui contoh kecil dua qubit. Ini bisa dianggap opsional bagi mereka yang tidak fokus pada mekanika kuantum dan notasi Dirac. Tapi bagi mereka yang berharap untuk bekerja secara substansial dengan komputer kuantum, ini sangat direkomendasikan.

Berikut adalah diagram Circuit dengan state kuantum yang berlabel di berbagai posisi. Perhatikan bahwa dengan hanya dua qubit, hanya ada empat kemungkinan state yang bisa diukur dalam keadaan apa pun: $|00\rangle$, $|01\rangle$, $|10\rangle$, dan $|11\rangle$.

Misalkan oracle ($Z_f$, tidak diketahui oleh kita) menandai state $|01\rangle$. Kita akan menelusuri aksi dari setiap set Gate kuantum, termasuk oracle, dan melihat distribusi kemungkinan state yang keluar saat pengukuran. Di awal sekali, kita punya

$$|\psi_0\rangle = |00\rangle$$

Menggunakan definisi Hadamard Gate, kita punya

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Sekarang oracle menandai state target:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Perhatikan bahwa dalam state ini, keempat kemungkinan hasil memiliki probabilitas yang sama untuk diukur. Semuanya memiliki bobot dengan besaran $1/2,$ artinya masing-masing memiliki $|1/2|^2=1/4$ peluang untuk diukur. Jadi meskipun state $|01\rangle$ ditandai melalui fase "-", ini belum menghasilkan peningkatan probabilitas pengukuran state tersebut. Kita lanjutkan dengan menerapkan lapisan Hadamard Gate berikutnya.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Menggabungkan suku-suku sejenis, kita menemukan

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Sekarang $Z_{\text{OR}}$ membalik tanda pada semua state kecuali $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

Dan terakhir, kita menerapkan lapisan terakhir Hadamard Gate:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Layak untuk mengerjakan penggabungan suku-suku ini sendiri untuk meyakinkan dirimu bahwa hasilnya memang:

$$|\psi_5\rangle =|01\rangle$$

Artinya, probabilitas mengukur $|01\rangle$ adalah 100% (tanpa adanya noise dan error) dan probabilitas mengukur state lain apa pun adalah nol.

Contoh dua qubit ini adalah kasus yang sangat bersih; algoritma Grover tidak selalu menghasilkan 100% peluang mengukur state target. Sebaliknya, ia akan memperkuat probabilitas mengukur state target. Juga, operator Grover mungkin perlu diulang lebih dari sekali.

Di bagian berikutnya, kita akan mempraktikkan algoritma ini menggunakan komputer kuantum IBM® yang sungguhan.

Gambaran geometris

Contoh dua qubit di atas menunjukkan bagaimana aljabarnya bekerja untuk kasus kecil, tetapi ada cara yang jauh lebih intuitif untuk memahami algoritma Grover: sebagai serangkaian refleksi geometris dalam bidang dua dimensi. Di bawah ini kita menggambarkan gambaran ini. Kamu juga bisa melihat kursus John Watrous Fundamentals of Quantum Algorithms untuk detail lebih lanjut.

Membangun bidang. Kita bisa menguraikan state superposisi awal $|\psi\rangle$ menjadi dua komponen. State yang benar — yang sedang kita cari — kita sebut $|A_1\rangle$. Setiap state lainnya, digabungkan bersama, kita sebut $|A_0\rangle$. Menurut definisi, $|A_1\rangle$ dan $|A_0\rangle$ saling ortogonal, sehingga kita bisa memplotnya sebagai sumbu tegak lurus dalam ruang dua dimensi abstrak. Karena $|\psi\rangle$ adalah kombinasi linier dari kedua komponen ini, ia berada pada sudut kecil $\theta$ terhadap sumbu $|A_0\rangle$ — dekat dengan $|A_0\rangle$, karena pada awalnya hanya sebagian kecil dari state yang berada pada komponen yang benar $|A_1\rangle$.

Refleksi. Fakta matematis kunci yang kita butuhkan adalah bahwa operator berbentuk

$$2|v\rangle\langle v| - I$$

merefleksikan setiap state terhadap sumbu yang didefinisikan oleh $|v\rangle.$ Untuk melihat mengapa, pertimbangkan dua kasus: state di sepanjang $|v\rangle$ dibiarkan tidak berubah, dan state tegak lurus terhadap $|v\rangle$ mendapatkan tandanya dibalik. State lain apa pun bisa diuraikan menjadi dua komponen ini, dan operator bertindak pada masing-masing sesuai — yang merupakan refleksi tentang $|v\rangle$ persis.

Ternyata baik oracle maupun langkah difusi dalam algoritma Grover bisa diekspresikan sebagai refleksi dalam gambaran geometris ini.

Oracle sebagai refleksi. Oracle membalik tanda state $|A_1\rangle$ dan membiarkan yang lainnya sendiri. Itu sama dengan refleksi terhadap sumbu $|A_0\rangle$.

Difusi sebagai refleksi. Sedikit lebih sulit untuk melihat bagaimana operator difusi juga merupakan refleksi. Operator difusinya adalah

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ sendiri merupakan refleksi terhadap state semua-nol, karena ia membalik tanda setiap state yang bukan $|0\rangle^{\otimes n}$. Ini bisa ditulis sebagai $2|0\rangle\langle 0| - I$. Lapisan Hadamard di sekitarnya secara efektif melakukan perubahan basis, mengubah sumbu refleksi. Ingat bahwa $H^{\otimes n}$ memetakan $|0\rangle^{\otimes n}$ ke superposisi seragam $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Karena Hadamard adalah inversnya sendiri, ekspresi penuh menjadi

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

yang merupakan refleksi terhadap $|u\rangle$. Karena $|u\rangle$ sangat dekat dengan $|\psi\rangle$ (keduanya hampir di sepanjang $|A_0\rangle$), refleksi kedua ini mengirimkan state ke sudut $2\theta$ dari posisi awalnya.

Rotasi sebesar $2\theta$. Efek gabungan dari dua refleksi ini adalah rotasi sebesar $2\theta$ menuju $|A_1\rangle$. Setiap iterasi berturutan dari operator Grover memutar state sebesar $2\theta$ lagi.

Jumlah iterasi optimal. Tujuan kita adalah memutar state sedekat mungkin ke $|A_1\rangle$, yang berarti memutar sekitar $\pi/2$ radian (seperempat putaran). Jika setiap iterasi berkontribusi $2\theta$, jumlah iterasi optimal $t$ memenuhi

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

Untuk satu solusi di antara $N$ state, sudut awal adalah $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (untuk $N$ besar). Substitusikan,

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

Inilah asal dari percepatan $\sqrt{N}$ yang terkenal: kita hanya membutuhkan $O(\sqrt{N})$ iterasi untuk mencapai target, daripada $O(N)$ pemeriksaan yang diperlukan oleh pencarian klasik.

Lebih umum lagi, jika ada $|A_1|$ state solusi di antara $N$ state total, jumlah iterasi optimal adalah

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

Perhatikan bahwa jika kamu menerapkan terlalu banyak iterasi, kamu akan memutar melewati $|A_1\rangle$ dan probabilitas menemukan target state akan mulai berkurang lagi. Menemukan jumlah iterasi yang tepat itu penting, meskipun pada hardware kuantum yang berderau jumlah optimal secara eksperimen mungkin berbeda dari rumus ideal ini.

Mengapa algoritma Grover berguna?

Pada titik ini kamu mungkin bertanya-tanya: kita baru saja membangun oracle yang menandai target state — tetapi untuk membangunnya, kita harus mengetahui target state. Jadi apa yang sebenarnya kita cari?

Ini adalah pertanyaan yang wajar, dan ada beberapa jawaban yang baik.

• Model kueri adalah alat teoritis. Model kueri komputasi tidak pernah dirancang untuk langsung praktis. Tujuannya adalah memberi kita cara yang bersih untuk menganalisis kompleksitas algoritmik dengan memisahkan masalah menjadi dua bagian: oracle, dan segalanya yang lain. Seberapa sulit pencarian, mengingat verifikasi gratis? Bagaimana jumlah kueri berskala dengan ukuran input? Ini adalah pertanyaan yang berguna meskipun tidak ada sistem nyata yang bekerja persis seperti ini.

• Kamu juga bisa menganggapnya sebagai aktivitas dua pihak: satu orang mengetahui target state dan membangun oracle; tugas orang lain adalah menemukan jawaban menggunakan oracle sebagai kotak hitam, tanpa mengintip ke dalamnya. Dalam Aktivitas 2 di bawah, kamu akan melakukan ini persis dengan seorang mitra.

• Amplifikasi amplitudo adalah subroutine yang sangat berguna. Meskipun demonstrasi pertama ini tampak melingkar, mekanisme yang mendasari — yang disebut amplifikasi amplitudo — muncul berulang kali dalam komputasi kuantum. Yang sebenarnya kita bangun di sini adalah intuisi untuk alat yang muncul sebagai subroutine dalam banyak algoritma kuantum yang lebih kompleks.

• Ada masalah di mana kamu bisa membangun oracle tanpa mengetahui jawabannya. Wawasan kuncinya adalah bahwa ada seluruh kelas masalah yang sangat sulit untuk menemukan solusi, tetapi sangat mudah untuk memeriksa bahwa solusi tertentu benar. Faktorisasi adalah satu contoh: diberikan hasil kali dua bilangan prima besar, sangat sulit untuk menentukan apa bilangan prima tersebut, tetapi setelah kamu memilikinya, kamu bisa dengan mudah mengalikannya bersama untuk memverifikasi. (Kita memiliki algoritma yang lebih baik dari Grover untuk faktorisasi secara khusus — lihat algoritma Shor — tetapi ini jauh dari satu-satunya masalah dengan fitur ini.) Sudoku, constraint satisfaction, dan bahkan game klasik Minesweeper semuanya adalah masalah yang sulit untuk diselesaikan tetapi mudah untuk diperiksa.

Mengapa itu relevan? Artinya kita bisa mengetahui semua kondisi dan persyaratan yang harus dipenuhi oleh solusi, dan kita bisa mengkodekan persyaratan tersebut ke dalam Circuit kuantum yang berfungsi sebagai oracle — meskipun kita tidak mengetahui solusinya sendiri. Algoritma Grover akan menemukannya untuk kita.

Dengan ide-ide ini dalam pikiran, mari kita berjalan melalui beberapa contoh. Kita akan mulai dengan contoh di mana state solusi ditentukan dengan jelas sehingga kita bisa mengikuti logika algoritma. Kita kemudian akan beralih ke aktivitas dua pihak, dan akhirnya ke contoh di mana oracle dibangun dari batasan masalah daripada dari pengetahuan jawaban.

Import umum dan pendekatan

Kita mulai dengan mengimpor beberapa paket yang diperlukan.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

Sepanjang tutorial ini dan lainnya, kita akan menggunakan kerangka kerja untuk komputasi kuantum yang dikenal sebagai "pola Qiskit", yang membagi alur kerja menjadi langkah-langkah berikut:

• Langkah 1: Petakan input klasik ke masalah kuantum
• Langkah 2: Optimalkan masalah untuk eksekusi kuantum
• Langkah 3: Eksekusi menggunakan Qiskit Runtime Primitives
• Langkah 4: Post-processing dan analisis klasik

Kita umumnya akan mengikuti langkah-langkah ini, meskipun kita tidak selalu akan melabelinya secara eksplisit.

Aktivitas 1: Temukan satu target state yang ditentukan

Langkah 1: Petakan input klasik ke masalah kuantum

Kita perlu gate phase query untuk memberikan fase keseluruhan (-1) pada solution state, dan membiarkan non-solution state tidak terpengaruh. Cara lain untuk mengatakannya adalah bahwa algoritma Grover membutuhkan oracle yang menentukan satu atau lebih marked computational basis state, di mana "marked" berarti state dengan fase -1. Ini dilakukan menggunakan controlled-Z gate, atau generalisasi multi-controlled-nya pada $N$ qubit. Untuk melihat cara kerjanya, perhatikan contoh spesifik bitstring {110}. Kita ingin Circuit yang beroperasi pada state $|\psi\rangle = |q_2,q_1,q_0\rangle$ dan menerapkan fase jika $|\psi\rangle = |011\rangle$ (di mana kita telah membalik urutan string biner, karena notasi di Qiskit yang menempatkan qubit paling tidak signifikan (biasanya 0) di sebelah kanan).

Jadi, kita ingin Circuit $Z_f$ yang melakukan

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Kita bisa menggunakan gate multiple control multiple target (MCMTGate) untuk menerapkan Z gate yang dikontrol oleh semua qubit (flip fase jika semua qubit berada di state $|1\rangle$). Tentu saja, beberapa qubit dalam state yang kita inginkan mungkin bernilai $|0\rangle$. Oleh karena itu, untuk qubit-qubit tersebut kita harus terlebih dahulu menerapkan X gate, lalu melakukan multiply-controlled Z gate, kemudian menerapkan X gate lagi untuk membatalkan perubahan kita. MCMTGate terlihat seperti ini:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Perhatikan bahwa banyak qubit mungkin terlibat dalam proses kontrol (di sini tiga qubit), tetapi tidak ada satu qubit pun yang ditetapkan sebagai target. Ini karena seluruh state mendapatkan tanda "-" keseluruhan (phase flip); gate tersebut mempengaruhi semua qubit secara setara. Ini berbeda dari banyak gate multi-qubit lainnya, seperti gate CX, yang memiliki satu qubit kontrol dan satu qubit target.

Dalam kode berikut, kita mendefinisikan gate phase query (atau oracle) yang melakukan apa yang baru saja kita jelaskan: menandai satu atau lebih input basis state yang ditentukan melalui representasi bitstringnya. Gate MCMT digunakan untuk mengimplementasikan multi-controlled Z-gate.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Sekarang kita pilih state "marked" tertentu sebagai target kita, dan terapkan fungsi yang baru saja kita definisikan. Mari lihat Circuit seperti apa yang dibuat.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Jika qubit 1-3 berada di state $|1\rangle$, dan qubit 0 awalnya di state $|0\rangle$, X gate pertama akan membalik qubit 0 ke $|1\rangle$ dan semua qubit akan berada di $|1\rangle.$ Ini berarti gate MCMT akan menerapkan perubahan tanda keseluruhan atau phase flip, seperti yang diinginkan. Untuk kasus lainnya, qubit 1-3 berada di state $|0\rangle$, atau qubit 0 dibalik ke state $|0\rangle$, dan phase flip tidak akan diterapkan. Kita melihat bahwa Circuit ini memang menandai state yang kita inginkan $|0111\rangle,$ atau bitstring {1110}. Operator Grover lengkap terdiri dari gate phase query (oracle), lapisan Hadamard, dan operator $Z_\text{OR}$. Kita bisa menggunakan grover_operator bawaan untuk membangun ini dari oracle yang kita definisikan di atas.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Seperti yang kita diskusikan dalam gambaran geometris di atas, kita mungkin perlu menerapkan operator Grover beberapa kali. Jumlah iterasi optimal $t$ untuk memaksimalkan amplitudo target state tanpa adanya noise adalah

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

di mana $|A_1|$ adalah jumlah solution state dan $N=2^n$ adalah jumlah total state. Pada komputer kuantum modern yang berderau, jumlah iterasi optimal secara eksperimen mungkin berbeda — tetapi di sini kita hitung dan gunakan jumlah optimal secara teoritis menggunakan $|A_1|=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

Sekarang mari kita buat Circuit yang mencakup Hadamard gate awal untuk membuat superposisi dari semua state yang mungkin, dan terapkan operator Grover sejumlah iterasi optimal.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Kita telah membangun Grover Circuit kita!

Langkah 2: Optimalkan masalah untuk eksekusi hardware kuantum

Kita telah mendefinisikan Circuit kuantum abstrak kita, tetapi kita perlu menulisnya ulang dalam hal gate yang bersifat native untuk komputer kuantum yang sebenarnya ingin kita gunakan. Kita juga perlu menentukan qubit mana di komputer kuantum yang harus digunakan. Karena alasan-alasan ini dan lainnya, kita sekarang harus men-transpile Circuit kita. Pertama, mari kita tentukan komputer kuantum yang ingin kita gunakan.

Ada kode di bawah untuk menyimpan kredensial kamu saat pertama kali menggunakan. Pastikan kamu menghapus informasi ini dari notebook setelah menyimpannya ke lingkunganmu, sehingga kredensialmu tidak terekspos secara tidak sengaja saat kamu berbagi notebook. Lihat Set up your IBM Cloud account dan Initialize the service in an untrusted environment untuk panduan lebih lanjut.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Sekarang kita gunakan preset pass manager untuk mengoptimalkan Circuit kuantum kita untuk Backend yang dipilih.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Perlu dicatat bahwa kedalaman Circuit kuantum yang di-transpile cukup substansial.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

Ini sebenarnya angka yang cukup besar, bahkan untuk kasus sederhana ini. Karena semua gate kuantum (terutama gate dua qubit) mengalami error dan tunduk pada noise, serangkaian lebih dari 100 gate dua qubit akan menghasilkan tidak lebih dari noise jika qubitnya tidak memiliki performa yang sangat tinggi. Mari kita lihat bagaimana performa mereka.

Langkah 3: Eksekusi menggunakan Qiskit primitives

Kita ingin melakukan banyak pengukuran dan melihat state mana yang paling mungkin. Amplifikasi amplitudo seperti ini adalah masalah sampling yang cocok untuk dieksekusi dengan primitive Qiskit Runtime Sampler.

Perlu dicatat bahwa metode run() dari Qiskit Runtime SamplerV2 menerima iterable dari primitive unified blocks (PUB). Untuk Sampler, setiap PUB adalah iterable dalam format (circuit, parameter_values). Namun, minimal, ia menerima daftar Circuit kuantum.

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Untuk memaksimalkan pengalaman ini, kami sangat menyarankan kamu menjalankan eksperimen pada komputer kuantum nyata yang tersedia dari IBM Quantum. Namun, jika kamu telah menghabiskan waktu QPU, kamu bisa membuka komentar baris di bawah untuk menyelesaikan aktivitas ini menggunakan simulator.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Langkah 4: Post-process dan kembalikan hasil dalam format klasik yang diinginkan

Sekarang kita bisa memplot hasil sampling kita dalam histogram.

plot_distribution(dist)

Kita melihat bahwa algoritma Grover mengembalikan state yang diinginkan dengan probabilitas tertinggi sejauh ini, setidaknya satu orde besaran lebih tinggi dari opsi lainnya. Dalam aktivitas berikutnya, kita akan menggunakan algoritma tersebut dengan cara yang lebih konsisten dengan alur kerja dua pihak dari query algorithm.

Uji pemahamanmu

Baca pertanyaan di bawah ini, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Kita baru saja mencari satu solusi dalam himpunan $2^4=16$ state yang mungkin. Kita menentukan jumlah pengulangan optimal operator Grover adalah $t=3$. Apakah jumlah optimal ini akan bertambah atau berkurang jika kita mencari (a) salah satu dari beberapa solusi, atau (b) satu solusi dalam ruang state yang lebih banyak?

Jawaban:

Ingat bahwa selama jumlah solusi kecil dibandingkan dengan seluruh ruang solusi, kita bisa mengekspansi fungsi sinus di sekitar sudut kecil dan menggunakan

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) Kita lihat dari ekspresi di atas bahwa meningkatkan jumlah solution state akan menurunkan jumlah iterasi. Asalkan fraksi $\frac{|\mathcal{A}_1|}{N}$ masih kecil, kita bisa menggambarkan bagaimana $t$ akan berkurang: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) Saat ruang solusi yang mungkin ($N$) bertambah, jumlah iterasi yang diperlukan meningkat, tetapi hanya seperti $t~\sqrt{N}$.

Misalkan kita bisa meningkatkan ukuran target bitstring menjadi sembarang panjang dan tetap memiliki hasil bahwa target state memiliki amplitudo probabilitas yang setidaknya satu orde besaran lebih besar dari state lainnya. Apakah ini berarti kita bisa menggunakan algoritma Grover untuk menemukan target state secara andal?

Jawaban:

Tidak. Misalkan kita mengulangi aktivitas pertama dengan 20 qubit, dan kita menjalankan Circuit kuantum beberapa kali num_shots = 10,000. Distribusi probabilitas seragam akan berarti bahwa setiap state memiliki probabilitas $10,000/2^{20}=0.00954$ untuk diukur bahkan sekali pun. Jika probabilitas mengukur target state adalah 10 kali lipat dari non-solusi (dan probabilitas setiap non-solusi berkurang sedikit sesuai), hanya akan ada sekitar 10% kemungkinan mengukur target state bahkan sekali. Sangat tidak mungkin untuk mengukur target state beberapa kali, yang akan membuatnya tidak dapat dibedakan dari banyak non-solution state yang diperoleh secara acak. Kabar baiknya adalah kita bisa mendapatkan hasil dengan fidelitas lebih tinggi menggunakan error suppression dan mitigasi.

Aktivitas 2: Alur kerja query algorithm yang akurat

Kita akan memulai aktivitas ini persis seperti yang pertama, kecuali sekarang kamu akan berpasangan dengan penggiat Qiskit lainnya. Kamu akan memilih bitstring rahasia, dan pasanganmu akan memilih bitstring yang (umumnya) berbeda. Kamu masing-masing akan menghasilkan Circuit kuantum yang berfungsi sebagai oracle, dan kamu akan saling bertukar. Kamu kemudian akan menggunakan algoritma Grover dengan oracle tersebut untuk menentukan bitstring rahasia pasanganmu.

Langkah 1: Petakan input klasik ke masalah kuantum

Menggunakan fungsi grover_oracle yang didefinisikan di atas, buat oracle circuit untuk satu atau lebih marked state. Pastikan kamu memberi tahu pasanganmu berapa banyak state yang kamu tandai, sehingga mereka bisa menerapkan operator Grover sejumlah iterasi optimal. Jangan buat bitstring terlalu panjang. 3-5 bit seharusnya berfungsi tanpa banyak kesulitan. Bitstring yang lebih panjang akan menghasilkan Circuit yang dalam yang memerlukan teknik lebih lanjut seperti mitigasi error.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Sekarang kamu telah membuat Circuit kuantum yang membalik fase dari target state kamu. Kamu bisa menyimpan Circuit ini sebagai my_circuit.qpy menggunakan sintaks di bawah.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Sekarang kirimkan file ini ke pasanganmu (melalui email, layanan pesan, repo bersama, dan sebagainya). Minta pasanganmu juga mengirimkan Circuit mereka kepadamu. Pastikan kamu menyimpan file di tempat yang mudah kamu temukan. Setelah kamu mendapatkan Circuit pasanganmu, kamu bisa memvisualisasikannya - tetapi itu melanggar model query. Artinya, kita memodelkan situasi di mana kamu bisa melakukan query pada oracle (menggunakan oracle circuit) tetapi tidak memeriksanya untuk menentukan state yang ditargetkan.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Tanya pasanganmu berapa banyak target state yang mereka encode dan masukkan di bawah.

# Update according to your partner's number of target states.
num_marked_states = 1

Ini digunakan dalam ekspresi berikutnya untuk menentukan jumlah iterasi Grover yang optimal.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Langkah 2: Optimalkan masalah untuk eksekusi hardware kuantum

Ini berjalan persis seperti sebelumnya.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Langkah 3: Eksekusi menggunakan Qiskit primitives

Ini juga identik dengan proses pada aktivitas pertama.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Langkah 4: Post-process dan kembalikan hasil dalam format klasik yang diinginkan

Sekarang tampilkan histogram dari hasil samplingmu. Satu atau lebih state seharusnya memiliki probabilitas pengukuran yang jauh lebih tinggi dari yang lain. Laporkan ini ke pasanganmu dan periksa apakah kamu berhasil menentukan target state dengan benar. Secara default, histogram yang ditampilkan adalah dari Circuit yang sama dari aktivitas pertama. Kamu seharusnya mendapatkan hasil berbeda dari Circuit pasanganmu.

plot_distribution(dist)

Uji pemahamanmu

Baca pertanyaan atau petunjuk di bawah, pikirkan jawabanmu atau diskusikan proses tersebut dengan pasanganmu. Klik segitiga untuk petunjuk atau saran.

Kamu seharusnya berhasil mendapatkan target state pasanganmu. Jika tidak, kerja sama dengan pasanganmu untuk mengidentifikasi apa yang salah. Klik di bawah untuk beberapa ide.

Petunjuk:

• Visualisasikan/gambar Circuit pasanganmu dan pastikan itu berhasil dimuat dengan benar.
• Bandingkan Circuit yang digunakan dan bandingkan hasil yang diharapkan dengan yang kamu peroleh.
• Periksa kedalaman Circuit yang digunakan untuk memastikan bitstring tidak terlalu panjang atau jumlah iterasi Grover tidak terlalu tinggi.

Jika belum, gambar oracle circuit yang dikirimkan pasanganmu. Lihat apakah kamu bisa menjelaskan efek setiap gate dan berargumen apa target state-nya. Ini akan jauh lebih mudah untuk kasus satu marked state dibandingkan beberapa.

Petunjuk:

• Ingat bahwa tugas oracle adalah membalik tanda pada target state.
• Ingat bahwa MCMTGate membalik tanda pada state jika dan hanya jika semua qubit yang terlibat dalam kontrol berada di state $|1\rangle$.
• Jika target state kamu sudah memiliki $|1\rangle$ pada qubit tertentu, maka kamu tidak perlu melakukan apa pun pada qubit itu. Jika target kamu memiliki $|0\rangle$ pada qubit tertentu dan kamu ingin MCMTGate membalik tandanya, kamu perlu menerapkan gate X pada qubit tersebut di oraclemu (dan kemudian membatalkan gate X setelah MCMTGate).

Ulangi eksperimen dengan satu iterasi lebih sedikit dari operator Grover. Apakah kamu masih mendapatkan jawaban yang benar? Mengapa atau mengapa tidak?

Panduan:

Kemungkinan besar ya, meskipun mungkin tergantung pada jumlah solusi yang di-encode. Ini menyoroti suatu kehalusan: jumlah iterasi Grover yang "optimal" adalah jumlah yang membuat probabilitas mengukur marked state setinggi mungkin. Tetapi jumlah iterasi yang lebih sedikit dari itu mungkin masih membuat marked state jauh lebih mungkin dari state lainnya. Oleh karena itu, kamu mungkin bisa lolos dengan jumlah iterasi yang lebih sedikit dari jumlah optimal. Ini mengurangi kedalaman Circuit, dan dengan demikian mengurangi tingkat error.

Mengapa seseorang mungkin ingin menggunakan lebih sedikit iterasi Grover dari "jumlah optimal" yang diidentifikasi di sini?

Jawaban:

Jumlah iterasi Grover yang "optimal" adalah jumlah yang membuat probabilitas mengukur marked state setinggi mungkin tanpa adanya noise. Tetapi jumlah iterasi yang lebih sedikit dari itu mungkin masih membuat marked state jauh lebih mungkin dari state lainnya. Jadi kamu mungkin bisa lolos dengan jumlah iterasi yang lebih sedikit dari jumlah optimal. Ini mengurangi kedalaman Circuit, dan dengan demikian mengurangi tingkat error.

Aktivitas 3: Selesaikan grid Minesweeper dengan algoritma Grover

Pada bagian sebelumnya, kita mencatat bahwa algoritma Grover menjadi benar-benar berguna ketika kita bisa membangun oracle dari batasan suatu masalah, daripada dari pengetahuan tentang jawaban. Minesweeper adalah contoh yang sempurna: sel-sel bernomor memberi tahu kita berapa banyak ranjau yang berdekatan, dan batasan tersebut sepenuhnya menentukan di mana ranjau harus berada — tetapi menemukan konfigurasi tersebut membutuhkan pencarian.

Minesweeper telah terbukti NP-complete: sulit untuk diselesaikan tetapi mudah untuk diperiksa. Itu menjadikannya kandidat alami untuk algoritma Grover. Tentu saja, kita belum bisa menyelesaikan grid 9$\times$9 penuh pada komputer kuantum yang berderau — circuit-nya akan terlalu dalam. Sebaliknya, kita akan menggunakan grid kecil sebagai demonstrasi mainan tentang bagaimana seseorang akan mendekati papan yang lebih besar pada mesin fault-tolerant di masa depan.

Beberapa catatan penting. Algoritma Grover hanya memberikan percepatan kuadratik dibandingkan pencarian klasik tak terstruktur. Minesweeper hampir pasti memiliki struktur yang bisa dimanfaatkan yang bisa digunakan oleh algoritma klasik yang cerdas. Dan untuk ruang pencarian yang tumbuh secara eksponensial, bahkan peningkatan $\sqrt{N}$ hanya sejauh itu. Tetapi mari kita abaikan kekhawatiran tersebut dan gunakan masalah mainan ini untuk mengilustrasikan bagaimana batasan masalah dikodekan ke dalam oracle kuantum.

Grid tersebut

Berikut adalah grid minesweeper kecil kita:

Setiap sel kosong dapat direpresentasikan oleh variabel biner yang menunjukkan apakah berisi ranjau. Kita beri label $x_0$, $x_1$, dan $x_2$, di mana $x_i = 1$ berarti ada ranjau di sel tersebut dan $x_i = 0$ berarti tidak ada:

Kita bisa menyelesaikan ini dalam pikiran kita dalam sekitar setengah detik, tetapi kita menggunakan masalah mainan ini untuk mengilustrasikan bagaimana papan yang jauh lebih sulit bisa didekati dengan komputer kuantum.

Kodekan batasannya

Setiap sel bernomor menempatkan kondisi pada sel-sel kosong yang berdekatan. Kita perlu mengekspresikan kondisi-kondisi ini sebagai ekspresi Boolean yang bisa dikodekan ke dalam circuit kuantum.

Sel "1" yang berdekatan dengan $x_0$ dan $x_1$ mengatakan bahwa tepat satu dari mereka berisi ranjau. Ini adalah operasi exclusive-OR (XOR), $\oplus$, yang mengembalikan true ketika tepat satu inputnya adalah true:

$$(x_0 \oplus x_1)$$

Demikian pula, sel "1" lainnya (berdekatan dengan $x_1$ dan $x_2$) memberikan kita:

$$(x_1 \oplus x_2)$$

Sel "2" mengatakan bahwa dua dari tiga sel kosong harus berisi ranjau. Karena XOR adalah operasi paritas, $x_0 \oplus x_1 \oplus x_2$ mengembalikan true ketika jumlah ganjil dari variabel adalah true. Kita ingin jumlah genap (khususnya dua) yang true, jadi kita negasikan dengan $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

Dengan sendirinya, ekspresi ini akan dipenuhi oleh nol atau dua qubit dalam state $|1\rangle$, karena ini adalah pernyataan tentang paritas. Tetapi dikombinasikan dengan dua klausa lainnya, yang masing-masing membutuhkan setidaknya satu ranjau, satu-satunya penugasan yang memuaskan memiliki tepat dua ranjau.

Ketiga kondisi harus dipenuhi secara bersamaan, jadi kita gabungkan dengan simbol dan $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

Langkah 1: Petakan input klasik ke masalah kuantum

Sekarang kita perlu mengkodekan ekspresi Boolean ini ke dalam circuit kuantum yang berfungsi sebagai oracle. Versi kuantum dari XOR dapat dicapai dengan gate CX (CNOT): menerapkan dua gate CX dari data qubit ke workspace (ancilla) qubit secara efektif menghitung XOR mereka dan menyimpan hasilnya di ancilla.

Kita memperkenalkan tiga workspace qubit — satu untuk setiap klausa. Kita menyimpan hasil setiap ekspresi Boolean di workspace qubit yang sesuai, kemudian menggunakan multi-controlled Z gate untuk membalik fase state tiga qubit yang membuat semua tiga workspace qubit $|1\rangle$ (artinya semua klausa dipenuhi secara bersamaan).

Dalam sel kode pertama di bawah ini, kita membangun separuh "compute" dari oracle — bagian yang mengevaluasi setiap klausa dan menulis hasilnya ke workspace qubit.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

Pada titik ini, hasil setiap klausa disimpan di workspace qubit yang sesuai. Sekarang kita membutuhkan state data tiga qubit yang membuat semua tiga workspace qubit $|1\rangle$ untuk mendapatkan tanda minus. Kita melakukan ini dengan multi-controlled Z gate (diimplementasikan sebagai gate MCX yang diapit oleh Hadamard gate pada target).

Setelah menerapkan phase flip, kita harus uncompute — membatalkan semua langkah evaluasi klausa dalam urutan terbalik — untuk mereset workspace qubit kembali ke $|0\rangle.$ Ini penting agar workspace qubit bersih untuk iterasi berikutnya dari operator Grover.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Circuit ini adalah oracle kita: ia membalik fase state data qubit yang memenuhi semua tiga batasan Minesweeper, dan membiarkan workspace qubit kembali ke $|0\rangle.$

Sekarang kita membangun operator Grover penuh dari oracle ini. Perhatikan argumen reflection_qubits: kita hanya meneruskan data qubit x, karena workspace qubit bukan bagian dari ruang pencarian. Tugas mereka selesai setelah oracle diterapkan.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Dengan tiga data qubit dan satu solution state, jumlah iterasi Grover optimal adalah $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, jadi kita gunakan dua iterasi. Kita menerapkan Hadamard gate ke data qubit untuk membuat superposisi awal, menyusun operator Grover dua kali, dan mengukur hanya data qubit.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

Langkah 2: Optimalkan masalah untuk eksekusi hardware kuantum

Seperti sebelumnya, kita transpile circuit untuk backend target.

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

Sekarang kita bisa memeriksa kedalaman circuit yang di-transpile. Karena oracle Minesweeper menggunakan workspace qubit dan beberapa gate CX, circuit yang di-transpile akan lebih dalam dari yang ada di aktivitas sebelumnya.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

Langkah 3: Eksekusi menggunakan Qiskit primitives

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Langkah 4: Post-process dan kembalikan hasil dalam format klasik yang diinginkan

plot_distribution(dist)

State 101 seharusnya muncul dengan probabilitas jauh lebih tinggi dari yang lainnya, menunjukkan bahwa ranjau berada di $x_0$ dan $x_2$. Kita telah menggunakan komputer kuantum untuk menyelesaikan permainan Minesweeper kecil!

Tentu saja, algoritma klasik terbaik untuk minesweeper lebih baik daripada pencarian brute-force melalui semua konfigurasi ranjau yang mungkin — mereka memanfaatkan struktur grid. Algoritma Grover hanya menawarkan keunggulan pada papan yang sangat sulit yang dirancang untuk menjadi ambigu secara maksimal, dan bahkan dalam kasus itu, percepatan kuadratik berarti ia tidak bisa mengikuti pertumbuhan eksponensial selamanya. Tetapi pengambilan nyata adalah tekniknya: mengkodekan batasan masalah ke dalam oracle kuantum adalah pola yang kuat yang meluas ke constraint satisfaction, optimasi kombinatorial, dan banyak domain lainnya.

Pertanyaan dan konsep kritis:

Konsep kritis:

Dalam modul ini, kita mempelajari beberapa fitur kunci dari algoritma Grover:

• Sedangkan algoritma pencarian tak terstruktur klasik membutuhkan jumlah query yang skala secara linier dalam ukuran ruang, $N,$ algoritma Grover membutuhkan jumlah query yang berskala seperti $\sqrt{N}.$
• Algoritma Grover melibatkan pengulangan serangkaian operasi (umumnya disebut "operator Grover") sebanyak $t$ kali, dipilih untuk membuat target state paling mungkin diukur secara optimal.
• Algoritma Grover bisa dijalankan dengan kurang dari $t$ iterasi dan tetap mengamplifikasi target state.
• Algoritma Grover cocok dengan model query dari komputasi dan paling masuk akal ketika satu orang mengendalikan pencarian dan orang lain mengendalikan/membangun oracle. Ini juga mungkin berguna sebagai subroutine dalam komputasi kuantum lainnya.
• Oracle bisa dibangun dari batasan masalah daripada dari pengetahuan solusi, seperti yang didemonstrasikan dengan contoh Minesweeper.

Pertanyaan B/S:

1. B/S Algoritma Grover memberikan peningkatan eksponensial dibandingkan algoritma klasik dalam jumlah query yang dibutuhkan untuk menemukan satu marked state dalam pencarian tak terstruktur.

2. B/S Algoritma Grover bekerja dengan secara iteratif meningkatkan probabilitas bahwa solution state akan diukur.

3. B/S Semakin banyak kali kamu mengulangi operator Grover, semakin tinggi probabilitas mengukur solution state.

Pertanyaan MC:

1. Pilih opsi terbaik untuk melengkapi kalimat. Strategi terbaik untuk berhasil menggunakan algoritma Grover pada komputer kuantum modern adalah mengiterasi operator Grover...

• a. Hanya sekali.
• b. Selalu $t$ kali, untuk memaksimalkan amplitudo probabilitas solution state.
• c. Hingga $t$ kali, meskipun jumlah yang lebih sedikit mungkin cukup untuk membuat solution state menonjol.
• d. Tidak kurang dari 10 kali.

2. Sebuah phase query circuit ditampilkan di sini yang berfungsi sebagai oracle untuk menandai state tertentu dengan phase flip. State mana dari berikut ini yang ditandai oleh Circuit ini?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Misalkan kamu ingin mencari tiga marked state dari himpunan 128. Berapa jumlah iterasi optimal dari operator Grover untuk memaksimalkan amplitudo dari marked state?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Pertanyaan diskusi:

1. Masalah lain apa yang bisa kamu formulasikan sebagai pencarian Grover? Pikirkan masalah di mana sulit untuk menemukan solusi tetapi mudah untuk memverifikasinya.

2. Bisakah kamu melihat masalah apa pun dalam menskalakan algoritma Grover pada komputer kuantum modern?