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 litar 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 litar Qiskit untuk menyediakan instance carian Grover dengan mudah. Primitif Sampler masa jalan membolehkan pelaksanaan litar Grover yang lancar.

Teori

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 litar kuantum yang melaksanakan algoritma Grover.

Algoritma Grover boleh dipecahkan kepada peringkat berikut:

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

Selalunya, get 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.

get Hadamard $H$ dikenali dan digunakan secara meluas dalam pengkomputeran kuantum. get 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 get 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 get 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 get Hadamard, tunjukkan bahawa aplikasi kedua get 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.

get $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, get $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 get 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 get 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 get 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 get 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 get 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 get 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.

Gambaran geometri

Contoh dua qubit di atas menunjukkan cara algebra berfungsi untuk kes kecil, tetapi ada cara yang lebih intuitif untuk memahami algoritma Grover: sebagai urutan pantulan geometri dalam satah dua dimensi. Di bawah kami huraikan gambaran ini. Anda juga boleh melihat kursus John Watrous Fundamentals of Quantum Algorithms untuk butiran lanjut.

Menyediakan satah. Kita boleh menguraikan keadaan superposisi awal $|\psi\rangle$ kepada dua komponen. Keadaan yang betul — yang kita cari — kita panggil $|A_1\rangle$. Setiap keadaan lain, yang digabungkan bersama, kita panggil $|A_0\rangle$. Secara definisi, $|A_1\rangle$ dan $|A_0\rangle$ adalah ortogon antara satu sama lain, jadi kita boleh memplotnya sebagai paksi berserenjang dalam ruang dua dimensi abstrak. Oleh kerana $|\psi\rangle$ adalah gabungan linear kedua-dua komponen ini, ia berada pada sudut kecil $\theta$ terhadap paksi $|A_0\rangle$ — hampir dengan $|A_0\rangle$, kerana pada permulaan, hanya sebahagian kecil keadaan berada dalam komponen yang betul $|A_1\rangle$.

Pantulan. Fakta matematik utama yang kita perlukan ialah operator berbentuk

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

memantulkan mana-mana keadaan terhadap paksi yang ditakrifkan oleh $|v\rangle.$ Untuk memahami mengapa, pertimbangkan dua kes: keadaan sepanjang $|v\rangle$ tidak berubah, dan keadaan berserenjang dengan $|v\rangle$ mendapat tanda nyahbalik. Mana-mana keadaan lain boleh diuraikan kepada dua komponen ini, dan operator bertindak ke atas setiap satu — yang merupakan tepat pantulan terhadap $|v\rangle$.

Rupa-rupanya, oracle dan langkah peresapan dalam algoritma Grover boleh dinyatakan sebagai pantulan dalam gambaran geometri ini.

Oracle sebagai pantulan. Oracle membalikkan tanda keadaan $|A_1\rangle$ dan membiarkan semua yang lain. Ini sama dengan pantulan terhadap paksi $|A_0\rangle$.

Peresapan sebagai pantulan. Sedikit lebih sukar untuk melihat bagaimana operator peresapan juga merupakan pantulan. Operator peresapan ialah

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

$Z_{\text{OR}}$ sendiri adalah pantulan terhadap keadaan semua-sifar, kerana ia membalikkan tanda setiap keadaan yang bukan $|0\rangle^{\otimes n}$. Ini boleh ditulis sebagai $2|0\rangle\langle 0| - I$. Lapisan Hadamard di sekeliling secara berkesan melakukan pertukaran asas, mengubah paksi pantulan. Ingat bahawa $H^{\otimes n}$ memetakan $|0\rangle^{\otimes n}$ kepada superposisi seragam $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Oleh kerana Hadamard adalah inversnya sendiri, ungkapan penuh menjadi

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

yang merupakan pantulan terhadap $|u\rangle$. Oleh kerana $|u\rangle$ sangat hampir dengan $|\psi\rangle$ (kedua-duanya hampir sepanjang $|A_0\rangle$), pantulan kedua ini menghantar keadaan ke sudut $2\theta$ dari tempat ia bermula.

Putaran sebanyak $2\theta$. Kesan gabungan kedua-dua pantulan ini adalah putaran sebanyak $2\theta$ ke arah $|A_1\rangle$. Setiap lelaran berturutan operator Grover memutar keadaan sebanyak $2\theta$ lagi.

