Algoritma Grover

Untuk modul Qiskit dalam Bilik Darjah ini, pelajar perlu mempunyai persekitaran Python yang berfungsi dengan pakej berikut dipasang:

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

Untuk menyediakan dan memasang pakej di atas, lihat panduan Pasang Qiskit. Untuk menjalankan kerja pada komputer kuantum sebenar, pelajar perlu membuat akaun dengan IBM Quantum® dengan mengikuti langkah-langkah dalam panduan Sediakan akaun IBM Cloud anda.

Modul ini telah diuji dan menggunakan 12 saat masa QPU. Ini adalah anggaran suci hati; penggunaan sebenar anda mungkin berbeza.

# 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'

Pengenalan

Algoritma Grover ialah algoritma kuantum asas yang menangani masalah carian tidak berstruktur: diberikan satu set $N$ item dan cara untuk memeriksa sama ada mana-mana item adalah yang anda cari, seberapa cepat anda boleh mencari item yang dikehendaki? Dalam pengkomputeran klasik, jika data tidak tersusun dan tiada struktur yang boleh dieksploitasi, pendekatan terbaik ialah memeriksa setiap item satu persatu, yang menghasilkan kerumitan pertanyaan $O(N)$ — secara purata, anda perlu memeriksa kira-kira separuh item sebelum menemui sasaran.

Algoritma Grover, yang diperkenalkan oleh Lov Grover pada tahun 1996, menunjukkan bagaimana komputer kuantum boleh menyelesaikan masalah ini dengan lebih cekap, hanya memerlukan $O(\sqrt{N})$ langkah untuk mencari item yang ditanda dengan kebarangkalian tinggi. Ini mewakili pecutan kuadratik berbanding kaedah klasik, yang penting untuk set data yang besar.

Algoritma ini beroperasi dalam konteks berikut:

• Persediaan masalah: Anda mempunyai fungsi $f(x)$ yang mengembalikan 1 jika $x$ ialah item yang anda inginkan, dan 0 sebaliknya. Fungsi ini sering dipanggil oracle atau kotak hitam, kerana anda hanya boleh mengetahui tentang data dengan membuat pertanyaan $f(x)$.
• Kegunaan kuantum: Walaupun algoritma klasik untuk masalah ini memerlukan, secara purata, $N/2$ pertanyaan, algoritma Grover boleh mencari penyelesaian dalam kira-kira $\pi\sqrt{N}/4$ pertanyaan, yang jauh lebih pantas untuk $N$ yang besar.
• Cara ia berfungsi (pada tahap tinggi):
  • Komputer kuantum mula-mula mencipta superposisi semua keadaan yang mungkin, mewakili semua item yang mungkin sekaligus.
  • Kemudian ia berulang kali menggunakan urutan operasi kuantum (lelaran Grover) yang menguatkan kebarangkalian jawapan yang betul dan mengurangkan yang lain.
  • Selepas cukup lelaran, pengukuran keadaan kuantum menghasilkan jawapan yang betul dengan kebarangkalian tinggi.

Berikut adalah rajah asas algoritma Grover yang melepasi banyak nuansa. Untuk rajah yang lebih terperinci, lihat makalah ini.

Beberapa perkara yang perlu diperhatikan tentang algoritma Grover:

• Ia optimum untuk carian tidak berstruktur: tiada algoritma kuantum boleh menyelesaikan masalah dengan kurang daripada $O(\sqrt{N})$ pertanyaan.
• Ia hanya memberikan pecutan kuadratik, bukan eksponen — tidak seperti beberapa algoritma kuantum lain (contohnya, algoritma Shor untuk pemfaktoran).
• Ia mempunyai implikasi praktikal, seperti kemungkinan mempercepatkan serangan kekerasan pada sistem kriptografi, walaupun pecepatannya tidak cukup untuk memecahkan kebanyakan penyulitan moden dengan sendirinya.

Bagi pelajar sarjana muda yang biasa dengan konsep pengkomputeran asas dan model pertanyaan, algoritma Grover menawarkan ilustrasi yang jelas tentang bagaimana pengkomputeran kuantum boleh mengatasi pendekatan klasik untuk masalah tertentu, walaupun penambahbaikannya "hanya" kuadratik. Ia juga berfungsi sebagai pintu masuk untuk memahami algoritma kuantum yang lebih maju dan potensi yang lebih luas pengkomputeran kuantum.

Pengamplifikasian amplitud ialah algoritma kuantum tujuan umum, atau subrutin, yang boleh digunakan untuk mendapatkan pecutan kuadratik berbanding beberapa algoritma klasik. Algoritma Grover adalah yang pertama menunjukkan pecutan ini pada masalah carian tidak berstruktur. Merumuskan masalah carian Grover memerlukan fungsi oracle yang menanda satu atau lebih keadaan asas pengiraan sebagai keadaan yang kita mahu cari, dan Circuit pengamplifikasian yang meningkatkan amplitud keadaan yang ditanda, seterusnya menekan keadaan yang lain.

