Algoritma Grover untuk pencarian basis data: di mana keuntungan kuantum?

8

Saya telah mencoba untuk memahami apa yang bisa menjadi keuntungan menggunakan algoritma Grover untuk mencari di database D (kunci, nilai) yang sewenang-wenang dengan nilai-nilai N daripada pencarian klasik.

Saya berasumsi bahwa fungsi oracle adalah fungsi f (key) = y, di mana y adalah indeks dari nilai yang sesuai dalam database klasik.

Masalah saya terkait dengan oracle. Sirkuit oracle harus dimodifikasi untuk setiap pencarian dilakukan dalam database karena kunci ditentukan dalam oracle. Mari kita asumsikan ini adalah operasi yang diabaikan untuk kesederhanaan.

Andaikata sirkuit oracle harus dihitung secara klasik, maka akan diperlukan untuk menghasilkan sirkuit yang berperilaku seperti fungsi f (kunci) = y. Fungsi ini akan diperoleh setidaknya dalam langkah O (N) (kecuali untuk beberapa kasus khusus). Sirkuit fungsi oracle harus dihitung ulang setiap kali entri database sedang dimodifikasi / ditambahkan / dihapus, dengan biaya O (N).

Banyak makalah seperti Implementasi Algoritma Quantum untuk Pemula , Algoritma Quantum untuk Pencocokan dan Aliran Jaringan tampaknya tidak mempertimbangkan oracle sama sekali.

Saya tidak tahu apakah saya harus mempertimbangkan database kuantum untuk mendapatkan keuntungan nyata atau tidak ( ini dan hasil kuantum yang tidak dapat diandalkan meyakinkan saya bukanlah ide yang sangat bagus, tetapi itu hanya dugaan).

Jadi, di mana dianggap kompleksitas untuk membangun oracle? Apakah saya salah mengerti sesuatu?

Apakah "Rangkaian fungsi oracle harus dihitung ulang setiap kali entri database sedang dimodifikasi / ditambahkan / dihapus, dengan biaya O (N)" asumsi yang salah?

algorithm grovers-algorithm quantum-advantage Moreno G
sumber

mengapa Anda mengatakan bahwa " Rangkaian fungsi oracle harus dihitung ulang setiap kali entri database sedang dimodifikasi / ditambahkan / dihapus "? Fungsi oracle hanya perlu menjadi versi reversibel dari sirkuit klasik yang memeriksa apakah kunci yang diberikan adalah yang Anda cari. Mengubah jumlah kunci (yaitu elemen apa yang ada dalam database) tidak mengharuskan Anda untuk mengubah struktur oracle, sama seperti itu tidak mengharuskan Anda untuk mengubah fungsi klasik yang akan Anda gunakan untuk pencarian normal

glS

Nah, masalahnya adalah "hanya perlu versi reversibel dari sirkuit klasik". Jika itu akan menjadi korrispondensi sepele 1: 1 antara algoritma klasik dan yang kuantum, akan ada semacam kompiler dari bahasa pemrograman klasik ke sirkuit kuantum. Mengubah hal-hal dari algoritma klasik "sebagaimana adanya" menjadi yang kuantum selalu bagi saya merupakan ide yang buruk, juga karena sebagian besar operasi hampir tidak berskala ( lihat implementasi nCNOT ).

Moreno G

Di sirkuit kuantum, Anda tidak memiliki akses ke database klasik fisik. Sistem "komputer kuantum" berinteraksi dengan: - Uraian skema rangkaian, yang diberikan oleh (biasanya) program klasik sebagai input; - Hasil dari eksekusi sebagai output. Selama eksekusi, tidak ada akses ke sumber daya eksternal lainnya (saya tidak yakin apakah ini berdasarkan desain atau batasan teknologi aktual). Jadi, mengetahui bahwa oracle menggambarkan basis data dan kuncinya, itu harus dimodifikasi. Dan ini seringkali merupakan operasi yang tidak sepele

Moreno G

2

$\tilde \Omega(n)$ $O(n^{0.99})$ $\tilde \Omega(n^{1.5})$ $O(n^{0.5})$

