Teori algoritma pencarian Grover

Pada artikel ini Anda akan menemukan penjelasan teoritis terperinci tentang prinsip-prinsip matematika yang membuat algoritma Grover bekerja.

Untuk implementasi praktis algoritma Grover untuk memecahkan masalah matematika, lihat Menerapkan algoritma pencarian Grover.

Pernyataan masalah

Algoritma Grover mempercepat solusi untuk pencarian data yang tidak terstruktur (atau masalah pencarian), menjalankan pencarian dalam langkah yang lebih sedikit daripada algoritma klasik apa pun. Setiap tugas pencarian dapat dinyatakan dengan fungsi abstrak $f(x)$ yang menerima item pencarian $x$. Jika item $x$ adalah solusi untuk tugas pencarian, maka $f(x)=1$. Jika item $x$ bukan solusi, maka $f(x)=0$. Masalah pencarian terdiri dari menemukan item $x_0$ apa pun sedemikian rupa sehingga $f(x_0)=1$.

Masalah apa pun yang memungkinkan Anda memeriksa apakah nilai yang diberikan $x$ adalah solusi yang valid (kutipan &; ya atau tidak ada masalah&kutipan;) dapat diformulasikan dalam hal masalah pencarian. Berikut ini adalah beberapa contoh:

• Masalah keterpuasan Boolean: Diberikan sebuah himpunan nilai Boolean, apakah himpunan tersebut memenuhi rumus Boolean tertentu?
• Masalah penjual keliling: Apa rute terpendek yang bisa menghubungkan semua kota?
• Masalah pencarian database: Apakah tabel database berisi rekaman $x$?
• Masalah faktorisasi bilangan bulat: Apakah angka $N$ dapat dibagi berdasarkan angka $x$?

Tugas yang algoritma Grover bertujuan untuk memecahkan dapat dinyatakan sebagai berikut: mengingat fungsi klasik $f(x):\{0,1\}^n \rightarrow\{0,1\}$, di mana $n$ merupakan bit-size dari ruang pencarian, temukan input $x_0$ yang $f(x_0)=1$. Kompleksitas algoritma diukur dengan jumlah penggunaan fungsi $f(x)$. Secara klasik, dalam skenario terburuk, $f(x)$ harus dievaluasi total $N-1$ kali, di mana $N=2^n$, mencoba semua kemungkinan. Setelah elemen $N-1$, elemen tersebut harus menjadi elemen terakhir. Algoritma kuantum Grover dapat memecahkan masalah ini lebih cepat, memberikan kecepatan kuadrat. Kuadrat di sini menyiratkan bahwa hanya tentang evaluasi $\sqrt{N}$ yang diperlukan, dibandingkan dengan $N$.

Garis besar algoritma

Misalkan ada item $N=2^n$ yang memenuhi syarat untuk tugas pencarian dan mereka adalah indeks dengan menetapkan setiap item bilangan bulat dari $0$ sampai $N-1$. Selanjutnya, misalkan ada $M$ input valid yang berbeda, yang berarti bahwa ada input $M$ yang $f(x)=1$. Langkah-langkah algoritma adalah sebagai berikut:

1. Mulailah dengan daftar $n$ qubit yang diinsialisasi di status $\ket{0}$.
2. Siapkan register ke dalam superposisi seragam dengan menerapkan $H$ ke setiap qubit register: $$|\text{register}\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$
3. Terapkan operasi berikut ke register $N_{\text{sebanyak}}$ kali secara optimal:
   1. Oracle fase $O_f$ yang menerapkan pergeseran fase bersyarat $-1$ untuk item solusi.
   2. Terapkan $H$ ke setiap qubit dalam register.
   3. Pergeseran fase bersyarat $-1$ ke setiap kondisi dasar komputasi kecuali $\ket{0}$. Ini dapat diwakili oleh operasi $kesatuan -O_0$, karena $O_0$ mewakili pergeseran fase bersyarat menjadi hanya $\ket{0}$.
   4. Terapkan $H$ ke setiap qubit dalam register.
