Kompleksitas pengambilan sampel (kira-kira) transformasi Fourier dari fungsi Boolean

Satu hal yang dapat dilakukan oleh komputer kuantum (mungkin bahkan hanya dengan sirkuit kuantum log-depth BPP +) adalah untuk memperkirakan-sampel transformasi Fourier dari fungsi Boolean -nilai dalam P.$\pm 1$

Di sini dan di bawah ini ketika saya berbicara tentang pengambilan sampel transformasi Fourier yang saya maksud memilih x menurut . (Dinormalisasi jika perlu dan kurang-lebih).$|\hat f(x)|^2$

Bisakah kita menggambarkan kelas kompleksitas, yang bisa kita sebut P-FOURIER SAMPLING, dari perkiraan fungsi sampling Boolean P? Apakah ada masalah yang lengkap untuk kelas ini?

Diberikan kelas X fungsi Boolean apa yang dapat dikatakan tentang kompleksitas komputasi, yang dapat kita sebut sebagai SAMPLING-X dari pendekatan pengambilan sampel transformasi Fourier fungsi di X. (Saya menduga bahwa jika X adalah BQP maka X-SAMPLING adalah masih dalam kekuatan komputer kuantum.)

Apa saja contoh X di mana SAMPLING-X berada di P? Apakah ada contoh menarik di mana SAMPLING-X NP-hard?

Ada beberapa varian masalah ini yang juga bisa menarik. Di sisi Fourier, daripada sampel perkiraan kita dapat berbicara tentang masalah keputusan yang diaktifkan (secara probabilistik) dengan perkiraan sampling. Di sisi utama, kita dapat mulai dengan kelas X dari distribusi probabilitas dan bertanya apa hubungan antara kemampuan untuk kira-kira sampel distribusi D dalam X dan kira-kira sampel transformasi Fourier (dinormalisasi).

Singkatnya, apa yang diketahui tentang pertanyaan ini.

Pembaruan: Martin Schwarz menunjukkan bahwa jika semua koefisien Fourier sendiri terkonsentrasi hanya pada jumlah entri polinom maka mungkin di BPP untuk memperkirakan koefisien besar ini (dan dengan demikian juga untuk sekitar sampel.) Ini kembali ke Goldreich-Levin, dan Kushilevitz-Mansour. Apakah ada kelas fungsi yang menarik di mana ada algoritma polinomial probabilistik untuk kira-kira pengambilan sampel sisi Fourier, di mana koefisien Fourier tersebar di lebih dari banyak koefisien secara polinomi?

Ditambahkan Kemudian: Izinkan saya menyebutkan beberapa masalah nyata.

1) Seberapa sulit kira-kira sampel transformasi Fourier dari fungsi Boolean di P.

a) Satu pertanyaan yang disebutkan Scott Aaronson dalam komentar di bawah ini adalah untuk menunjukkan bahwa ini tidak ada dalam BPP. Atau sesuatu yang lebih lemah di sepanjang garis bahwa jika tugas ini di BPP beberapa keruntuhan terjadi. (Scot menduga bahwa ini masalahnya.)

b) Pertanyaan lain adalah untuk menunjukkan bahwa tugas ini sulit sehubungan dengan beberapa kelas kompleksitas berbasis kuantum. Misalnya, untuk menunjukkan bahwa jika Anda dapat melakukan tugas ini, Anda dapat menyelesaikan masalah keputusan di BPP yang dibantu dengan komputer kuantum log-depth, atau sesuatu seperti itu.

2) Apa kelas fungsi Boolean sehingga kira-kira pengambilan sampel transformasi Fourler mereka adalah dalam P. Apa yang kita ketahui adalah bahwa ini adalah kasus ketika koefisien Fourier terkonsentrasi pada banyak koefisien polinomial, tetapi ini tampaknya sangat terbatas.

3) Apakah ada beberapa kerumitan kelas X tinggi di PH bahwa mesin-X dapat kira-kira sampel transformasi Fourier dari setiap fungsi yang dapat dihitung mesin-X.

4) Saya sangat tertarik pada masalah pengambilan sampel transformasi Fourier dari peristiwa persimpangan untuk perkolasi pada n oleh n kisi heksagonal.

The Kushilevitz-Mansour algoritma belajar Menetapkan teori, bahwa setiap kali f ( x )$\hat{f}(x)$$O(poly(n))$$\Omega(1/poly(n))$$\sf{BPP}$$\mathbb{Z}_2$

$\Omega(2^{n/2})$