Algoritma Grover digunakan, antara lain, untuk mencari item dalam daftar item yang tidak terurut panjangnya . Meskipun ada banyak pertanyaan di sini mengenai topik ini, saya masih merindukan intinya. $\mathbf{y}$ $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ $n$

Mencari dalam daftar, cara klasik

Biasanya, saya akan merancang fungsi pencarian dengan cara ini Jadi saya memberikan daftar dan item yang diinginkan sebagai input, dan saya menerima posisi dari item dalam daftar sebagai keluaran. Saya pikir saya sudah mengerti bahwa informasi tentang tertanam dalam algoritma melalui gerbang oracle , jadi fungsi kita menjadi Mari kita buat contoh praktis. Pertimbangkan mencari kartu as sekop

s e a r c h ([x_{0}, x_{1}, . . ., x_{n - 1}], y) = i \in N such that x_{i} = y

$\mathrm{search}([\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}], \mathbf{y}) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$

y

$\mathbf{y}$

O

$O$

{s e a r c h}_{y} ([x_{1}, x_{2}, . . ., x_{n}]) = i \in N such that x_{i} = y

$\mathrm{search}_\mathbf{y}([\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n] ) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$

1 ♠

$1\spadesuit$ dalam urutan 8 kartu dari kartu 52 kartu standar :

Daftar panjang adalah . $8$ $[ \mathbf{x}_0 = J\clubsuit,$ $\mathbf{x}_1 = 10\diamondsuit,$ $\mathbf{x}_2 = 4\heartsuit,$ $\mathbf{x}_3 = Q\clubsuit,$ $\mathbf{x}_4 = 3\spadesuit,$ $\mathbf{x}_5 = 1\spadesuit,$ $\mathbf{x}_6 = 6\spadesuit,$ $\mathbf{x}_7 = 6\clubsuit]$

Elemen yang dicari adalah $\mathbf{x}_5$ . Saya harus mendapatkan $\mathrm{search}_{\spadesuit}(cards) = 5$ . Setiap kartu dapat dikodekan dengan $\lceil{\log_2 52}\rceil = 6$ bit, daftar ini memiliki $8$ elemen sehingga kita membutuhkan $6\times 8 = 48$ bit untuk menyandikan daftar. Dalam hal ini, oracle $O$ akan mengimplementasikan fungsi:

