Algoritma Grover: apa yang harus diinput ke Oracle?

Saya bingung tentang apa yang harus dimasukkan ke Oracle dalam algoritma Grover.

Tidakkah kita perlu memasukkan apa yang kita cari dan di mana menemukan apa yang kita cari untuk Oracle, selain status kuantum superposisi?

Misalnya, anggap kita memiliki daftar nama orang {"Alice", "Bob", "Corey", "Dio"}, dan kami ingin mengetahui apakah "Dio" ada di daftar. Kemudian, Oracle harus mengambil sebagai input dan output . Saya agak mengerti itu. $1/2(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$

Tapi bukankah kita juga perlu memasukkan kata "Dio" dan daftar {"Alice", "Bob", "Corey", "Dio"} ke Oracle? Jika tidak, bagaimana Oracle dapat mengembalikan output? Apakah itu tidak disebutkan secara eksplisit karena Oracle adalah kotak hitam dan kita tidak perlu memikirkan cara mengimplementasikannya?

Pemahaman saya tentang Oracle adalah,

Oracle memiliki kemampuan untuk mengenali jika kata "Dio" ada dalam daftar.
Untuk melakukannya, Oracle mengambil status kuantum superposisi sebagai input, di mana setiap status kuantum mewakili indeks daftar.
Jadi, masukan ke Oracle berarti, cek jika kata "Dio" adalah dalam indeks 0 dari daftar dan kembali jika ya dan kembali sebaliknya. $|00\rangle$ $-|00\rangle$ $|00\rangle$
$1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$
Tetapi bagaimana dengan daftar dan kata itu?

algorithm grovers-algorithm oracles Bick
sumber

Meskipun tidak diutarakan dengan cara yang sama, saya yakin pertanyaan Anda kurang lebih sama dengan yang ini: Algoritma Grover: di mana daftarnya?

DaftWullie

Jawaban:

$O(\sqrt{N} \cdot F)$ $N$ $F$

$N$ $F$ $O(N)$ $O(\sqrt{N} \cdot F) = O(\sqrt{N} \cdot N) = O(N^{1.5})$ $N^{1.5} > N$

Craig Gidney
sumber

O (\sqrt{N} \log (N))

$O(\sqrt{N}\log(N))$

@DaftWullie Masalahnya adalah bahwa Grover harus melakukan pencarian di bawah superposisi, dan ini membutuhkan sirkuit multiplexer dengan gerbang N AND (atau operasi non-Clifford lainnya). Gerbang kuantum DAN (yaitu Toffoli) memiliki biaya yang tidak dapat diabaikan ketika melakukan koreksi kesalahan. Biaya ini secara teknis juga ada dalam mesin klasik (yaitu RAM memiliki gerbang O (N) DAN), kebetulan saja diabaikan dan bahkan dapat dihindari dalam konteks itu.

Craig Gidney

Saya tidak mengerti apa yang Anda katakan. Apakah Anda dapat mengungkapkan pertanyaan, dan menjawabnya, untuk menunjukkan detailnya? (Saya rasa saya tidak bisa mengutarakan pertanyaan yang cukup bagus saat ini)

DaftWullie

@ DavidWullie Saya pikir pertanyaannya akan menjadi sesuatu seperti "bagaimana saya memberikan akses baca komputer kuantum ke database klasik dan seberapa mahal itu".

Craig Gidney