Di sini, kami menunjukkan cara membina oracle Grover dan menggunakan GroverOperator daripada pustaka Circuit Qiskit untuk menyediakan instance carian Grover dengan mudah. Primitif Sampler masa jalan membolehkan pelaksanaan Circuit Grover yang lancar.

Matematik

Andaikan wujud fungsi $f$ yang memetakan rentetan binari kepada satu pemboleh ubah binari tunggal, bermaksud

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

Satu contoh yang ditakrifkan pada $\Sigma^6$ ialah

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

Contoh lain yang ditakrifkan pada $\Sigma^{2n}$ ialah

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

Anda ditugaskan untuk mencari keadaan kuantum yang sepadan dengan argumen $x$ dari $f(x)$ yang dipetakan ke 1. Dengan kata lain, cari semua $\{x_1\}\in \Sigma^n$ supaya $f(x_1)=1$ (atau jika tiada penyelesaian, laporkan perkara tersebut). Kami merujuk bukan-penyelesaian sebagai $x_0$. Sudah tentu, kami akan melakukan ini pada komputer kuantum, menggunakan keadaan kuantum, jadi berguna untuk menyatakan rentetan binari ini sebagai keadaan:

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

Menggunakan notasi keadaan kuantum (Dirac), kita mencari satu atau lebih keadaan khas $\{|x_1\rangle\}$ dalam satu set $N=2^n$ keadaan yang mungkin, di mana $n$ ialah bilangan Qubit, dengan bukan-penyelesaian dinotasikan $\{|x_0\rangle\}.$

Kita boleh menganggap fungsi $f$ sebagai disediakan oleh oracle: kotak hitam yang boleh kita tanya untuk menentukan kesannya terhadap keadaan $|x\rangle.$ Dalam praktik, kita sering mengetahui fungsinya, tetapi ia mungkin sangat rumit untuk dilaksanakan, bermakna mengurangkan bilangan pertanyaan atau aplikasi $f$ boleh menjadi penting. Sebagai alternatif, kita boleh membayangkan paradigma di mana satu pihak membuat pertanyaan kepada oracle yang dikawal oleh pihak lain, supaya kita tidak mengetahui fungsi oracle, kita hanya mengetahui tindakannya terhadap keadaan tertentu daripada pertanyaan.

Ini adalah "masalah carian tidak berstruktur", kerana tiada yang istimewa tentang $f$ yang membantu kita dalam pencarian. Outputnya tidak disusun dan penyelesaian tidak diketahui berkelompok, dan sebagainya. Pertimbangkan buku telefon kertas lama sebagai analogi. Carian tidak berstruktur ini ibarat mengimbas melaluinya mencari nombor tertentu, bukan seperti mencari melalui senarai nama yang tersusun mengikut abjad.

Dalam kes di mana satu penyelesaian dicari, secara klasik, ini memerlukan bilangan pertanyaan yang linear dalam $N$. Jelas anda mungkin menemui penyelesaian pada percubaan pertama, atau anda mungkin tidak menemui penyelesaian dalam $N-1$ tekaan pertama, sehingga anda perlu membuat pertanyaan input ke-$N$ untuk melihat sama ada ada penyelesaian langsung. Memandangkan fungsi tidak mempunyai struktur yang boleh dieksploitasi, anda akan memerlukan $N/2$ tekaan secara purata. Algoritma Grover memerlukan bilangan pertanyaan atau pengiraan $f$ yang berskala seperti $\sqrt{N}.$

Lakaran litar dalam algoritma Grover

Penjelasan matematik penuh algoritma Grover boleh didapati, contohnya, dalam Asas algoritma kuantum, kursus oleh John Watrous di IBM Quantum Learning. Perlakuan ringkas disediakan dalam lampiran di hujung modul ini. Tetapi buat masa ini, kita hanya akan mengkaji semula struktur keseluruhan Circuit kuantum yang melaksanakan algoritma Grover.

Algoritma Grover boleh dipecahkan kepada peringkat berikut:

• Penyediaan superposisi awal (menggunakan Gate Hadamard pada semua Qubit)
• "Menanda" keadaan sasaran dengan pembalikan fasa
• Peringkat "penyebaran" di mana Gate Hadamard dan pembalikan fasa digunakan pada semua Qubit.
• Kemungkinan pengulangan peringkat penandaan dan penyebaran untuk memaksimumkan kebarangkalian mengukur keadaan sasaran
• Pengukuran

Selalunya, Gate penandaan $Z_f$ dan lapisan penyebaran yang terdiri daripada $H,$ $Z_{\text{OR}},$ dan $H$ secara kolektif dirujuk sebagai "operator Grover". Dalam rajah ini, hanya satu pengulangan operator Grover ditunjukkan.