4. Ukur register untuk mendapatkan indeks item yang merupakan solusi dengan probabilitas yang sangat tinggi.
5. Periksa apakah itu solusi yang valid. Jika tidak, mulailah lagi.

$N_{\text{}}=\leftoptimal \lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\r$ lantai adalah jumlah perulangan optimal yang memaksimalkan kemungkinan mendapatkan item yang benar dengan mengukur register.

Operasi kesatuan keseluruhan yang diterapkan pada register adalah:

$$(-H^{\otimes n}O_0H^{\otimes n}O_f)^{N_{\text{optimal}}}H^{\otimes n}$$

Mengikuti status register langkah demi langkah

Untuk mengilustrasikan prosesnya, mari kita ikuti transformasi matematis dari kondisi register untuk kasus sederhana di mana hanya ada dua qubit dan elemen yang valid adalah $\ket{01}.$

1. Pendaftaran dimulai dengan status:

   $$\ket{\text{mendaftarkan}}=\ket{{00}$$

2. Setelah menerapkan $H$ ke setiap qubit, status register berubah menjadi:

   $$\ket{\text{mendaftarkan}}=\frac{{1}{\sqrt{4}}\sum_{i \in \lbrace 0,1 \r}^2\ket{i}=\frac12(\ket{00}+\ket{01}+\ket{{10}+\ket{11})$$

3. Kemudian, phase oracle diterapkan untuk mendapatkan:

   $$\ket{\text{mendaftarkan}}=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$$

4. Kemudian $H$ bertindak pada setiap qubit lagi untuk memberikan:

   $$\ket{\text{mendaftarkan}}=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$$

5. Sekarang pergeseran fase kondisional diterapkan pada setiap status kecuali $\ket{00}$:

   $$\ket{\text{mendaftarkan}}=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$$

6. Akhirnya, iterasi pertama dari Grover berakhir dengan menerapkan $H$ sekali lagi untuk mendapatkan:

   $$\ket{\text{mendaftarkan}}=\ket{{01}$$

Dengan mengikuti langkah-langkah di atas, item yang valid ditemukan dalam satu iterasi. Seperti yang akan Anda lihat nanti, ini karena untuk N=4 dan satu item yang valid, jumlah waktu optimal adalah $N_{\text{optimal}}=1$.

Penjelasan geometris

Untuk melihat mengapa algoritma Grover bekerja, mari kita pelajari algoritma dari perspektif geometris. Menyangkut terdapatnya $M$ solusi yang valid, superposisi dari semua status kuantum yang bukan merupakan solusi untuk masalah pencarian:

$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$

Superposisi semua keadaan yang merupakan solusi untuk masalah pencarian:

$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$

Karena baik dan buruk saling mengecualikan satu sama lain, sebab sebuah item tidak bisa valid dan tidak valid secara bersamaan, kondisinya menjadi ortogonal. Kedua status membentuk dasar ortogonal dari bidang di ruang vektor. Seseorang dapat menggunakan bidang ini untuk memvisualisasikan algoritma.

Sekarang, misalkan $\ket{\psi}$ adalah kondisi arbitrary yang hidup di pesawat yang membentang oleh $\ket{\text{baik}}$ dan $\ket{\text{buruk}}$. Setiap status yang tinggal di pesawat itu dapat dinyatakan sebagai:

$$\ket{\psi} = \alpha \ket{\text{baik}} + \beta\ket{\text{buruk}}$$

di mana $\alpha$ dan $\beta$ adalah bilangan real. Sekarang, mari kita perkenalkan operator refleksi $R_{\ket{\psi}}$, di mana $\ket{\psi}$ kondisi qubit yang tinggal di pesawat. Operator didefinisikan sebagai:

$$R_{\ket{\psi}}=2\ket{\psi}\bra{\psi}-\mathcal{I}$$

Ini disebut operator refleksi tentang $\ket{\psi}$ karena dapat ditafsirkan secara geometris sebagai refleksi tentang arah $\ket{\psi}$. Untuk melihatnya, ambil dasar ortogonal dari bidang yang dibentuk oleh $\ket{\psi}$ dan pelengkap $\ket{\psi^{\perp}}$ ortogonalnya. Setiap kondisi $\ket{\xi}$ pesawat dapat diuraikan dalam dasar seperti:

$$\ket{\xi}=\mu \ket{\psi} + \nu {\ket{\psi^{\perp}}}$$

Jika salah satu menerapkan operator $R_{\ket{\psi}}$ to $\ket{\xi}$:

$$R_{\ket{\psi}}\ket{\xi}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$

Operator $R_{\ket{\psi}}$ membalikkan komponen orthogonal ke $\ket{\psi}$ tetapi membiarkan komponen $\ket{\psi}$ tidak berubah. Oleh karena itu, $R_{\ket{\psi}}$ adalah refleksi tentang $\ket{\psi}$.

Algoritma Grover, setelah aplikasi pertama $H$ untuk setiap qubit, dimulai dengan superposisi seragam dari semua status. Ini dapat ditulis sebagai:

$$\ket{\text{all}}=\sqrt{\frac{M}{N}}\ket{\text{good}} + \sqrt{\frac{N-M}{N}}\ket{\text{bad}}$$

Dan dengan demikian status tinggal di pesawat. Perhatikan bahwa probabilitas mendapatkan hasil yang benar ketika mengukur dari superposisi yang sama hanya $|\bra{\text{baik}}\ket{\text{semua}}|^2=M/N$, yang akan Anda harapkan dari tebakan acak.

Oracle $O_f$ menambahkan fase negatif ke solusi apa pun untuk masalah pencarian. Oleh karena itu, dapat ditulis sebagai refleksi tentang sumbu $\ket{\text{buruk}}$ :

$$O_f = R_{\ket{\text{buruk}}}= 2\ket{\text{buruk}}}}\bra{\text{buruk - \mathbb{saya}$$

Analoginya, pergeseran fase bersyarat $O_0$ hanyalah refleksi terbalik tentang kondisi $\ket{0}$:

$$O_{0}= R_{\ket{0}}= -2\ket{{0}\bra{{0} + \mathbb{I}$$

Mengetahui fakta ini, mudah untuk memeriksa bahwa operasi difusi Grover $-H^{\otimes n} O_{0} H^{\otimes n}$ juga merupakan cerminan terhadap keadaan $\ket{semua}$. Lakukan saja:

$$-H^{\otimes n} O_{{0} H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^{\otimes n} -H^{\otimes n}\mathbb{saya}H^{\otimes n}= 2\ket{\text{semua}}\bra{\text{semua}} - \mathbb{saya}= R_{\ket{\text{semua}}}$$

Telah ditunjukkan bahwa setiap iterasi algoritma Grover adalah komposisi dari dua refleksi $R_{\ket{\text{bad}}}$ dan $R_{\ket{\text{semua}}}$.

Efek gabungan dari setiap iterasi Grover adalah rotasi berlawanan arah jarum jam dari sudut $2\theta$. Untungnya, sudut $\theta$ mudah ditemukan. Karena $\theta$ hanyalah sudut antara $\ket{\text{semua}}$ dan $\ket{\text{buruk}}$, seseorang dapat menggunakan produk skalar untuk menemukan sudutnya. Diketahui bahwa $\cos{\theta}=\braket{\text{all}|\text{bad}}$, jadi seseorang perlu menghitung $\braket{\text{all}|\text{bad}}$. Dari dekomposisi $\ket{\text{semua}}$ dalam hal $\ket{\text{buruk}}$ dan $\ket{\text{baik}}$, berikut:

$$\theta = \arccos{\left(\braket{\text{all}|\text{bad}}\right)}= \arccos{\left(\sqrt{\frac{N-M}{N}}\right)}$$

Sudut antara status register dan $\ket{\text{status yang baik}}$ berkurang dengan setiap iterasi, menghasilkan probabilitas yang lebih tinggi untuk mengukur hasil yang valid. Untuk menghitung probabilitas ini, Anda hanya perlu menghitung $|\braket{\text{register}|\text{^2}}| yang baik$. Sudut antara $\ket{\text{baik}}$ dan register $\ket{\text{}}$ dinyatakan sebagai $\gamma (k)$, di mana $k$ adalah jumlah iterasi:

$$\gamma = \frac{\pi}{2}-\theta -2k\theta =\frac{\pi}{{2} -(2k + 1) \theta $$

Oleh karena itu, probabilitas keberhasilan adalah:

$$P(\text{success}) = \cos^2(\gamma(k)) = \sin^2\left[(2k +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)\right]$$

Jumlah iterasi yang optimal

Karena probabilitas keberhasilan dapat ditulis sebagai fungsi dari jumlah iterasi, jumlah optimal iterasi $N_{\text{optimal}}$ dapat ditemukan dengan menghitung bilangan bulat positif terkecil yang (kira-kira) memaksimalkan fungsi probabilitas keberhasilan.

Diketahui bahwa $\sin^2{x}$ mencapai maksimum pertama untuk $x=\frac{\pi}{2}$, jadi:

$$\frac{\pi}{{2}=(}} optimal 2k_{\text{+1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)$$

Ini memberikan:

$$k_{\text{optimal}}=\frac{\pi}{4\arccos\left(\sqrt{1-M/N}\right)}-1/2 =\frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{2}-O\left(\sqrt\frac{M}{N}\right)$$

Di mana pada langkah terakhir, $\arccos \sqrt{1-x}=\sqrt{x} + O(x^{3/2})$.

Oleh karena itu, Anda dapat memilih $N_{\text{}}=\leftoptimal \lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\rfloor$.

Analisis kompleksitas

Dari analisis sebelumnya, kueri $O\left(\sqrt{\frac{N}{M}}\right)$ dari oracle $O_f$ diperlukan untuk menemukan item yang valid. Namun, dapatkah algoritma diimplementasikan secara efisien dalam hal kompleksitas waktu? $O_0$ didasarkan pada komputasi operasi Boolean pada $n$ bit dan diketahui dapat diimplementasikan menggunakan gerbang $O(n)$. Ada juga dua lapisan $n$ gerbang Hadamard. Kedua komponen ini dengan demikian hanya membutuhkan gerbang $O(n)$ per iterasi. Karena $N=2^n$, maka $O(n)=O(log(N))$. Oleh karena itu, jika iterasi $O\left(\sqrt{\frac{N}{M}}\right)$ dan gerbang $O(log(N))$ per iterasi diperlukan, kompleksitas total waktu (tanpa memperhitungkan implementasi oracle) adalah $O\left(\sqrt{\frac{N}{M}}log(N)\right)$.

Kompleksitas keseluruhan algoritma pada akhirnya tergantung pada kompleksitas implementasi O_f$ oracle$. Jika evaluasi fungsi jauh lebih rumit pada komputer kuantum daripada pada yang klasik, runtime algoritma keseluruhan akan lebih lama dalam kasus kuantum, meskipun secara teknis, ia menggunakan lebih sedikit kueri.

Referensi

Jika Anda ingin terus belajar tentang algoritma Grover, Anda dapat memeriksa salah satu sumber berikut:

• Karya ilmiah asli oleh Lov K. Grover
• Algoritma pencarian kuantum bagian Nielsen, M. A. &Amp; Chuang, I. L. (2010). Quantum Computation and Quantum Information.
• Algoritma Grover tentang Arxiv.org

Konten terkait

• Entanglement dalam komputasi kuantum
• Vektor dan matriks
• Gerbang T dan pabrik T
• Beberapa qubit