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.

Matematika

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.

Peringatan yang jelas

Untuk menerapkan algoritma Grover, kita harus membangun operator Grover, yang berarti kita harus bisa membalik fase pada state yang memenuhi kriteria solusi kita. Ini menimbulkan pertanyaan: jika kita tahu set solusi kita dengan sangat baik sehingga kita bisa merancang Circuit kuantum untuk melabeli masing-masing, apa yang sedang kita cari?! Jawabannya ada tiga, dan kita akan kembali ke hal ini sepanjang tutorial:

(1) Jenis algoritma kueri ini sering melibatkan dua pihak: satu yang memiliki oracle yang menetapkan kriteria solusi, dan satu lagi yang mencoba menebak/menemukan state solusi. Fakta bahwa satu orang bisa membangun oracle tidak meniadakan kebutuhan akan pencarian.

(2) Ada masalah di mana lebih mudah untuk menentukan kriteria solusi daripada menemukan solusi. Contoh paling terkenal dari ini mungkin mengidentifikasi faktor prima dari bilangan besar. Algoritma Grover tidak terlalu efektif dalam menyelesaikan masalah spesifik itu; kita akan menggunakan algoritma Shor untuk faktorisasi prima. Ini hanyalah contoh untuk menunjukkan bahwa mengetahui kriteria perilaku suatu state tidak selalu sama dengan mengetahui state tersebut.

(3) Algoritma Grover tidak hanya mengembalikan data klasik. Memang benar, jika kita melakukan pengukuran state akhir setelah $t$ pengulangan operator Grover, kita kemungkinan akan mendapatkan informasi klasik yang mengidentifikasi state solusi. Tapi bagaimana jika kita tidak menginginkan informasi klasik; bagaimana jika kita menginginkan state solusi yang disiapkan di komputer kuantum untuk digunakan lebih lanjut dalam algoritma lain? Algoritma Grover sebenarnya menghasilkan state kuantum dengan solusi yang sangat berbobot. Jadi kamu bisa berharap menemukan algoritma Grover sebagai subrutin dalam algoritma kuantum yang lebih kompleks.

Dengan mempertimbangkan hal ini, mari kita berjalan melalui beberapa contoh. Kita akan mulai dengan contoh di mana state solusi ditentukan dengan jelas sehingga kita bisa mengikuti logika algoritma, dan kita akan beralih ke contoh di mana kegunaan algoritma Grover menjadi lebih jelas.

Import umum dan pendekatan

Kita mulai dengan mengimpor beberapa paket yang diperlukan.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
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 argumenkan di atas, kita mungkin perlu menerapkan operator Grover beberapa kali. Jumlah iterasi optimal, $t,$ untuk memaksimalkan amplitudo target state tanpa adanya noise dapat diperoleh dari ekspresi ini:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Di sini $A_1$ adalah jumlah solusi atau target 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.

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: Kriteria selain bitstring tertentu

Sebagai ilustrasi terakhir tentang bagaimana algoritma Grover mungkin berguna dalam konteks subroutine, bayangkan kita membutuhkan state kuantum dengan jumlah 1 tertentu dalam representasi bitstringnya. Ini umum dalam situasi di mana hukum konservasi terlibat. Misalnya, dalam konteks kimia kuantum, seseorang sering memetakan state 1 dari qubit ke occupancy orbital elektronik. Agar muatan terjaga, jumlah total 1 juga harus tetap konstan. Batasan seperti ini sangat umum sehingga memiliki nama khusus: batasan Hamming weight, dan jumlah 1 dalam state disebut Hamming weight.

Langkah 1:

Mari kita pertama-tama tulis fungsi yang menandai state dengan Hamming weight yang diinginkan. Kita akan menulis ini secara umum untuk jumlah qubit yang tidak ditentukan num_qubits dan target Hamming weight target_weight.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

Dari sini seluruh proses identik dengan dua aktivitas sebelumnya. Demi singkatnya, langkah-langkah pola Qiskit hanya ditampilkan dalam komentar kode di sini.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(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()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

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)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

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()

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

ibm_brisbane

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  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Di sini algoritma Grover memang menyiapkan state dengan Hamming weight 2 untuk jauh lebih mungkin diukur dibandingkan state lainnya, kira-kira satu orde besaran lebih mungkin.

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.

Pertanyaan

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. Kondisi lain apa yang mungkin kamu gunakan dalam oracle kuantum? Pertimbangkan kondisi yang mudah dinyatakan atau diterapkan pada bitstring tetapi bukan sekadar menuliskan marked bitstring.

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