Gate Hadamard $H$ dikenali dan digunakan secara meluas dalam pengkomputeran kuantum. Gate Hadamard mencipta keadaan superposisi. Secara khusus ia ditakrifkan 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 mana-mana keadaan lain ditakrifkan melalui kelinearan. Khususnya, lapisan Gate Hadamard membolehkan kita berpindah dari keadaan awal dengan semua Qubit dalam $|0\rangle$ (dinotasikan $|0\rangle^{\otimes n}$) kepada keadaan di mana setiap Qubit mempunyai beberapa kebarangkalian untuk diukur sama ada dalam $|0\rangle$ atau $|1\rangle;$ ini membolehkan kita menyelidik ruang semua keadaan yang mungkin secara berbeza daripada dalam pengkomputeran klasik.

Sifat akibat penting Gate Hadamard ialah bertindak kali kedua boleh membatalkan keadaan 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 penting sebentar lagi.

Semak kefahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaiannya.

Bermula dari definisi Gate Hadamard, tunjukkan bahawa aplikasi kedua Gate Hadamard membatalkan superposisi tersebut seperti yang dituntut di atas.

Jawapan:

Apabila kita menggunakan X pada keadaan $|+\rangle$, kita mendapat nilai +1 dan pada keadaan $|-\rangle$ kita mendapat -1, jadi jika kita mempunyai taburan 50-50, kita akan mendapat nilai jangkaan 0.

Gate $Z_\text{OR}$ kurang biasa, dan ditakrifkan mengikut

$$\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$$

Akhirnya, Gate $Z_f$ ditakrifkan oleh

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

Perhatikan kesannya ialah $Z_f$ membalikkan tanda pada keadaan sasaran yang $f(x) = 1$ dan membiarkan keadaan lain tidak terjejas.

Pada tahap abstrak yang sangat tinggi, anda boleh berfikir tentang langkah-langkah dalam litar dengan cara berikut:

• Lapisan Hadamard pertama: meletakkan Qubit ke dalam superposisi semua keadaan yang mungkin.
• $Z_f$: tandakan keadaan sasaran dengan menambah tanda "-" di hadapan. Ini tidak segera mengubah kebarangkalian pengukuran, tetapi ia mengubah cara keadaan sasaran akan berkelakuan dalam langkah seterusnya.
• Lapisan Hadamard lain: Tanda "-" yang diperkenalkan dalam langkah sebelumnya akan mengubah tanda relatif antara beberapa sebutan. Memandangkan Gate Hadamard menukar satu campuran keadaan pengiraan $(|0\rangle+|1\rangle)/\sqrt{2}$ menjadi satu keadaan pengiraan, $|0\rangle,$ dan ia menukar $(|0\rangle-|1\rangle)/\sqrt{2}$ menjadi $|1\rangle$ perbezaan tanda relatif ini kini boleh mula memainkan peranan dalam keadaan yang diukur.
• Satu lapisan akhir Gate Hadamard digunakan, kemudian pengukuran dibuat. Kita akan melihat secara lebih terperinci bagaimana ini berfungsi dalam bahagian seterusnya.

Contoh

Untuk lebih memahami cara algoritma Grover berfungsi, mari kita lalui contoh kecil dua Qubit. Ini boleh dianggap pilihan bagi mereka yang tidak fokus pada mekanik kuantum dan notasi Dirac. Tetapi bagi mereka yang berharap untuk bekerja secara substantif dengan komputer kuantum, ini amat disyorkan.

Berikut ialah rajah litar dengan keadaan kuantum berlabel pada pelbagai kedudukan sepanjang laluan. Perhatikan bahawa dengan hanya dua Qubit, hanya terdapat empat keadaan yang mungkin yang boleh diukur dalam mana-mana keadaan: $|00\rangle$, $|01\rangle$, $|10\rangle$, dan $|11\rangle$.

Andaikan oracle ($Z_f$, tidak diketahui oleh kita) menanda keadaan $|01\rangle$. Kita akan melalui tindakan setiap set Gate kuantum, termasuk oracle, dan melihat taburan keadaan yang mungkin keluar pada masa pengukuran. Pada permulaan sekali, kita mempunyai

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

Menggunakan definisi Gate Hadamard, kita mempunyai

$$|\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 menanda keadaan sasaran:

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

Perhatikan bahawa dalam keadaan ini, kesemua empat hasil yang mungkin mempunyai kebarangkalian yang sama untuk diukur. Semuanya mempunyai berat magnitud $1/2,$ bermakna masing-masing mempunyai peluang $|1/2|^2=1/4$ untuk diukur. Jadi walaupun keadaan $|01\rangle$ ditanda melalui fasa "-", ini belum menghasilkan peningkatan kebarangkalian mengukur keadaan tersebut. Kita teruskan dengan menggunakan lapisan Gate Hadamard seterusnya.

$$\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 sebutan yang serupa, kita dapati

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

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

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

Dan akhirnya, kita menggunakan lapisan akhir Gate Hadamard:

$$\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}$$

Berbaloi untuk melalui penggabungan sebutan-sebutan ini untuk meyakinkan diri anda bahawa hasilnya memang:

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

Iaitu, kebarangkalian mengukur $|01\rangle$ adalah 100% (tanpa kehadiran hingar dan ralat) dan kebarangkalian mengukur mana-mana keadaan lain adalah sifar.

