Pada optimalitas algoritma Grover dengan probabilitas keberhasilan tinggi

Diketahui bahwa kompleksitas query quantum error terbatas dari fungsi adalah Θ ( $OR(x_1,x_2,\ldots, x_n)$. Sekarang pertanyaannya adalah bagaimana jika kita ingin algoritma quantum kami berhasil untuk setiap input dengan probabilitas1-εdaripada biasa2/3. Sekarang dalam halϵapa yang akan menjadi batas atas dan bawah yang sesuai?$\Theta(\sqrt{n})$$1-\epsilon$$2/3$$\epsilon$

Segera bahwa kueri cukup untuk tugas ini dengan mengulangi algoritma Grover. Tetapi dari apa yang saya ingat ini sama sekali tidak optimal karena bahkan algoritma Grover biasa jika dijalankan dengan hati-hati, yaitu untuk jumlah iterasi yang sesuai, dapat mencapai sesuatu sepertiϵ=O(1/n)hanya denganO($O(\sqrt{n} \log(1/\epsilon))$$\epsilon=O(1/n)$iterasi. Dan karenanya menggunakan yang satu itu bisa mendapatkan perbaikan untuk semuaϵ. Di sisi lain, saya tidak mengharapkan ituΩ($O(\sqrt{n})$$\epsilon$menjadi jawaban yang tepat untuk sangat kecilε's.$\Omega(\sqrt{n})$$\epsilon$

Tapi saya tertarik untuk melihat apa yang bisa ditunjukkan oleh -dependent batas atas dan bawah untuk rentang yang berbeda ϵ terutama ketika ϵ sangat kecil katakan ϵ = exp ( - Ω ( n ) ) atau ϵ = 1 / n k untuk besar k .$\epsilon$$\epsilon$$\epsilon$$\epsilon= \exp(-\Omega(n))$$\epsilon=1/n^k$$k$

(Untuk memberikan beberapa konteks, fenomena umum yang saya maksudkan adalah amplifikasi dalam konteks kompleksitas kueri kuantum.)

Demi kelengkapan, inilah jawabannya.

$Q_\epsilon(f)$$\epsilon$$f$$\mathsf{OR}_n$$n$$\mathsf{OR}_n(x_1,\ldots,x_n)=\bigvee_{i=1}^n x_i$$\Theta(\sqrt{n})$

$\epsilon \in [2^{-n},1/3]$

$Q_\epsilon(\mathsf{OR}_n) = \Theta(\sqrt{n\log(1/\epsilon)})$

Ini mengikuti dari Batas untuk Algoritma Quantum Kesalahan Kecil dan Nol Kesalahan .

$f$$\epsilon \in [2^{-n},1/3]$

$Q_\epsilon(f) = \Theta(Q_{1/3}(f)+\sqrt{n\log(1/\epsilon)})$

Ini ditunjukkan dalam Catatan tentang algoritma kuantum dan tingkat minimal polinomial kesalahan epsilon untuk fungsi simetris .