Bagaimana Grover-Algorithm diterapkan pada basis data?

Pertanyaan

Saya ingin menggunakan Grover-Algorithm untuk mencari basis data yang tidak disortir untuk elemen . Sekarang muncul pertanyaan, bagaimana cara menginisialisasi indeks dan nilai database dengan qubit?$x$

Contoh

• Katakanlah saya punya qubit. Dengan demikian, nilai klasik dapat dipetakan.$4$$2 ^ 4 = 16$
• Saya disortir database yang memiliki unsur-unsur berikut: .$d$$d [\text{Value}] = [3,2,0,1]$
• Saya ingin mencari .$x = 2_d = 10_b = |10\rangle$
• Pendekatan saya: indeks database dengan . Register dan untuk indeks dan register dan untuk nilainya. Kemudian terapkan Algoritma Grover hanya untuk register dan . Bisakah ini diwujudkan? Apakah ada pendekatan lain?$d$$d [(\text{Index, Value})] = [(0,3), (1,2), (2,0), (3,1)]$$0$$1$$2$$3$$2$$3 (\text{Value})$

Apa yang sudah saya terapkan ( di GitHub )

"Grover-Algorithm with 2-, 3-, 4-Qubits", tetapi yang dilakukannya sederhana: bit diinisialisasi dengan , oracle akan menandai solusi saya (yang hanya berupa angka seperti ), bagian Grover akan meningkatkan probabilitas elemen yang dipilih dan mengurangi semua probabilitas lainnya dan kemudian qubit dibaca dengan dipetakan ke bit klasik. Kami membiarkan proses ini berjalan beberapa kali berturut-turut dan dengan demikian memperoleh distribusi probabilitas, di mana probabilitas tertinggi memiliki elemen yang kami cari .$|0\rangle$$x$$2_d = 10_b$$x$$x$

Outputnya selalu sama dengan yang ditandai di oracle. Bagaimana saya dapat menghasilkan lebih banyak informasi dari output, yang saya tidak tahu pada saat saya membangun oracle?

Saya telah mengerjakan masalah ini juga. Sebagai seorang pemula dan seorang programmer klasik (yaitu, saya tidak berbicara Quantum Mechanics), sulit untuk memahami konsep-konsep tanpa contoh lengkap. Saya telah bekerja dengan sampel Pencarian Microsoft Q # Database . Itu hanya mencari indeks / kunci tertentu dalam database, yang tidak terlalu berguna. Saya telah memperluas sampel itu untuk mencari daftar nilai dalam database dan mengembalikan kunci yang sesuai.

Seperti contoh Anda, ada satu "register kunci" dua-qubit untuk indeks, dan register dua-qubit terpisah untuk nilai-nilai. Ada juga "qubit bertanda" kelima yang berasal dari sampel Microsoft, untuk menunjukkan kapan nilai yang diinginkan ditemukan. Kunci dan nilai dikaitkan melalui keterjeratan. Itu terbaik ditunjukkan dengan sirkuit. Klik di sini untuk melihat sirkuit Quirk yang sebenarnya .

Perhatikan bahwa sirkuit ini hanya berisi oracle. Itu tidak menerapkan semua algoritma Grover.

• Dua qubit teratas adalah register kunci, dua berikutnya adalah register nilai, dan qubit bawah adalah qubit yang ditandai.
• Bagian pertama menempatkan register kunci dalam superposisi seragam menggunakan gerbang Haramard, seperti yang dipersyaratkan oleh algoritma Grover.
• Bagian kedua adalah di mana kunci terkait dengan nilai-nilai melalui keterjeratan. Setiap kunci terjerat dengan nilai yang sesuai dalam daftar nilai dengan menerapkan (Anti-) gerbang X Terkendali. Jadi, ketika register kunci adalah 0, maka register nilai akan diatur ke 3. Ketika kuncinya adalah 1, nilai diatur ke 2, dan seterusnya.
• Bagian ketiga dari sirkuit adalah pencarian oracle. Register nilai terjerat dengan qubit yang ditandai. Dalam contoh ini, nilai yang diinginkan adalah 2. Ketika daftar nilai berisi 2, qubit yang ditandai akan ditetapkan ke 1.
• Algoritma Grover melihat register kunci dan menandai qubit. Oracle pencarian melihat pada register nilai dan mengatur qubit yang ditandai. Ini akan menyebabkan kunci 1 diperkuat ketika nilainya 2.

Sangat menarik untuk dicatat bahwa kunci dan nilai tidak disimpan di qubit, tetapi di sirkuit / program. Anda bisa mengatakan itu bukan database sebenarnya. Ini lebih seperti pernyataan switch / case, tetapi yang bisa berjalan pada superposisi nilai.

Untuk detail lebih lanjut, peringatan, dan kode Q #, lihat repositori GitHub saya .

EDIT: Sesuatu yang saya mengerti lebih baik sejak menjawab ... Anda harus membalik / membatalkan rangkaian sebagai bagian dari setiap iterasi. Dalam kode Q #, panggilan Adjoint StatePreparationOracle () di dalam operasi ReflectStart () menangani ini, jadi saya tidak perlu melakukannya secara eksplisit. Saya tidak tahu apakah Qiskit memiliki fitur serupa. Jika saya sudah melakukan terjemahan dengan benar, berikut adalah rangkaian lengkap untuk contoh di atas.

Ketika menyajikan algoritme Grover sebagaimana diterapkan untuk mencari dalam database, seharusnya Oracle memiliki akses ke elemen daftar klasik. Namun itu adalah asumsi yang sangat kuat dan inilah mengapa kami menyatakan bahwa dengan pemilih-terkontrol menggunakan CNOT / Toffolis dari indeks yang hanya mewakili operasi ini (seperti sirkuit Toffoli dalam kasus ).$n=4$

Anda menyebutkan pendekatan penghitungan nilai dalam register lain: Anda mengasumsikan lagi Anda diberi oracle untuk melakukannya dan efisien (cara langsung adalah mengontrol-BUKAN tetapi Anda harus melakukan ini untuk setiap indeks / nilai sehingga tidak sangat efisien). Dalam hal ini, oracle akan menjadi fungsi dalam format sirkuit kuantum (lagi selektor terkontrol), menandai keadaan ini dan melanjutkan dengan iterasi Grover.

Saya pikir lebih baik untuk memikirkan algoritma pencarian kuantum sebagai mengoptimalkan fungsi, daripada mencari dalam daftar / database. Berikut ini adalah artikel yang saya kerjakan di mana pencarian kuantum digunakan untuk memecahkan masalah maksimalisasi kombinatorial jika Anda ingin melanjutkan pemahaman Anda tentang algoritma.

Anda perlu mengonversi oracle untuk memegang database juga, sebagai hasilnya, Oracle umum (Phase Inversion) akan memiliki dua sub-oracle untuk melihat gambarnya.

Sub-oracle pertama yang harus dipersiapkan adalah sirkuit memori, berbeda dengan QRAM yang menyimpan data kuantum (keadaan) di dalam tubuhnya, sirkuit memori (array) ini disiapkan untuk hanya menyimpan informasi klasik dalam bingkainya. Contoh jenis sirkuit yang menyimpan array binari [010, 110, 100, 011] ditampilkan di bawah ini: Untuk lebih banyak membaca makalah ini .