Bilangan lelaran optimum. Matlamat kita adalah memutar keadaan sedekat mungkin dengan $|A_1\rangle$, yang bermakna memutar sebanyak kira-kira $\pi/2$ radian (satu suku pusingan). Jika setiap lelaran menyumbang $2\theta$, bilangan lelaran optimum $t$ memenuhi

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

Untuk satu penyelesaian dalam $N$ keadaan, sudut awal ialah $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (untuk $N$ besar). Dengan menggantikan,

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

Di sinilah pecutan $\sqrt{N}$ yang terkenal itu berasal: kita hanya memerlukan $O(\sqrt{N})$ lelaran untuk mencapai sasaran, berbanding pemeriksaan $O(N)$ yang diperlukan oleh carian klasik.

Secara lebih umum, jika terdapat $|A_1|$ keadaan penyelesaian dalam $N$ keadaan keseluruhan, bilangan lelaran optimum ialah

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

Perhatikan bahawa jika anda menggunakan terlalu banyak lelaran, anda akan memutar melepasi $|A_1\rangle$ dan kebarangkalian menemui keadaan sasaran akan mula menurun semula. Mencari bilangan lelaran yang betul adalah penting, walaupun pada perkakasan kuantum berderau bilangan optimum secara eksperimen mungkin berbeza daripada formula ideal ini.

Mengapa algoritma Grover berguna?

Pada ketika ini anda mungkin tertanya-tanya: kita baru membina oracle yang menanda keadaan sasaran — tetapi untuk membinanya, kita mesti mengetahui keadaan sasaran. Jadi apakah yang sebenarnya kita cari?

Ini adalah soalan yang wajar, dan terdapat beberapa jawapan yang baik.

• Model pertanyaan adalah alat teori. Model pertanyaan pengiraan tidak pernah direka untuk menjadi praktis secara langsung. Tujuannya adalah untuk memberi kita cara yang jelas untuk menganalisis kerumitan algoritma dengan memisahkan masalah kepada dua bahagian: oracle, dan segala-galanya yang lain. Betapa susahnya pencarian, memandangkan pengesahan adalah percuma? Bagaimanakah bilangan pertanyaan berskala dengan saiz input? Ini adalah soalan yang berguna walaupun tiada sistem sebenar yang berfungsi persis begini.

• Anda juga boleh memikirkannya sebagai aktiviti dua pihak: satu orang mengetahui keadaan sasaran dan membina oracle; tugas orang lain adalah mencari jawapan menggunakan oracle sebagai kotak hitam, tanpa mengintip ke dalam. Dalam Aktiviti 2 di bawah, anda akan melakukan tepat ini bersama rakan kongsi.

• Pengamplifikasian amplitud adalah subrutin yang berguna secara meluas. Walaupun demonstrasi pertama ini kelihatan bulat, mekanisme asas — yang dipanggil pengamplifikasian amplitud — muncul berulang kali dalam pengkomputeran kuantum. Apa yang kita bina di sini sebenarnya adalah intuisi untuk alat yang muncul sebagai subrutin dalam banyak algoritma kuantum yang lebih kompleks.

• Terdapat masalah di mana anda boleh membina oracle tanpa mengetahui jawapannya. Pandangan utama ialah terdapat satu kelas masalah yang mana adalah sangat sukar untuk mencari penyelesaian, tetapi sangat mudah untuk menyemak bahawa penyelesaian yang diberikan adalah betul. Pemfaktoran adalah satu contoh: diberikan hasil darab dua nombor perdana besar, adalah sangat sukar untuk menentukan nombor perdana tersebut, tetapi setelah anda memperolehnya, anda boleh dengan mudah mendarabkannya untuk mengesahkan. (Kita mempunyai algoritma yang lebih baik daripada Grover untuk pemfaktoran khususnya — lihat algoritma Shor — tetapi ini jauh dari satu-satunya masalah dengan ciri ini.) Sudoku, kepuasan kekangan, dan bahkan permainan klasik Minesweeper semuanya adalah masalah yang sukar diselesaikan tetapi mudah diperiksa.

Mengapa ia relevan? Ia bermakna kita boleh mengetahui semua syarat dan keperluan yang mesti dipenuhi oleh penyelesaian, dan kita boleh mengekod keperluan tersebut ke dalam litar kuantum yang berfungsi sebagai oracle — walaupun kita tidak mengetahui penyelesaiannya sendiri. Algoritma Grover akan mencarinya untuk kita.

