Aplikasi apa yang dimiliki Algoritma Pencarian Grover?

Algoritma Pencarian Grover biasanya dibicarakan dalam hal menemukan entri yang ditandai di basis data yang tidak disortir. Ini adalah formalisme alami yang memungkinkan diterapkan langsung untuk mencari solusi untuk masalah NP (di mana solusi yang baik mudah dikenali).

Saya tertarik untuk belajar tentang aplikasi lain dari pencarian Grover untuk menemukan minimum, rata-rata dan median dari serangkaian angka. Itu membuat saya bertanya-tanya apakah ada aplikasi lain yang kurang jelas dari pencarian Grover (atau aplikasi generalisasi seperti amplifikasi amplitudo) yang sudah dikenal? Setiap wawasan singkat tentang bagaimana hal ini dilakukan akan dihargai.

algorithm grovers-algorithm DaftWullie
sumber

Terlepas dari yang Anda sebutkan, aplikasi lain dari algoritma Grover (yang dimodifikasi) yang saya ketahui adalah memecahkan masalah Collision dalam teori kompleksitas, komputasi kuantum, dan matematika komputasi . Ini juga disebut algoritma BHT .

Pendahuluan :

Masalah tabrakan paling sering merujuk pada versi 2-ke-1 yang dijelaskan oleh Scott Aaronson dalam tesis PhD-nya. Mengingat bahwa adalah genap dan fungsi kita tahu sebelumnya bahwa adalah 1-ke-1 atau 2-ke -1. Kami hanya diperbolehkan membuat pertanyaan tentang nilai untuk setiap . Masalahnya kemudian bertanya berapa banyak pertanyaan yang perlu kita buat untuk menentukan dengan pasti apakah adalah 1-ke-1 atau 2-ke-1. $n$ $f:\{1,...,n\}\to\{1,...,n\}$ $f$ $f(i)$ $i\in\{1,2,...,n\}$ $f$

Memecahkan versi 2-ke-1 secara deterministik membutuhkan query, dan secara umum membedakan fungsi r-to-1 dari fungsi 1-ke-1 membutuhkan query. $n/2+1$ $n/r+1$

Solusi klasik deterministik :

Ini adalah penerapan langsung prinsip pigeonhole: jika suatu fungsi r-to-1, maka setelah kueri kami dijamin telah menemukan tabrakan. Jika suatu fungsi adalah 1-ke-1, maka tidak ada tabrakan. Jika kita kurang beruntung maka query dapat memberikan jawaban yang berbeda. Jadi permintaan diperlukan. $n/r+1$ $n/r$ $n/r+1$

Solusi klasik acak :

Jika kita membiarkan keacakan, masalahnya lebih mudah. Dengan paradoks ulang tahun, jika kita memilih kueri (berbeda) secara acak, maka dengan probabilitas tinggi kita menemukan tabrakan dalam fungsi 2-ke-1 yang tetap setelah kueri . $\Theta(\sqrt{n})$

Solusi BHT kuantum :

Secara intuitif, algoritma menggabungkan speedup akar kuadrat dari paradoks ulang tahun menggunakan keacakan (klasik) dengan speedup akar kuadrat dari algoritma (kuantum) Grover.

Pertama, input ke dipilih secara acak dan dipertanyakan semuanya. Jika ada tabrakan di antara input ini, maka kami mengembalikan pasangan input yang bertabrakan. Jika tidak, semua input ini dipetakan ke nilai yang berbeda oleh . Kemudian algoritma Grover digunakan untuk mencari input baru untuk yang bertabrakan. Karena hanya ada input untuk , algoritma Grover dapat menemukan satu (jika ada) dengan membuat hanya kueri ke . $n^{1/3}$ $f$ $f$ $f$ $f$ $n^{2/3}$ $f$ $\mathcal{O}(\sqrt{n^{2/3}})=\mathcal{O}(n^{1/3})$ $f$

Sumber:

Sanchayan Dutta
sumber

Beberapa komentar tentang solusi BHT (saya tidak menemukan artikel wikipedia sangat mencerahkan): Pertama, pilih untuk menguji secara acak. Anggaplah mereka tidak bertabrakan. Sortir nilai-nilai ini sesuai dengan . Sekarang, jika adalah 2-ke-1, ada nilai belum diuji yang bertabrakan dengan yang diuji. Jadi, tentukan fungsi yang memeriksa "belum diuji dan bertabrakan". Ini mendefinisikan entri yang ditandai. Tabrakan mudah untuk diuji dengan daftar nilai yang diurutkan . Mengetahui jumlah entri yang ditandai (jika 2 banding 1), Grover's (hampir) menjamin solusi.

n^{1 / 3}

$n^{1/3}$

f

$f$

x

$x$

f (x)

$f(x)$

f (x)

$f(x)$

n^{1 / 3}

$n^{1/3}$

x

$x$

f (x)

$f(x)$

DaftWullie

@ DavidWullie Ya, itu masuk akal. Algoritma Grover tidak menjamin solusi tetapi memiliki probabilitas tinggi untuk memberikan solusi yang benar. Tetapi bukankah itu cukup jelas dari deskripsi Wikipedia itu sendiri? Saya tidak yakin saya mengerti maksud atau keberatan yang Anda buat. Apakah saya melewatkan sesuatu?

Sanchayan Dutta

Yang bisa saya katakan adalah itu tidak jelas bagi saya . Pada bacaan pertama, saya mengerti (secara salah) bahwa untuk Grover, alih-alih menyiapkan superposisi dari semua kondisi yang mungkin, ia hanya menyiapkan superposisi atas yang belum diuji. Tapi itu sepertinya penting untuk cara mempercepat itu dijelaskan. Juga, saya awalnya khawatir tentang bagaimana tabrakan diperiksa: pasangan mana yang diperiksa untuk tabrakan, dan seberapa efisien tabrakan dapat dihitung?

DaftWullie

@ David Wullie Ah, oke. Saya mengerti maksud Anda. Wikipedia tidak membahas banyak tentang detail algoritma. Anda selalu dapat merujuk ke makalah asli ( arxiv.org/ab/quant-ph/9705002 ) untuk detailnya (yang saya rasa sudah Anda lakukan). Nanti, saya akan mencoba mengembangkan jawaban ini untuk memasukkan semua detail. Saya masih membaca koran.

Sanchayan Dutta

Kecuali jika qubit dan gerbang kuantum ternyata jauh lebih murah daripada bit dan gerbang klasik, setiap diskusi tentang BHT harus mencakup peringatan bahwa biaya melebihi pencarian tabrakan klasik canggih dengan mesin van Oorschot-Wiener. Lihat cr.yp.to/papers.html#collisioncost atau blog.cr.yp.to/20171017-collisions.html untuk detailnya. (Yang terakhir adalah respon terhadap dugaan peningkatan BHT yang mengklaim lebih hemat biaya daripada pencarian tabrakan klasik.)

Squeamish Ossifrage

Aplikasi apa yang dimiliki Algoritma Pencarian Grover?

Jawaban: