Mengapa qubit oracle diperlukan dalam algoritma Grover?

10

Saya agak bingung tentang perlunya qubit oracle dalam algoritma Grover.

Pertanyaan saya adalah, apakah itu tergantung pada bagaimana Anda menerapkan oracle Anda apakah Anda memerlukan oracle qubit atau tidak? Atau, apakah ada alasan untuk qubit oracle? (seperti, ada beberapa masalah yang tidak dapat diselesaikan tanpa qubit oracle, atau lebih mudah untuk memikirkan masalah dengan qubit oracle, atau itu adalah konvensi, dll)

Banyak sumber memperkenalkan algoritma Grover dengan qubit oracle, tetapi saya menemukan ada beberapa kasus yang Anda tidak memerlukan oracle qubit.

Sebagai contoh, berikut adalah dua implementasi dari algoritma Grover di simulator Q IBM. Satu menggunakan oracle qubit, dan yang lainnya tidak. Dalam kedua kasus, saya ingin mencari | 11> dari spasi | 00>, | 01>, | 10>, dan | 11>. Dalam kedua kasus, oracle berhasil membalik | 11> ke - | 11>.

・ Dengan qubit oracle ( Tautan ke IBM Q simulator ) masukkan deskripsi gambar di sini

・ Tanpa qubit oracle ( Tautan ke IBM Q simulator ) masukkan deskripsi gambar di sini

algorithm grovers-algorithm Bick
sumber

Jawaban:

5

Dari perspektif mendefinisikan sirkuit kuantum, qubit oracle tidak sepenuhnya diperlukan. Misalnya, dalam pencarian Grover, Anda mungkin mendefinisikan aksi oracle sebagai mana mengembalikan 1 jika adalah item yang ditandai. Namun, kami selalu menggunakan ini dengan cara tertentu, memasukkan pada oracle qubit. Ini memiliki efek bersih hanya menerapkan fase pada item yang ditandai. Dengan kata lain, itu sepenuhnya setara dengan implementasi kesatuan baru f ( x ) x ( | 0 ⟩ - | 1 ⟩ ) / √

U|x⟩|y⟩=|x⟩|y⊕f(x)⟩,
f(x)x˜ U | x⟩=(-1) f ( x ) | x⟩(|0⟩−|1⟩)/2
U~|x⟩=(−1)f(x)|x⟩

Namun, di mana itu membuat perbedaan adalah kenyataan praktis. Mencari item, kita benar-benar membutuhkan semacam rangkaian yang mengenali item yang ditandai, berdasarkan pada input . Pada titik itu, jauh lebih mudah untuk berpikir tentang mengeluarkan jawaban ke bit oracle, daripada entah bagaimana langsung membangun kesatuan yang memberikan fase tanpa menggunakan qubit oracle. Memang, saya curiga jika saya meminta Anda untuk merancang versi generik , Anda akan menghasilkan dengan qubit tambahan sebagai solusinya.˜ U UxU~U

DaftWullie
sumber
Sebenarnya sangat mudah untuk menghindari qubit tambahan, dengan anggapan itu tidak digunakan sebagai ruang kerja selama perhitungan oracle. Temukan CNOT ke dalam qubit tambahan, dan ganti dengan gerbang Z ke kontrol CNOT. Demikian pula, ganti CCNOT ke qubit tambahan dengan CZ antara dua kontrol CCNOT. Dll
Craig Gidney
@CraigGidney Ini adalah poin yang adil, meskipun saya pikir ada lebih banyak asumsi yang dibangun dalam pernyataan Anda (menjadikannya non-generik, bahkan jika sebagian besar kasus yang kita ketahui memuaskan mereka): (1) seharusnya tidak ada ancillas perantara yang digunakan selama evaluasi fungsi; (2) sirkuit oracle harus didekomposisi menjadi satu set gerbang di mana satu-satunya gerbang multi-qubit yang bekerja pada qubit oracly adalah (multi) -controlled-nots yang menargetkan qubit oracle; (3) tidak ada gerbang lain yang dapat bertindak pada qubit oracle (yaitu Anda tidak bisa membalikkan c-not yang bertindak dengan cara yang salah dengan menggunakan Hadamard pada input dan output).
DaftWullie
Itu betul.
Craig Gidney