Dengan idea-idea ini dalam fikiran, mari kita lalui beberapa contoh. Kita akan bermula dengan contoh di mana keadaan penyelesaian dinyatakan dengan jelas supaya kita boleh mengikuti logik algoritma. Kita kemudian akan beralih kepada aktiviti dua pihak, dan akhirnya kepada contoh di mana oracle dibina dari kekangan masalah dan bukan dari pengetahuan tentang jawapan.

Import umum dan pendekatan

Kita mulakan dengan mengimport beberapa pakej 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 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 get 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 get Z-terkawal, atau generalisasi berbilang-kawalannya ke atas $N$ qubit. Untuk melihat cara ini berfungsi, pertimbangkan contoh khusus rentetan bit {110}. Kita ingin sebuah litar 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 litar $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 get kawalan berbilang sasaran berbilang (MCMTGate) untuk menggunakan get 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 get X, kemudian lakukan get Z berbilang-kawalan, kemudian gunakan get 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); get mempengaruhi semua qubit secara setara. Ini berbeza daripada banyak get berbilang qubit lain, seperti get CX, yang mempunyai satu qubit kawalan dan satu qubit sasaran.

Dalam kod berikut, kita mentakrifkan get 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. get MCMT digunakan untuk melaksanakan get 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 litar 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$, get X pertama akan membalikkan qubit 0 ke $|1\rangle$ dan semua qubit akan berada dalam $|1\rangle.$ Ini bermakna get 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 litar ini memang menanda keadaan yang kita inginkan $|0111\rangle,$ atau rentetan bit {1110}.

Operator Grover penuh terdiri daripada get 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 bincangkan dalam gambaran geometri di atas, kita mungkin perlu menggunakan operator Grover beberapa kali. Bilangan lelaran optimum $t$ untuk memaksimumkan amplitud keadaan sasaran tanpa kehadiran hingar ialah

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

di mana $|A_1|$ ialah bilangan keadaan penyelesaian dan $N=2^n$ ialah jumlah bilangan keadaan. 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 litar yang merangkumi get 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 litar Grover kita!

Langkah 2: Optimumkan masalah untuk pelaksanaan perkakasan kuantum

Kita telah mentakrifkan litar kuantum abstrak kita, tetapi kita perlu menulis semula dalam bentuk get 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 litar 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 litar 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 litar 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 get kuantum (dan terutama get dua qubit) mengalami ralat dan tertakluk kepada hingar, satu siri lebih 100 get dua qubit akan menghasilkan hingar semata-mata jika qubit tidak berprestasi sangat tinggi. Mari kita lihat bagaimana prestasinya.

Langkah 3: 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 litar 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 litar 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 Anda beritahu rakan kongsi Anda berapa banyak keadaan yang Anda tandakan, supaya mereka boleh menerapkan operator Grover sebanyak bilangan kali yang optimum. Jangan buat bitstring Anda 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 Anda telah mencipta litar kuantum yang membalikkan fasa keadaan sasaran Anda. Anda 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 Anda (melalui e-mel, perkhidmatan pesanan, repo dikongsi, dan sebagainya). Minta rakan kongsi Anda hantar litar mereka kepada Anda juga. Pastikan Anda simpan fail tersebut di tempat yang mudah dicari. Setelah Anda mempunyai litar rakan kongsi Anda, Anda boleh menggambarkannya — tetapi itu akan melanggar model pertanyaan. Maksudnya, kita sedang memodelkan situasi di mana Anda 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 Anda 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 Anda. Satu atau lebih keadaan sepatutnya mempunyai kebarangkalian pengukuran yang jauh lebih tinggi daripada yang lain. Laporkan ini kepada rakan kongsi Anda dan semak sama ada Anda berjaya menentukan keadaan sasaran mereka. Secara lalai, histogram yang dipaparkan adalah dari litar yang sama dalam aktiviti pertama. Anda sepatutnya mendapat keputusan yang berbeza daripada litar rakan kongsi Anda.

plot_distribution(dist)

Semak kefahaman Anda

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

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

Petunjuk:

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

Jika Anda belum berbuat demikian, lukis litar oracle yang dihantar oleh rakan kongsi Anda. 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 Anda sudah mempunyai $|1\rangle$ pada qubit tertentu, maka Anda tidak perlu berbuat apa-apa pada qubit tersebut. Jika sasaran Anda mempunyai $|0\rangle$ pada qubit tertentu dan Anda mahukan MCMTGate membalikkan tanda, Anda perlu menerapkan gate X pada qubit tersebut dalam oracle Anda (dan kemudian membatalkan gate X selepas MCMTGate).

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