Contoh dua Qubit ini adalah kes yang sangat kemas; algoritma Grover tidak selalunya akan menghasilkan peluang 100% mengukur keadaan sasaran. Sebaliknya, ia akan menguatkan kebarangkalian mengukur keadaan sasaran. Juga, operator Grover mungkin perlu diulang lebih dari sekali.

Dalam bahagian seterusnya, kita akan mempraktikkan algoritma ini menggunakan komputer kuantum IBM® yang sebenar.

Kaveat yang jelas

Untuk menggunakan algoritma Grover, kita perlu membina operator Grover, yang bermakna kita mesti dapat membalikkan fasa pada keadaan yang memenuhi kriteria penyelesaian kita. Ini menimbulkan soalan: jika kita mengetahui set penyelesaian kita dengan begitu baik sehingga kita boleh mereka bentuk Circuit kuantum untuk melabelkan setiap satu, apakah yang kita cari?! Jawapannya ada tiga, dan kita akan kembali kepada ini sepanjang tutorial:

(1) Algoritma pertanyaan seperti ini sering melibatkan dua pihak: satu yang mempunyai oracle yang menetapkan kriteria penyelesaian, dan satu lagi yang cuba meneka/mencari keadaan penyelesaian. Fakta bahawa satu orang boleh membina oracle tidak menafikan keperluan untuk carian.

(2) Terdapat masalah yang lebih mudah untuk menentukan kriteria penyelesaian daripada mencari penyelesaiannya. Contoh terbaik yang diketahui bagi ini mungkin adalah mengenal pasti faktor perdana nombor besar. Algoritma Grover tidak begitu berkesan untuk menyelesaikan masalah khusus itu; kita akan menggunakan algoritma Shor untuk pemfaktoran perdana. Ini hanyalah contoh untuk menunjukkan bahawa mengetahui kriteria terhadap kelakuan keadaan tidak selalu sama dengan mengetahui keadaan itu.

(3) Algoritma Grover tidak hanya mengembalikan data klasik. Benar, jika kita membuat pengukuran keadaan akhir selepas $t$ pengulangan operator Grover, kita mungkin mendapat maklumat klasik yang mengenal pasti keadaan penyelesaian. Tetapi bagaimana jika kita tidak mahukan maklumat klasik; bagaimana jika kita mahukan keadaan penyelesaian yang disediakan pada komputer kuantum untuk kegunaan lanjut dalam algoritma lain? Algoritma Grover sebenarnya menghasilkan keadaan kuantum dengan penyelesaian yang sangat diberi berat. Jadi anda boleh menjangkakan untuk menemui algoritma Grover sebagai subrutin dalam algoritma kuantum yang lebih rumit.

Dengan mengambil kira perkara-perkara ini, mari kita lalui beberapa contoh. Kita akan bermula dengan contoh di mana keadaan penyelesaian dinyatakan dengan jelas supaya kita boleh mengikuti logik algoritma, dan kita akan beralih kepada contoh di mana kegunaan algoritma Grover menjadi lebih jelas.

Import umum dan pendekatan

Kita mulakan dengan mengimport beberapa pakej 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 yang lain, kita akan menggunakan rangka kerja untuk pengkomputeran kuantum yang dikenali sebagai "corak Qiskit", yang memecahkan aliran kerja kepada langkah-langkah berikut:

• Langkah 1: Petakan input klasik kepada masalah kuantum
• Langkah 2: Optimumkan masalah untuk pelaksanaan kuantum
• Langkah 3: Laksanakan menggunakan Primitif Masa Jalan Qiskit
• Langkah 4: Pasca-pemprosesan dan analisis klasik

Kita akan mengikuti langkah-langkah ini secara umum, walaupun kita mungkin tidak selalu melabelkannya secara eksplisit.

Aktiviti 1: Cari satu keadaan sasaran yang diberikan

Langkah 1: Petakan input klasik kepada masalah kuantum

Kita memerlukan Gate pertanyaan fasa untuk meletakkan fasa keseluruhan (-1) pada keadaan penyelesaian, dan membiarkan keadaan bukan-penyelesaian tidak terjejas. Cara lain untuk menyatakannya ialah algoritma Grover memerlukan oracle yang menentukan satu atau lebih keadaan asas pengiraan yang ditanda, di mana "ditanda" bermaksud keadaan dengan fasa -1. Ini dilakukan menggunakan Gate Z-terkawal, atau generalisasi berbilang-kawalannya ke atas $N$ Qubit. Untuk melihat cara ini berfungsi, pertimbangkan contoh khusus rentetan bit {110}. Kita ingin sebuah Circuit yang bertindak pada keadaan $|\psi\rangle = |q_2,q_1,q_0\rangle$ dan menggunakan fasa jika $|\psi\rangle = |011\rangle$ (di mana kita telah membalikkan urutan rentetan binari, kerana notasi dalam Qiskit yang meletakkan Qubit paling tidak ketara (selalunya 0) di sebelah kanan).

Oleh itu, kita mahukan Circuit $Z_f$ yang mencapai

$$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 boleh menggunakan Gate kawalan berbilang sasaran berbilang (MCMTGate) untuk menggunakan Gate Z yang dikawal oleh semua Qubit (balikkan fasa jika semua Qubit dalam keadaan $|1\rangle$). Sudah tentu, beberapa Qubit dalam keadaan yang kita inginkan mungkin $|0\rangle$. Oleh itu, untuk Qubit tersebut kita mesti terlebih dahulu menggunakan Gate X, kemudian lakukan Gate Z berbilang-kawalan, kemudian gunakan Gate X lagi untuk membatalkan perubahan kita. MCMTGate kelihatan seperti ini:

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

Perhatikan bahawa banyak Qubit mungkin terlibat dalam proses kawalan (di sini tiga Qubit terlibat), tetapi tiada satu Qubit pun yang ditetapkan sebagai sasaran. Ini kerana keseluruhan keadaan mendapat tanda "-" keseluruhan (pembalikan fasa); Gate mempengaruhi semua Qubit secara setara. Ini berbeza daripada banyak Gate berbilang Qubit lain, seperti Gate CX, yang mempunyai satu Qubit kawalan dan satu Qubit sasaran.

Dalam kod berikut, kita mentakrifkan Gate pertanyaan fasa (atau oracle) yang melakukan apa yang kita huraikan di atas: menanda satu atau lebih keadaan asas input yang ditakrifkan melalui perwakilan rentetan bit mereka. Gate MCMT digunakan untuk melaksanakan Gate Z berbilang-kawalan.

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 memilih keadaan "ditanda" tertentu sebagai sasaran kita, dan menggunakan fungsi yang baru kita takrifkan. Mari lihat jenis Circuit yang ia cipta.

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

Jika Qubit 1-3 berada dalam keadaan $|1\rangle$, dan Qubit 0 pada awalnya dalam keadaan $|0\rangle$, Gate X pertama akan membalikkan Qubit 0 ke $|1\rangle$ dan semua Qubit akan berada dalam $|1\rangle.$ Ini bermakna Gate MCMT akan menggunakan perubahan tanda keseluruhan atau pembalikan fasa, seperti yang dikehendaki. Untuk mana-mana kes lain, sama ada Qubit 1-3 berada dalam keadaan $|0\rangle$, atau Qubit 0 dibalikkan ke keadaan $|0\rangle$, dan pembalikan fasa tidak akan digunakan. Kita melihat bahawa Circuit ini memang menanda keadaan yang kita inginkan $|0111\rangle,$ atau rentetan bit {1110}.

Operator Grover penuh terdiri daripada Gate pertanyaan fasa (oracle), lapisan Hadamard, dan operator $Z_\text{OR}$. Kita boleh menggunakan grover_operator terbina dalam untuk membina ini daripada oracle yang kita takrifkan di atas.

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

Seperti yang kita hujahkan di atas, kita mungkin perlu menggunakan operator Grover beberapa kali. Bilangan lelaran optimum, $t,$ untuk memaksimumkan amplitud keadaan sasaran tanpa kehadiran hingar boleh diperoleh daripada ungkapan 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$ ialah bilangan penyelesaian atau keadaan sasaran. Pada komputer kuantum berderau moden, bilangan lelaran optimum secara eksperimen mungkin berbeza — tetapi di sini kita mengira dan menggunakan bilangan optimum teori ini 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 bina Circuit yang merangkumi Gate Hadamard awal untuk mencipta superposisi semua keadaan yang mungkin, dan menggunakan operator Grover sebanyak bilangan kali optimum.

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 membina Circuit Grover kita!

Langkah 2: Optimumkan masalah untuk pelaksanaan perkakasan kuantum

Kita telah mentakrifkan Circuit kuantum abstrak kita, tetapi kita perlu menulis semula dalam bentuk Gate yang asli kepada komputer kuantum yang sebenarnya ingin kita gunakan. Kita juga perlu menentukan Qubit mana pada komputer kuantum yang perlu digunakan. Atas sebab-sebab ini dan lain-lain, kita kini mesti transpil Circuit kita. Pertama, mari kita tentukan komputer kuantum yang ingin kita gunakan.

Terdapat kod di bawah untuk menyimpan kelayakan anda pada penggunaan pertama. Pastikan anda memadam maklumat ini daripada notebook selepas menyimpannya ke persekitaran anda, supaya kelayakan anda tidak terdedah secara tidak sengaja apabila anda berkongsi notebook. Lihat Sediakan akaun IBM Cloud anda dan Mulakan perkhidmatan dalam persekitaran tidak dipercayai untuk panduan 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 menggunakan pengurus pas pratetap untuk mengoptimumkan Circuit kuantum kita untuk Backend yang kita pilih.

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 dinyatakan pada masa ini bahawa kedalaman Circuit kuantum yang ditranspilkan adalah besar.

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 adalah nombor yang agak besar, walaupun untuk kes mudah ini. Memandangkan semua Gate kuantum (dan terutama Gate dua Qubit) mengalami ralat dan tertakluk kepada hingar, satu siri lebih 100 Gate dua Qubit akan menghasilkan hingar semata-mata jika Qubit tidak berprestasi sangat tinggi. Mari kita lihat bagaimana prestasinya.

Laksanakan menggunakan primitif Qiskit

Kita ingin membuat banyak pengukuran dan melihat keadaan mana yang paling mungkin. Pengamplifikasian amplitud sedemikian ialah masalah pensampelan yang sesuai untuk pelaksanaan dengan primitif Masa Jalan Qiskit Sampler.

Perhatikan bahawa kaedah run() SamplerV2 Masa Jalan Qiskit mengambil objek boleh ulang dari blok bersatu primitif (PUB). Untuk Sampler, setiap PUB ialah objek boleh ulang dalam format (circuit, parameter_values). Namun, pada minimum, ia mengambil senarai 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 mendapat manfaat terbaik daripada pengalaman ini, kami sangat mengesyorkan anda menjalankan eksperimen anda pada komputer kuantum sebenar yang tersedia daripada IBM Quantum. Namun, jika anda telah menghabiskan masa QPU anda, anda boleh nyahulas baris di bawah untuk melengkapkan aktiviti 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: Pasca-proses dan kembalikan keputusan dalam format klasik yang dikehendaki

Sekarang kita boleh memplot keputusan pensampelan kita dalam histogram.

plot_distribution(dist)

Kita melihat bahawa algoritma Grover mengembalikan keadaan yang dikehendaki dengan kebarangkalian tertinggi setakat ini, sekurang-kurangnya satu order magnitud lebih tinggi daripada pilihan lain. Dalam aktiviti seterusnya, kita akan menggunakan algoritma dengan cara yang lebih konsisten dengan aliran kerja dua pihak bagi algoritma pertanyaan.

Semak kefahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaiannya.

Kita baru mencari satu penyelesaian dalam satu set $2^4=16$ keadaan yang mungkin. Kita menentukan bilangan optimum pengulangan operator Grover ialah $t=3$. Adakah bilangan optimum ini akan meningkat atau menurun jika kita mencari (a) mana-mana daripada beberapa penyelesaian, atau (b) satu penyelesaian dalam ruang keadaan yang lebih mungkin?

Jawapan:

Ingat bahawa selagi bilangan penyelesaian kecil berbanding keseluruhan ruang penyelesaian, kita boleh mengembangkan 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 daripada ungkapan di atas bahawa meningkatkan bilangan keadaan penyelesaian akan mengurangkan bilangan lelaran. Dengan syarat bahawa pecahan $\frac{|\mathcal{A}_1|}{N}$ masih kecil, kita boleh menghuraikan cara $t$ akan berkurang: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) Apabila ruang penyelesaian yang mungkin ($N$) meningkat, bilangan lelaran yang diperlukan meningkat, tetapi hanya seperti $t~\sqrt{N}$.

Andaikan kita boleh meningkatkan saiz rentetan bit sasaran menjadi sewenang-wenangnya panjang dan masih mempunyai hasil bahawa keadaan sasaran mempunyai amplitud kebarangkalian yang sekurang-kurangnya satu order magnitud lebih besar daripada mana-mana keadaan lain. Adakah ini bermakna kita boleh menggunakan algoritma Grover untuk mencari keadaan sasaran secara boleh dipercayai?

Jawapan:

Tidak. Andaikan kita mengulangi aktiviti pertama dengan 20 Qubit, dan kita menjalankan Circuit kuantum beberapa kali num_shots = 10,000. Taburan kebarangkalian seragam bermakna setiap keadaan mempunyai kebarangkalian $10,000/2^{20}=0.00954$ untuk diukur walaupun sekali. Jika kebarangkalian mengukur keadaan sasaran adalah 10 kali ganda berbanding bukan-penyelesaian (dan kebarangkalian setiap bukan-penyelesaian berkurang sedikit), hanya akan ada peluang kira-kira 10% untuk mengukur keadaan sasaran walaupun sekali. Kemungkinan besar untuk mengukur keadaan sasaran beberapa kali adalah sangat rendah, yang akan menjadikannya tidak dapat dibezakan daripada banyak keadaan bukan-penyelesaian yang diperoleh secara rawak. Berita baiknya ialah kita boleh mendapatkan hasil yang lebih tepat dengan menggunakan penindasan dan pengurangan ralat.

Activity 2: An accurate query algorithm workflow

Langkah 1: Petakan input klasik kepada masalah kuantum

Gunakan fungsi grover_oracle yang telah ditakrifkan di atas, bina litar oracle untuk satu atau lebih keadaan yang ditanda. Pastikan kamu beritahu rakan kongsi kamu berapa banyak keadaan yang kamu tandakan, supaya mereka boleh menerapkan operator Grover sebanyak bilangan kali yang optimum. Jangan buat bitstring kamu terlalu panjang. 3-5 bit patut berfungsi tanpa banyak kesulitan. Bitstring yang lebih panjang akan menghasilkan litar yang dalam dan memerlukan teknik lanjutan seperti pengurangan ralat.

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

Sekarang kamu telah mencipta litar kuantum yang membalikkan fasa keadaan sasaran kamu. Kamu boleh simpan litar 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 hantar fail ini kepada rakan kongsi kamu (melalui e-mel, perkhidmatan pesanan, repo dikongsi, dan sebagainya). Minta rakan kongsi kamu hantar litar mereka kepada kamu juga. Pastikan kamu simpan fail tersebut di tempat yang mudah dicari. Setelah kamu mempunyai litar rakan kongsi kamu, kamu boleh menggambarkannya — tetapi itu akan melanggar model pertanyaan. Maksudnya, kita sedang memodelkan situasi di mana kamu boleh membuat pertanyaan kepada oracle (menggunakan litar oracle) tetapi tidak boleh memeriksanya untuk menentukan keadaan yang disasarkan.

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 rakan kongsi kamu berapa banyak keadaan sasaran yang mereka kodkan dan masukkan di bawah.

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

Ini digunakan dalam ungkapan seterusnya untuk menentukan bilangan ulangan Grover yang optimum.

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: Optimumkan masalah untuk pelaksanaan perkakasan kuantum

Ini dijalankan sama 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: Laksanakan menggunakan primitif Qiskit

Ini juga sama dengan proses dalam aktiviti 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: Proses selepas dan kembalikan keputusan dalam format klasik yang dikehendaki

Sekarang paparkan histogram keputusan pensampelan kamu. Satu atau lebih keadaan sepatutnya mempunyai kebarangkalian pengukuran yang jauh lebih tinggi daripada yang lain. Laporkan ini kepada rakan kongsi kamu dan semak sama ada kamu berjaya menentukan keadaan sasaran mereka. Secara lalai, histogram yang dipaparkan adalah dari litar yang sama dalam aktiviti pertama. Kamu sepatutnya mendapat keputusan yang berbeza daripada litar rakan kongsi kamu.

plot_distribution(dist)

Semak kefahaman kamu

Baca soalan atau gesaan di bawah, fikirkan jawapan kamu atau bincangkan proses tersebut bersama rakan kongsi kamu. Klik segitiga untuk petunjuk atau cadangan.

Kamu sepatutnya berjaya mendapatkan keadaan sasaran rakan kongsi kamu dengan betul. Jika tidak, bekerjasama dengan rakan kongsi kamu untuk mengenal pasti apa yang silap. Klik di bawah untuk beberapa idea.

Petunjuk:

• Gambarkan/lukis litar rakan kongsi kamu dan pastikan ia dimuatkan dengan betul.
• Bandingkan litar yang digunakan dan bandingkan hasil yang dijangkakan dengan yang kamu peroleh.
• Semak kedalaman litar yang digunakan untuk memastikan bitstring tidak terlalu panjang atau bilangan ulangan Grover tidak terlalu tinggi.

Jika kamu belum berbuat demikian, lukis litar oracle yang dihantar oleh rakan kongsi kamu. Cuba bincangkan kesan setiap gate dan hujahkan apakah keadaan sasaran yang mungkin. Ini akan jauh lebih mudah untuk kes satu keadaan yang ditanda berbanding berbilang.

Petunjuk:

• Ingat bahawa tugas oracle adalah untuk membalikkan tanda pada keadaan sasaran.
• Ingat bahawa MCMTGate membalikkan tanda pada sesuatu keadaan jika dan hanya jika semua qubit yang terlibat dalam kawalan berada dalam keadaan $|1\rangle$.
• Jika keadaan sasaran kamu sudah mempunyai $|1\rangle$ pada qubit tertentu, maka kamu tidak perlu berbuat apa-apa pada qubit tersebut. Jika sasaran kamu mempunyai $|0\rangle$ pada qubit tertentu dan kamu mahukan MCMTGate membalikkan tanda, kamu perlu menerapkan gate X pada qubit tersebut dalam oracle kamu (dan kemudian membatalkan gate X selepas MCMTGate).

Ulang eksperimen dengan satu ulangan yang lebih sedikit bagi operator Grover. Adakah kamu masih mendapat jawapan yang betul? Kenapa atau kenapa tidak?

Panduan:

Kamu mungkin ya, walaupun ia mungkin bergantung pada bilangan penyelesaian yang dikodkan. Ini menyerlahkan satu kehalusan: bilangan ulangan Grover yang "optimum" adalah bilangan yang menjadikan kebarangkalian mengukur keadaan yang ditanda setinggi mungkin. Tetapi ulangan yang lebih sedikit daripada itu mungkin masih menjadikan keadaan yang ditanda jauh lebih mungkin daripada keadaan lain. Oleh itu, kamu mungkin boleh menggunakan ulangan yang lebih sedikit daripada bilangan optimum. Ini mengurangkan kedalaman litar, dan dengan itu mengurangkan kadar ralat.

Mengapa seseorang mungkin mahu menggunakan ulangan Grover yang lebih sedikit daripada "bilangan optimum" yang dikenal pasti di sini?

Jawapan:

Bilangan ulangan Grover yang "optimum" adalah bilangan yang menjadikan kebarangkalian mengukur keadaan yang ditanda setinggi mungkin tanpa kehadiran bunyi. Tetapi ulangan yang lebih sedikit daripada itu mungkin masih menjadikan keadaan yang ditanda jauh lebih mungkin daripada keadaan lain. Jadi kamu mungkin boleh menggunakan ulangan yang lebih sedikit daripada bilangan optimum. Ini mengurangkan kedalaman litar, dan dengan itu mengurangkan kadar ralat.

Aktiviti 3: Kriteria selain daripada bitstring tertentu

Sebagai ilustrasi terakhir tentang bagaimana algoritma Grover mungkin berguna dalam konteks subrutin, bayangkan kita memerlukan keadaan kuantum dengan bilangan 1 tertentu dalam perwakilan bitstring. Ini biasa dalam situasi di mana hukum keabadian terlibat. Sebagai contoh, dalam konteks kimia kuantum, seseorang sering memetakan keadaan 1 pada suatu qubit kepada pendudukan orbital elektronik. Agar cas dapat dikekalkan, jumlah bilangan 1 juga mesti kekal tetap. Kekangan seperti ini sangat biasa sehingga mempunyai nama khas: kekangan berat Hamming, dan bilangan 1 dalam keadaan dipanggil berat Hamming.

Langkah 1:

Mari kita tulis terlebih dahulu fungsi yang menanda keadaan dengan berat Hamming yang dikehendaki. Kita akan menulis ini secara umum untuk bilangan qubit num_qubits dan berat Hamming sasaran target_weight yang tidak dinyatakan.

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, keseluruhan proses adalah sama dengan dua aktiviti sebelumnya. Untuk ringkasan, langkah-langkah corak Qiskit ditunjukkan hanya dalam ulasan kod 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 telah menyediakan keadaan dengan berat Hamming 2 supaya lebih mudah diukur berbanding keadaan lain, kira-kira satu peringkat magnitud lebih mungkin.

Konsep penting:

Dalam modul ini, kita telah mempelajari beberapa ciri utama algoritma Grover:

• Manakala algoritma carian tidak berstruktur klasik memerlukan bilangan pertanyaan yang berskala secara linear mengikut saiz ruang, $N,$ algoritma Grover memerlukan bilangan pertanyaan yang berskala seperti $\sqrt{N}.$
• Algoritma Grover melibatkan pengulangan siri operasi (biasanya dipanggil "operator Grover") sebanyak $t$ kali, dipilih untuk menjadikan keadaan sasaran paling mudah diukur.
• Algoritma Grover boleh dijalankan dengan ulangan yang kurang daripada $t$ dan masih menguatkan keadaan sasaran.
• Algoritma Grover sesuai dengan model pertanyaan pengiraan dan paling masuk akal apabila satu pihak mengawal carian dan pihak lain mengawal/membina oracle. Ia juga mungkin berguna sebagai subrutin dalam pengiraan kuantum yang lain.

Soalan

Soalan B/S:

1. B/S Algoritma Grover memberikan peningkatan eksponen berbanding algoritma klasik dalam bilangan pertanyaan yang diperlukan untuk mencari satu keadaan yang ditanda dalam carian tidak berstruktur.

2. B/S Algoritma Grover berfungsi dengan meningkatkan kebarangkalian bahawa keadaan penyelesaian akan diukur secara berulang.

3. B/S Semakin banyak kali kamu mengulang operator Grover, semakin tinggi kebarangkalian mengukur keadaan penyelesaian.

Soalan Pelbagai Pilihan:

1. Pilih pilihan terbaik untuk melengkapkan ayat. Strategi terbaik untuk berjaya menggunakan algoritma Grover pada komputer kuantum moden adalah dengan mengulang operator Grover...

• a. Hanya sekali.
• b. Sentiasa $t$ kali, untuk memaksimumkan amplitud kebarangkalian keadaan penyelesaian.
• c. Sehingga $t$ kali, walaupun lebih sedikit mungkin cukup untuk menjadikan keadaan penyelesaian menonjol.
• d. Tidak kurang daripada 10 kali.

2. Litar pertanyaan fasa ditunjukkan di sini yang berfungsi sebagai oracle untuk menanda keadaan tertentu dengan pembalikan fasa. Antara keadaan berikut, yang manakah ditanda oleh litar ini?

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

3. Katakan kamu ingin mencari tiga keadaan yang ditanda daripada set 128. Berapakah bilangan ulangan operator Grover yang optimum untuk memaksimumkan amplitud keadaan yang ditanda?

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

Soalan perbincangan:

1. Apakah syarat lain yang mungkin kamu gunakan dalam oracle kuantum? Pertimbangkan syarat yang mudah dinyatakan atau dikenakan pada bitstring tetapi bukan sekadar menulis bitstring yang ditanda.

2. Adakah kamu nampak sebarang masalah dengan penskalaan algoritma Grover pada komputer kuantum moden?