Konstruksi Oracle untuk Algoritma Grover

Dalam "Quantum Computation and Quantum Information" Mike dan Ike, algoritma Grover dijelaskan dengan sangat terperinci. Namun, dalam buku ini, dan dalam semua penjelasan yang saya temukan online untuk algoritma Grover, tampaknya tidak disebutkan tentang bagaimana Oracle dibangun, kecuali kita sudah tahu negara bagian mana yang sedang kita cari, mengalahkan tujuan dari Grover. algoritma. Secara khusus, pertanyaan saya adalah ini: diberikan beberapa f (x) sedemikian rupa sehingga untuk beberapa nilai x, f (x) = 1, tetapi untuk semua yang lain, f (x) = 0, bagaimana seseorang membangun oracle yang akan membawa kita dari awal, keadaan arbitrer | x> | y> ke | x> | y + f (x)> kami? Detail eksplisit sebanyak mungkin (mungkin contoh?) Akan sangat dihargai. Jika konstruksi untuk fungsi sewenang-wenang semacam itu dimungkinkan dengan Hadamard, Pauli, atau gerbang kuantum standar lainnya,

quantum-computing quantum-information oracles search-problem black-box Akan
sumber

"Di sini sepertinya tidak disebutkan bagaimana Grover's Oracle dibangun, kecuali kita sudah tahu negara mana yang sedang kita cari, mengalahkan tujuan algoritma." ... "Grover's Oracle" adalah masalah yang harus dipecahkan. Anda tidak membangunnya. Anda diberikan (akses oracle) dan diminta melakukan perhitungan untuk mengungkap nilai. Jika itu membantu, berpura-pura bahwa saya membangun oracle, dan kemudian meminta Anda untuk menyelesaikan masalah. (Juga, perhatikan bahwa membaca / menulis / menyiapkan database item membutuhkan waktu lebih lama daripada menjalankan algoritme waktu Grover .)

N

$N$

\sqrt{N}

$\sqrt{N}$

Daniel Apon

Tetapi bagaimana jika alih-alih diberi oracle, kita diberi beberapa f (x)? Bayangkan kita sedang memecahkan masalah 3-SAT dan ingin menggunakan Grover untuk memberikan solusi cepat. Kita tahu f (x) dalam pertanyaan (klausa kebenaran 3-SAT), tetapi tidak perlu tahu bit string x mana yang akan menghasilkan hasil yang benar ketika dicolokkan ke 3-SAT. Tidakkah harus ada cara untuk membangun oracle dari fungsi 3-SAT untuk menemukan string bit yang benar? Jika tidak ada, dan seperti yang Anda sarankan, sesuatu disediakan oleh orang lain, algoritme Grover tampaknya agak buatan, hanya latihan yang diberikan kepada Anda.

Will

Jawaban:

Peramalan ini pada dasarnya hanyalah implementasi dari predikat yang Anda inginkan untuk mencari solusi yang memuaskan.

Misalnya, misalkan Anda memiliki masalah 3-sat:

(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)

Atau, dalam bentuk tabel dengan setiap baris menjadi 3-klausa, x berarti "variabel ini salah", o berarti "variabel ini benar", dan ruang yang berarti "tidak dalam klausa":

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Sekarang buat sirkuit yang menghitung apakah input adalah solusi, seperti ini:

Sekarang, untuk mengubah sirkuit Anda menjadi oracle, tekan bit output dengan gerbang Z dan hitung sampah yang Anda buat (mis. Jalankan sirkuit komputasi dalam urutan terbalik):

Hanya itu yang ada untuk itu. Hitung predikatnya, tekan hasilnya dengan Z, hitung predikatnya. Itu oracle.

Ulangi langkah-langkah difusi dengan langkah-langkah oracle, dan Anda sendiri sudah mencari :

... walaupun Anda mungkin harus memilih contoh dengan lebih sedikit solusi, jadi progresnya bertahap (alih-alih berputar di sepanjang bidang start-state-solution-state lebih dari 90 derajat per langkah seperti contoh saya).

Craig Gidney
sumber

Terima kasih, ini sangat membantu. Sangat jelas, menjawab semua yang saya tanyakan (dan bahkan menggunakan gerbang kuantum umum!) Apakah ada alasan Anda memutuskan untuk mengubah semua qubit awal Anda ke status | 1> sebelum menempatkannya di superposisi dengan gerbang Hadamard alih-alih hanya menempatkan | 0 > nyatakan qubit melalui Hadamard (yaitu apakah ada keuntungan untuk ini)? Juga, operasi apa itu untuk langkah difusi Anda? Sepertinya dikontrol X, tetapi apakah Anda menggunakan | 1> atau | 0> sebagai kontrol?

Will

@ Akankah saya menggunakan status awal yang berbeda. Anda dapat melakukannya selama Anda juga mengubah status yang dinegasikan oleh operator difusi (mereka harus cocok). Semua keadaan awal / difusi yang memiliki jarak sudut yang sama untuk setiap keadaan dasar komputasi bekerja dengan baik. Kontrol lingkaran-plus kecil dalam diagram saya adalah "kontrol sumbu-X", yang setara dengan kontrol normal yang dikelilingi oleh gerbang Hadamard. Sepertinya TIDAK karena mereka bisa saling dipertukarkan . Status permulaan / difusi saya adalah .

(\frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩)^{\otimes n}

$(\frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} |1\rangle)^{\otimes n}$

Craig Gidney

Jawaban yang fantastis, dan terima kasih atas tautannya ke algassert.com/quirk !

Frédéric Grosshans