f (x) = {\begin{cases} 1, & x = 1 ♠ \\ 0, & otherwise \end{cases}

$f(\mathbf{x}) = \begin{cases} 1, & \mathbf{x} = 1\spadesuit \\ 0, & \text{otherwise} \end{cases}$

Namun, input dari algoritma Grover bukanlah keadaan $48$ qubit.

(NB: Gambar deck dikocok diambil dari sini )

Grover dan oracle-nya

Beberapa sumber (mis. Di sini - dijelaskan secara grafis) mengatakan bahwa input dari algoritma berbeda: input adalah keadaan yang diambil dari ruang pencarian mana adalah jumlah elemen dari daftar. Setiap angka sesuai dengan posisi elemen dalam daftar. $S = \{ 0, 1, 2, ..., N \} = \{0, 1, 2, ..., 7 \}$ $N$

Input sekarang menjadi vektor qubit , yang harus menjadi superposisi semua item di ruang pencarian . $\mathrm{search}_{\spadesuit}(\cdot)$ $\lceil \log_2 8 \rceil = 3$ $|\psi\rangle$ $S$

Kita tahu

$|0_{3\text{qubits}}\rangle = |000\rangle$ sesuai dengan ; $J\clubsuit$
$|1_{3\text{qubits}}\rangle = |001\rangle$ sesuai dengan ; $10\diamondsuit$
$|2_{3\text{qubits}}\rangle = |010\rangle$ sesuai dengan ; $4\heartsuit$
$|5_{3\text{qubits}}\rangle = |101\rangle$ sesuai dengan yang merupakan elemen yang diinginkan; $1\spadesuit$
dan seterusnya...

Dalam hal ini kita memiliki Tetapi dalam kasus ini, oracle kita harus mengimplementasikan fungsi

{s e a r c h}_{♠} (| ψ ⟩) = | 5_{3 qubits} ⟩

$\mathrm{search}_{\spadesuit}(|\psi\rangle) = |5_{3\text{qubits}}\rangle$

f (| ψ ⟩) = {\begin{cases} 1, & | ψ ⟩ = | 5_{3 qubits} ⟩ \\ 0, & otherwise \end{cases}

$f(|\psi\rangle) = \begin{cases} 1, & |\psi\rangle = |5_{3\text{qubits}}\rangle \\ 0, & \text{otherwise} \end{cases}$

Membangun oracle mengharuskan kita untuk mengetahui bahwa ada di posisi 5. Apa gunanya menjalankan algoritma jika kita sudah mencari elemen untuk membangun oracle? $\spadesuit$

grovers-algorithm incud
sumber

Saya juga mengalami kesulitan memahami keuntungan dari algoritma Grover. Misalkan saya memiliki N item dalam daftar. Pada setiap panggilan ke Oracle, apakah ia mengevaluasi semua kemungkinan N? Bahkan jika evaluasi sangat cepat tetapi jika kita masih perlu mengulangi semua konfigurasi, maka kompleksitas evaluasi Oracle adalah O (N). Jadi algoritma Grover sepertinya tidak lebih cepat daripada pencarian bodoh. Apakah ini benar?

Sanparith Marukatat

@SparparMarukatat Itu tidak benar. Item daftar Anda adalah ketentuan superposisi negara yang terlibat dalam pencarian. Ketika Oracle beroperasi pada kondisi ini, ia dianggap sebagai satu operasi. Kemampuan Oracle untuk menandai istilah superposisi yang Anda cari adalah bagian mendasar dari wawasan Grover. Untuk memahami algoritme Grover, saya sarankan Anda terlebih dahulu memahami bagaimana penandaan status yang diinginkan terjadi. Setelah itu, pastikan untuk memahami peran negara

di Oracle.

| - ⟩

$|- \rangle$

R. Chopin

Jika Anda memahaminya, maka Anda harus mempelajari operator yang mampu meningkatkan amplitudo dari istilah yang diinginkan dalam superposisi sementara pada saat yang sama mengurangi amplitudo dari ketentuan superposisi yang tidak diinginkan. Bagi saya cara termudah untuk mendekati Grover adalah dengan melihat operator invers-tentang-rata. (Beberapa orang mengambil tampilan geometris, tetapi saya tidak menemukannya dengan jelas.)

R. Chopin

10

Jika Anda memiliki 8 item dalam daftar (seperti pada contoh kartu Anda), maka input oracle adalah 3 (qu) bit. Jumlah kartu di dek (52) tidak relevan, Anda hanya perlu 3 bit untuk mengkodekan 8 kartu.

Anda dapat berpikir bahwa 3 bit mengkodekan posisi dalam daftar kartu yang Anda cari; maka Anda tidak tahu posisinya, tetapi oracle tahu. Jadi jika Anda mencari kartu as sekop, maka sang oracle tahu bahwa kartu as sekop adalah kartu ke-6 (atau penghitungan ke-5 dari nol) dan mengimplementasikan fungsi

f (x) = {\begin{cases} 1, & if x = 5, or binary '101' \\ 0, & otherwise \end{cases}

$f(\mathbf{x}) = \begin{cases} 1, & \text{if x = 5, or binary '101'} \\ 0, & \text{otherwise} \end{cases}$

PS: Lebih baik memikirkan algoritma Grover secara berbeda: Anda memiliki oracle yang mengimplementasikan fungsi boolean yang menghasilkan untuk kombinasi tunggal dari bit input, jika tidak menghasilkan nol, dan tugas Anda adalah menemukan kombinasi tersebut. Masalahnya memiliki kompleksitas yang sama dengan pencarian dalam daftar atau basis data yang tidak disortir, itulah sebabnya mengapa algoritma Grover biasanya digambarkan sebagai pencarian dalam database yang tidak disortir. Tetapi menerapkan algoritma untuk pencarian basis data dunia nyata memang menimbulkan pertanyaan yang berada di luar algoritma itu sendiri. Algoritma Grover hanya mencari apa yang diketahui oracle. $1$

kludg
sumber

Ya maaf, bahwa 6 adalah dari suntingan sebelumnya

incud

2

Terima kasih atas jawaban Anda. Saya memperbaiki kesalahan penulisan. Apa gunanya mengeksekusi algoritma jika untuk membangun oracle saya perlu mengetahui posisi elemen yang dicari?

incud

1

@incud Memang itu tidak masuk akal. Saya sudah memperbarui jawabannya.

kludg

" Algoritma Grover hanya mencari apa yang diketahui oracle ": belum tentu. Oracle mungkin memeriksa hanya beberapa properti spesifik dari input, sehingga hasil yang didapat pada akhirnya berisi lebih banyak informasi daripada yang dikodekan dalam oracle itsef. Contoh khas sedang mencari di buku telepon. Peramal "meminta" untuk catatan yang dilampirkan pada nama tertentu, tetapi begitu catatan yang benar ditemukan, orang juga mendapatkan informasi tambahan dari nomor telepon yang terlampir pada catatan itu, yang tidak dikodekan sama sekali di oracle

glS

4

Meskipun mungkin lebih mudah bagi kita untuk berpikir tentang fungsi oracle karena telah menghitung semua nilai-nilai ini, itu bukan apa yang dilakukannya. Dalam kasus yang Anda jelaskan, oracle memiliki 8 input yang mungkin (yaitu dikodekan dalam 3 (qu) bit), dan oracle melakukan semua perhitungan yang Anda butuhkan dengan cepat . Jadi, saat Anda mencoba mengevaluasi oracle untuk beberapa nilai , oracle mencari (dalam hal ini) kartu yang bernilai $x$ $x$ sesuai dengan, dan kemudian memeriksa apakah kartu itu adalah kartu yang ditandai. Idenya adalah bahwa setiap kali Anda memanggil oracle, itu melewati proses itu sekali. Secara keseluruhan, Anda mengevaluasi fungsi beberapa kali sama dengan berapa kali Anda memanggil oracle. Tujuan dari setiap algoritma pencarian adalah untuk memanggil oracle itu beberapa kali mungkin.

Dalam hal ini terdengar sedikit melingkar (diberi input , temukan kartu mana yang sesuai dengan), ingatlah bahwa tabel pencarian Anda untuk sesuai dengan kartu apa yang dapat dipesan yang merupakan pertanyaan pencarian yang berbeda, lebih sederhana, dan lebih cepat. $x$ $x$

Perbedaan utama dalam contoh Anda dibandingkan dengan skenario penggunaan yang lebih realistis adalah:

Ruang pencarian biasanya besar. Tidak ada prospek realistis untuk mengkomputasi semua nilai. Memang, itulah tepatnya yang kami coba hindari.
Biasanya, kita tidak benar-benar mengatakan 'menemukan kartu as sekop'. Sebaliknya, ada yang non-sepele untuk dievaluasi untuk menguji apakah adalah item yang 'ditandai' atau tidak. Fakta bahwa oracle dapat memakan waktu yang cukup lama untuk mengevaluasi, bahkan untuk satu entri, adalah apa yang membuat oracle menjadi bagian yang mahal untuk diimplementasikan (dan semua gerbang lainnya diberikan secara gratis) dan mengapa Anda perlu meminimalkan jumlah panggilan . $f(x)$ $x$

Jadi, sungguh, cara pencarian klasik akan mengatasi masalah Anda adalah: pilih secara acak. Evaluasi . Jika , kembalikan , jika tidak ulangi. Sementara efek bersih dari adalah 'adalah input , entri yang ditandai?', Itu bukan perhitungan aktual yang dilakukannya. $x$ $y=f(x)$ $y=1$ $x$ $f(x)$ $x_0$

DaftWullie
sumber

2

Pertanyaannya adalah akhirnya: "Apa gunanya mengeksekusi algoritma jika kita sudah mencari elemen untuk membangun oracle?"

Sementara seseorang membuat ulang oracle, itu mungkin bukan orang yang menggunakan oracle.

$\sqrt{\text{size of list}}$

Kami bertanya pada oracle: apa jawaban yang sudah dimilikinya untuk pertanyaan yang sudah dimilikinya? Bahkan Mateus dan Omar akan menanyakan "oracle-for-a-alphabet-symbol" selama runtime, apa posisi simbol-simbolnya dalam string yang telah dikompilasi? Oracle akan memberikan jawaban atas pertanyaan kami setelah hanya satu kali konsultasi, tetapi dalam cerita ini, tidak bisa misalnya menuliskan jawaban sebagai string biner dan mengirimkannya kepada kami melalui saluran komunikasi klasik. Itu akan menyembunyikan jawabannya dalam superposisi bagi kita untuk menariknya keluar.

Saya membiarkan angan-angan atau kiasan melarikan diri dalam bagian berikutnya: kita tidak cukup mendengar jawaban pertama kali, dan kita harus meminta oracle untuk mengulangi jawaban yang sama berulang-ulang sampai kita yakin apa yang dikatakan oracle, kecuali kita mulai berhalusinasi dari kesalahan informasi dalam proses difusi jika kita bertanya terlalu banyak.

Brendan M
sumber

2

Mengingat oracle yang Anda berikan, pencarian itu memang tidak ada gunanya. Namun, oracle itu melewatkan titik algoritma Grover karena mencari kartu di setumpuk kartu bukanlah pencarian yang tidak terstruktur karena, seperti yang Anda nyatakan, Anda sudah mengetahui urutannya. Ergo, pencarian Anda terstruktur. Alasan oracle ini digunakan adalah karena itu menunjukkan bagaimana Grover dapat diterapkan tanpa harus membahas oracle yang akan membuat Grover berguna karena oracle tersebut akan lebih rumit daripada berharga. Oleh karena itu, ramalan yang lebih baik untuk menunjukkan manfaat Grover mungkin seperti:

f (x) = {\begin{cases} 1, & x [0, \dots, 3] + x [4, \dots, 7] = 1010 \\ 0, & otherwise \end{cases}

$f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & \text{otherwise} \end{cases}$

Apa yang disiratkan oleh oracle ini adalah bahwa Anda memiliki pencarian 8-qubit di mana Anda mengambil empat qubit pertama dan menambahkannya ke empat qubit kedua dan membalikkan M jika penambahan menghasilkan 10 (1010 dalam biner). Perbedaan antara oracle ini dan yang Anda berikan adalah bahwa oracle ini menguji sebuah pola (apakah operan menambah 10) sedangkan Anda menguji kesetaraan (adalah indeks ini 5). Peramal ini jauh lebih sulit untuk dibangun tetapi memanfaatkan kekuatan sebenarnya dari Grover, yang pada dasarnya adalah pencarian dengan kekuatan besar di mana oracle Anda menentukan ruang pencarian.

Woody1193
sumber

Algoritma Grover: di mana daftarnya?

Mencari dalam daftar, cara klasik

Grover dan oracle-nya

Jawaban: