Menggunakan kekuatan ekstra dari metode musuh negatif

Metode musuh negatif ( $ADV^\pm$ ) adalah SDP yang mencirikan kompleksitas kueri kuantum. Ini adalah generalisasi dari metode permusuhan yang banyak digunakan ( $ADV$ ), dan mengatasi dua penghalang yang menghalangi metode permusuhan:

1. Hambatan pengujian properti: jika semua 0-instans adalah $\epsilon$ -far dari semua 1-instans maka metode musuh tidak dapat membuktikan batas bawah yang lebih baik daripada $\Omega(1/\epsilon)$ .

2. Kompleksitas sertifikat penghalang: jika adalah kompleksitas sertifikat b -instances maka metode musuh tidak dapat membuktikan batas bawah lebih baik dari $C_b(f)$$b$ mana$\sqrt{C_0(f)C_1(f)}$

Dalam kertas $ADV^\pm$ , penulis membuat contoh fungsi yang metode mereka mengatasi kedua hambatan. Namun, saya belum melihat contoh masalah alami di mana ini telah menghasilkan batas bawah baru.

Bisakah Anda memberikan referensi di mana metode musuh negatif digunakan untuk mencapai batas bawah yang tidak dapat dicapai metode asli?

Bunga terbesar bagi saya, adalah dalam pengujian properti. Saat ini ada sangat sedikit batas bawah pada pengujian properti, pada kenyataannya saya hanya tahu dua ( CFMdW2010 , ACL2011 ), yang keduanya menggunakan metode polinomial (yang pertama dengan reduksi dari masalah tabrakan yang semula lebih rendah dibatasi oleh metode polinomial). Kita tahu bahwa ada properti yang membutuhkan kueri kuantum untuk memeriksa, untuk setiap f ( n ) ∈ O ( n ) yang dapat dihitung (dengan menggabungkan hasil dalam BNFR2002 dan GKNR2009$\Theta(f(n))$$f(n) \in O(n)$). Mengapa begitu sulit untuk menggunakan metode musuh negatif untuk membuktikan batas bawah pada mereka?$\Omega(f(n))$

Rupanya, saya tidak bisa berkomentar jadi ini akan menjadi jawaban, walaupun itu hanya sebagian jawaban.

Elemen-keunikan telah menjadi batas bawah dari dan kompleksitas sertifikat adalah $\Omega(N^{2/3})$ , jadi jika seseorang mencoba membuktikannya menggunakan metode musuh, ia akan perlu menggunakan metode musuh dengan bobot negatif (yang optimal), atau mengapa tidak menggunakan metode musuh Multiplikatif.$\sqrt{N}$

Kalau tidak, metode polinomial kadang-kadang lebih mudah digunakan daripada metode musuh karena cukup untuk membuktikan keberadaan polinomial sedangkan untuk metode musuh, Anda perlu secara eksplisit memiliki matriks musuh yang baik, dan menghitung norma operatornya.