Algoritma Grover hanya memiliki keunggulan ketika hal yang Anda cari bersifat abstrak, seperti solusi yang mungkin untuk masalah SAT, yang bertentangan dengan yang secara harfiah disimpan di perangkat keras di suatu tempat, seperti database.

Craig Gidney
sumber

n

$n$

n

$n$

n

$n$

O (\log_{2} n)

$O(\log_2 n)$

2^{w 2^{n}}

$2^{w 2^n}$

n

$n$

w

$w$

n^{O (1)}

$n^{O(1)}$

W

$W$

(n^{O (1)})^{M} = 2^{(2^{n})}

$(n^{O(1)})^M = 2^{(2^n)}$

n

$n$ satu-panas nubuat, menghindari hal penghitungan, Anda akan perlu untuk mengulangi data klasik sebagai bagian dari membangun sirkuit kuantum. Saya kira secara filosofis saya keberatan dengan penggunaan model RAM ketika membandingkan jenis komputasi yang sangat berbeda.

Craig Gidney

w

$w$

w

$w$

2^{w}

$2^w$

w

$w$

n

$n$

w

$w$

M

$M$

W

$W$

Singkatnya, apa yang ingin saya katakan adalah akan lebih baik jika Anda dapat memperluas jawaban ini. Tampaknya ada informasi berguna di sini. Apakah argumen penghitungan seperti ini berasal dari suatu tempat? Saya belum pernah melihatnya sebelumnya

glS

w 2^{w}

$w 2^w$

w

$w$

w

$w$

w

$w$

6

Anda benar untuk mengenali kompleksitas membangun oracle untuk menggunakannya dengan pencarian Grover - itu memang bagian yang sulit untuk menyelesaikan masalah, dan memang banyak sumber tidak mempertimbangkan kompleksitas ini.

Saya suka berpikir tentang oracle sebagai alat untuk mengenali jawabannya, bukan untuk menemukannya. Misalnya, jika Anda ingin menyelesaikan masalah SAT , sirkuit oracle akan menyandikan rumus Boolean untuk contoh spesifik masalah yang Anda coba selesaikan. Ukuran sirkuit dalam hal ini tergantung pada ukuran formula, dan bukan pada ukuran ruang pencarian. Anda dapat menemukan contoh penerapan oracle untuk contoh masalah SAT di tutorial saya .

Jika Anda menggunakan algoritma Grover untuk pencarian basis data, oracle harus menyandikan kondisi yang Anda cari, tetapi juga kriteria apakah elemen tersebut ada dalam database. Misalnya, jika Anda mencari nama yang dimulai dengan A, oracle perlu mengenali semua string yang dimulai dengan A, tetapi juga perlu mengenali yang mana dari string yang ada dalam database - jika tidak, algoritma akan menghasilkan string acak dimulai dengan A, yang mungkin bukan yang Anda cari. (Ini bukan masalah dengan contoh masalah SAT, karena setiap penugasan variabel yang memenuhi rumus adalah penugasan variabel yang valid.)

Saya tidak tahu contoh yang baik dari menggunakan pencarian Grover untuk mencari melalui database yang tidak terstruktur - sejauh yang saya pahami, algoritma ini cocok untuk pencarian yang memiliki struktur. Perlu memeriksa pertanyaan lain tentang Grover di situs ini, karena banyak dari mereka akan mempertimbangkan implementasi oracle.

Mariia Mykhailova
sumber

Saya memiliki beberapa keraguan tentang keberadaan cara umum yang baik untuk membangun oracle, jika tidak saya akan berharap untuk menemukannya setidaknya ada implementasi oracle. Memang, tampaknya menggunakan algoritma grover untuk mencari di database adalah aplikasi yang buruk. Saya sepenuhnya setuju tentang aplikasi pemecahan SAT, lebih cocok dengan apa yang memungkinkan algoritma Grover lakukan.

Moreno G

5