Panduan:

Anda 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, Anda 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 Anda mungkin boleh menggunakan ulangan yang lebih sedikit daripada bilangan optimum. Ini mengurangkan kedalaman litar, dan dengan itu mengurangkan kadar ralat.

Aktiviti 3: Selesaikan grid Minesweeper dengan algoritma Grover

Dalam bahagian sebelumnya, kita menyatakan bahawa algoritma Grover menjadi benar-benar berguna apabila kita boleh membina oracle daripada kekangan sesuatu masalah, bukan dari pengetahuan tentang jawapannya. Minesweeper adalah contoh yang sempurna: sel-sel bernombor memberitahu kita berapa banyak lombong yang bersebelahan, dan kekangan tersebut menentukan sepenuhnya di mana lombong-lombong itu berada — tetapi mencari konfigurasi memerlukan pencarian.

Minesweeper telah terbukti NP-lengkap: ia sukar diselesaikan tetapi mudah disemak. Ini menjadikannya calon semula jadi untuk algoritma Grover. Sudah tentu, kita belum boleh menyelesaikan grid 9$\times$9 penuh pada komputer kuantum berderau — litar-litar tersebut akan terlalu dalam. Sebaliknya, kita akan menggunakan grid kecil sebagai demonstrasi permainan tentang bagaimana seseorang akan mendekati papan yang lebih besar pada mesin toleran-kesalahan masa depan.

Beberapa kaveat penting. Algoritma Grover hanya menyediakan pecutan kuadratik berbanding carian klasik tidak berstruktur. Minesweeper hampir pasti mempunyai struktur yang boleh dieksploitasi yang boleh digunakan oleh algoritma klasik yang bijak. Dan untuk ruang carian yang berkembang secara eksponen, walaupun penambahbaikan $\sqrt{N}$ hanya dapat bertahan setakat itu. Tetapi mari kita ketepikan kebimbangan tersebut dan gunakan masalah permainan ini untuk menggambarkan bagaimana kekangan masalah dikodkan ke dalam oracle kuantum.

Grid

Berikut adalah grid minesweeper kecil kita:

Setiap sel kosong boleh diwakili oleh pemboleh ubah binari yang menunjukkan sama ada ia mengandungi lombong. Kita labelkan ini sebagai $x_0$, $x_1$, dan $x_2$, di mana $x_i = 1$ bermakna ada lombong pada sel tersebut dan $x_i = 0$ bermakna tiada:

Kita boleh menyelesaikan ini dalam kepala kita dalam kira-kira setengah saat, tetapi kita menggunakan masalah permainan ini untuk menggambarkan bagaimana papan yang jauh lebih susah boleh didekati dengan komputer kuantum.

Kodkan kekangan

Setiap sel bernombor meletakkan syarat pada sel-sel kosong yang bersebelahan. Kita perlu menyatakan syarat-syarat ini sebagai ungkapan Boolean yang boleh dikodkan ke dalam litar kuantum.

Sel "1" yang bersebelahan dengan $x_0$ dan $x_1$ mengatakan bahawa tepat satu daripada mereka mengandungi lombong. Ini adalah tepat operasi eksklusif-ATAU (XOR), $\oplus$, yang mengembalikan benar apabila tepat satu daripada inputnya adalah benar:

$$(x_0 \oplus x_1)$$

Begitu juga, sel "1" yang lain (bersebelahan dengan $x_1$ dan $x_2$) memberi kita:

$$(x_1 \oplus x_2)$$

Sel "2" mengatakan bahawa dua daripada tiga sel kosong mesti mengandungi lombong. Oleh kerana XOR adalah operasi pariti, $x_0 \oplus x_1 \oplus x_2$ mengembalikan benar apabila bilangan ganjil pemboleh ubah adalah benar. Kita mahukan bilangan genap (khususnya dua) yang benar, jadi kita menafi dengan $\lnot$:

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

Dengan sendirinya, ungkapan ini akan dipenuhi sama ada oleh sifar atau dua qubit dalam keadaan $|1\rangle$, kerana ia adalah kenyataan tentang pariti. Tetapi digabungkan dengan dua fasal lain, yang masing-masing memerlukan sekurang-kurangnya satu lombong, satu-satunya tugasan yang memuaskan mempunyai tepat dua lombong.

Semua tiga syarat mesti dipenuhi secara serentak, jadi kita menggabungkannya 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 kepada masalah kuantum

Sekarang kita perlu mengekod ungkapan Boolean ini ke dalam litar kuantum yang berfungsi sebagai oracle. Versi kuantum XOR boleh dicapai dengan get CX (CNOT): menggunakan dua get CX dari qubit data ke qubit ruang kerja (ancilla) secara berkesan mengira XOR mereka dan menyimpan hasilnya dalam ancilla.

Kita memperkenalkan tiga qubit ruang kerja — satu untuk setiap fasal. Kita menyimpan hasil setiap ungkapan Boolean dalam qubit ruang kerja yang sepadan, kemudian menggunakan get Z berbilang-kawalan untuk membalikkan fasa keadaan tiga-qubit yang menjadikan semua tiga qubit ruang kerja $|1\rangle$ (bermakna semua fasal dipenuhi secara serentak).

Dalam sel kod pertama di bawah, kita membina bahagian "kira" oracle — bahagian yang menilai setiap fasal dan menulis hasilnya ke dalam qubit ruang kerja.

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 ketika ini, hasil setiap fasal disimpan dalam qubit ruang kerja yang sepadan. Sekarang kita memerlukan keadaan data tiga-qubit yang menjadikan semua tiga qubit ruang kerja $|1\rangle$ mendapat tanda negatif. Kita melakukan ini dengan get Z berbilang-kawalan (dilaksanakan sebagai get MCX yang diapit oleh get Hadamard pada sasaran).

Selepas menggunakan pembalikan fasa, kita mesti nyahkira — membatalkan semua langkah penilaian fasal dalam urutan terbalik — untuk menetapkan semula qubit ruang kerja kembali ke $|0\rangle.$ Ini penting supaya qubit ruang kerja bersih untuk lelaran seterusnya 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")

Litar ini adalah oracle kita: ia membalikkan fasa keadaan qubit-data yang memenuhi semua tiga kekangan Minesweeper, dan membiarkan qubit ruang kerja kembali dalam $|0\rangle.$

Sekarang kita membina operator Grover penuh daripada oracle ini. Perhatikan argumen reflection_qubits: kita hanya menghantar qubit data x, kerana qubit ruang kerja bukan sebahagian dari ruang carian. Tugas mereka selesai setelah oracle digunakan.

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

Dengan tiga qubit data dan satu keadaan penyelesaian, bilangan lelaran Grover optimum ialah $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, jadi kita menggunakan dua lelaran. Kita menggunakan get Hadamard pada qubit data untuk mencipta superposisi awal, menyusun operator Grover dua kali, dan mengukur hanya qubit data.

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

Seperti sebelumnya, kita mentranspilkan litar untuk backend sasaran.

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 boleh menyemak kedalaman litar yang ditranspilkan. Oleh kerana oracle Minesweeper menggunakan qubit ruang kerja dan berbilang get CX, litar yang ditranspilkan akan lebih dalam daripada yang ada dalam aktiviti 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: Laksanakan menggunakan primitif Qiskit

# 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: Pasca-proses dan kembalikan keputusan dalam format klasik yang dikehendaki

plot_distribution(dist)

Keadaan 101 sepatutnya muncul dengan kebarangkalian yang jauh lebih tinggi berbanding yang lain, menunjukkan bahawa lombong-lombong terletak di $x_0$ dan $x_2$. Kita telah menggunakan komputer kuantum untuk menyelesaikan permainan Minesweeper kecil!

Sudah tentu, algoritma klasik terbaik untuk minesweeper adalah lebih baik daripada carian melulu melalui semua konfigurasi lombong yang mungkin — mereka mengeksploitasi struktur grid. Algoritma Grover hanya akan menawarkan kelebihan pada papan yang sangat sukar yang direka untuk paling kabur, dan walaupun begitu, pecutan kuadratik bermakna ia tidak dapat bersaing dengan pertumbuhan eksponen selama-lamanya. Tetapi pengambilan sebenar adalah tekniknya: mengekodkan kekangan masalah ke dalam oracle kuantum adalah corak yang berkuasa yang meluas kepada kepuasan kekangan, pengoptimuman kombinatorial, dan banyak domain lain.

Soalan dan konsep penting:

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.
• Oracle boleh dibina daripada kekangan masalah dan bukan dari pengetahuan tentang penyelesaian, seperti yang ditunjukkan dengan contoh Minesweeper.

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 Anda 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 Anda 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 masalah lain yang boleh anda rumuskan sebagai carian Grover? Fikirkan masalah di mana sukar untuk mencari penyelesaian tetapi mudah untuk mengesahkannya.

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