Membatasi kesenjangan antara kuantum dan kompleksitas kueri deterministik

Meskipun pemisahan eksponensial antara kompleksitas kueri-kuantum kesalahan terbatas ( $Q(f)$ ) dan kompleksitas kueri deterministik ( $D(f)$ ) atau kompleksitas kueri acak terbatas ( $R(f)$ ) diketahui, mereka hanya berlaku untuk fungsi parsial tertentu. Jika fungsi parsial memiliki beberapa struktur khusus maka mereka juga terkait secara polinomi dengan $D(f) = O(Q(f)^9))$ . Namun, saya lebih mementingkan fungsi total.

Dalam kertas klasik ditunjukkan bahwa $D(f)$ dibatasi oleh $O(Q(f)^6)$ untuk fungsi total, $O(Q(f)^4)$ untuk fungsi total monoton, dan $O(Q(f)^2)$ untuk fungsi total simetris. Namun, tidak ada yang lebih besar dari pemisahan kuadrat dikenal untuk semacam ini fungsi (pemisahan ini dicapai dengan $OR$sebagai contoh). Sejauh yang saya mengerti, kebanyakan orang mengira bahwa untuk fungsi total kita memiliki $D(f) = O(Q(f)^2)$ . Dalam kondisi apa dugaan ini telah terbukti (terlepas dari fungsi simetris)? Apa batasan terbaik saat ini pada kompleksitas pohon keputusan dalam hal kompleksitas kueri kuantum untuk fungsi total?

Sejauh yang saya tahu, batas umum yang Anda sebutkan pada dasarnya adalah yang paling dikenal. Mengubah model sedikit, Midrijanis telah menunjukkan batas bahwa , di mana Q E ( f ) adalah kompleksitas kueri kuantum yang tepat dari f ; ada juga batas yang lebih ketat yang dikenal dalam hal kesalahan satu sisi (lihat Bagian 6 makalah ini ).$D(f) = O(Q_E(f))^3$$Q_E(f)$$f$

Dalam hal yang lebih spesifik, tetapi masih umum, kelas fungsi, ada kertas dari Barnum dan Saks yang menunjukkan bahwa semua fungsi baca-sekali pada variabel memiliki kompleksitas kuerium kuantum Ω ( $n$.$\Omega(\sqrt{n})$

Meskipun kemajuan ini terbatas, ada kemajuan besar dalam batas bawah kompleksitas kueri kuantum fungsi - fungsi tertentu ; lihat ulasan ini untuk perincian (atau misalnya makalah Reichardt yang lebih baru , yang membuktikan bahwa versi paling umum dari batasan '' musuh '' mencirikan kompleksitas kueri kuantum).

Saya suka jawaban Ashley Montanaro, tapi saya pikir saya juga akan memasukkan satu set fungsi yang diketahui dugaannya.

Serangkaian fungsi yang sering menarik adalah fungsi dengan 1-sertifikat berukuran konstan. Kelas ini masalah termasuk hal-hal seperti , keunikan, tabrakan, segitiga-temuan dan banyak masalah lain (tidak dalam HSP-keluarga) yang telah terbukti memiliki permintaan pemisahan kompleksitas.$OR$

Untuk konstan berukuran 1-sertifikat fungsi keseluruhan , kita memiliki D ( f ) = O ( Q ( f ) 2 ) .$f$$D(f) = O(Q(f)^2)$

Detail:

Sebuah sertifikat untuk input adalah bagian dari bit S ⊆ { 1 , . . . , n } sedemikian rupa sehingga untuk semua input y , ( ∀ i ∈ $x$$S \subseteq \{1,...,n\}$$y$$(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$$C_x(f)$$x$f ( x ) = $C_1(f) = \max_{x | f(x) = 1} C_x(f)$$f(x) = 0$

Anda dapat menunjukkan bahwa . Kemudian Anda dapat menggunakan algoritma yang disajikan dalam survei Buhrman and de Wolf untuk menunjukkan bahwa:D ( f ) ≤ C 1 ( f ) b s ( f ) ≤ C 0 ( f ) C 1 ( f $Q(f) \geq \sqrt{bs(f)} \geq 2C_0(f)/2^{C_1(f)} + 1$$D(f) \leq C_1(f)bs(f) \leq C_0(f)C_1(f)$

Jika kami membatasi perhatian pada properti grafik, maka kami dapat membuktikan batas yang sedikit lebih baik dibandingkan dengan batas umum yang Anda sebutkan:

Dalam sebuah makalah klasik ditunjukkan bahwa dibatasi oleh untuk fungsi total, untuk fungsi total monoton, dan untuk fungsi total simetris.O ( Q ( f ) 6 ) O ( Q ( f ) 4 ) O ( Q ( f ) 2$D(f)$$O(Q(f)^6)$$O(Q(f)^4)$$O(Q(f)^2)$

Pertama saya pikir kekuatan ke-6 dapat ditingkatkan menjadi kekuatan ke-4 untuk properti grafik. Ini mengikuti dari [1], di mana mereka menunjukkan bahwa setiap properti grafik memiliki kompleksitas kueri paling tidak , di mana adalah ukuran input, yang kuadratik dalam jumlah simpul. Tentu saja kompleksitas permintaan klasik paling .N $\Omega(N^{1/4})$$N$$N$

Batas daya ke-4 untuk fungsi total monoton dapat ditingkatkan ke daya ke-3 untuk properti grafik monoton. Ini mengikuti dari pengamatan Yao dan Santha yang tidak dipublikasikan (disebutkan dalam [2]) bahwa semua properti grafik monoton memiliki kompleksitas kueri kuantum .$\Omega(N^{1/3}\log^{1/6}N)$

[1] Sun, X .; Yao, AC.; Shengyu Zhang, "Properti grafik dan fungsi sirkular: seberapa rendah kompleksitas kueri kuantum dapat berjalan ?," Computational Complexity, 2004. Prosiding. Konferensi Tahunan IEEE ke-19 pada, vol., No., Hal.286.293, 21-24 Juni 2004 doi: 10.1109 / CCC.2004.1313851

[2] Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2005), "Algoritma kuantum untuk masalah segitiga", Prosiding simposium tahunan ACM-SIAM keenambelas tentang algoritma Discrete, Vancouver, British Columbia: Masyarakat untuk Industri dan Matematika Terapan, hal. 1109-1117, arXiv: quant -ph / 0310134.

Banyak kemajuan telah dibuat pada pertanyaan ini pada tahun 2015.

Pertama, di arXiv: 1506.04719 [cs.CC] , penulis telah meningkatkan pemisahan kuadrat dengan menunjukkan fungsi total dengan$f$

Di sisi lain, di arXiv: 1512.04016 [quant-ph] , ditunjukkan bahwa hubungan kuadratik antara kompleksitas kuantum dan kueri deterministik berlaku ketika domain fungsi sangat kecil.