Masalahnya adalah dengan asumsi awal Anda: oracle untuk Grover didasarkan pada fungsi f (nilai) = 0/1, di mana 1 menunjukkan bahwa nilai tersebut memenuhi kriteria pencarian Anda dan 0 menunjukkan bahwa itu tidak. Ini berarti Anda harus membuat oracle baru untuk setiap pencarian yang berbeda, tetapi tidak untuk setiap database yang berbeda.

Yang mengatakan, algoritma Grover dan database kuantum tidak membuat pengganti yang baik untuk metode pencarian basis data klasik. Lihatlah makalah ini untuk diskusi tentang kepraktisan algoritma Grover dalam konteks ini.

Algoritma Grover memiliki aplikasi praktis ketika digeneralisasikan ke amplifikasi amplitudo , yang muncul sebagai komponen dari banyak algoritma kuantum lainnya. Amplifikasi amplitude adalah cara untuk meningkatkan kemungkinan keberhasilan suatu algoritma kuantum probabilistik.

Alan Geller
sumber

"Meskipun algoritma Grover memenuhi Persyaratan 2 pada prinsipnya, memuaskannya dengan margin yang signifikan pada skala log mungkin sulit dalam banyak kasus karena implementasi sirkuit kecil dari fungsi oracle p (x) mungkin tidak ada atau mungkin memerlukan alasan yang tidak masuk akal upaya untuk menemukan. " Ini adalah dugaan yang sama dengan yang saya temukan. Yang ingin saya ketahui adalah apakah pencarian basis data adalah aplikasi yang buruk untuk algoritma Grover atau tidak. Apakah ada bukti resmi dari apa yang dikatakan di sini?

Moreno G

Juga, itu tidak sepenuhnya benar, implementasi ini memang memberikan hasil (bisa berguna ketika lebih dari satu elemen ditandai)

Moreno G

1

Algoritma Grover adalah pemecah SAT-sirkuit (kuantum). Saya kira itu bisa juga menjadi pemecah kotak hitam secara harfiah, tetapi itu hanya akan bekerja dengan kotak hitam yang tidak menentukan status input Anda yang terjerat, dan saya mengalami kesulitan mempercayai bahwa hal-hal seperti itu ada.

Saya tidak tahu mengapa Grover atau orang lain menyebutnya sebagai algoritma pencarian basis data. Anda tentu saja dapat memberikannya rangkaian yang mengimplementasikan tes keanggotaan yang ditetapkan, dengan beberapa input yang ditanamkan pada kunci yang Anda cari dan sisanya mewakili nilai output, dan menyebutnya sebagai pencarian basis data. Tapi Anda bisa melakukan hal yang sama dengan solver SAT klasik dan tidak ada yang memanggil mereka algoritma pencarian basis data setahu saya. Dan untuk Grover (atau pemecah SAT klasik) untuk dapat bersaing dalam masalah jenis ini, "database" harus secara mendasar tidak dapat dijelaskan, yang berarti terlalu besar untuk diindeks, yang berarti tidak benar-benar disimpan di mana pun, yang membuatnya menurut saya bukan database (dan bukan data).

Menemukan sirkuit yang efisien menerapkan fungsi yang diberikan adalah masalah penting dan menarik, tetapi juga sangat luas; itu termasuk banyak dari apa yang disebut ilmu komputer. Saya tidak melihat apa yang bisa dikatakan tentang hal itu dalam konteks algoritma Grover yang tidak akan berlaku sama dalam konteks lainnya. Algoritma Grover hanya mengambil sirkuit yang dioptimalkan setelah Anda menemukannya dan mengevaluasinya sekitar timesN kali. Sirkuit memang perlu dibalik, membuatnya agak berbeda dari sirkuit klasik yang biasa, tetapi itu masih tidak terkait langsung dengan Grover.

Singkatnya, saya berpikir bahwa orang-orang tidak berbicara tentang menemukan sirkuit oracle karena sebenarnya tidak terkait dengan algoritma kuantum (terlepas dari judul makalah Grover) dan karena itu adalah topik yang begitu kompleks dan luas sehingga tidak ada perawatan yang bisa melakukannya dengan adil. .

benrg
sumber

Algoritma Grover untuk pencarian basis data: di mana keuntungan kuantum?

Jawaban: