Apa kompleksitas membedakan spektrum Fourier sejati dari spektrum palsu?

Sebuah $PH$ mesin diberikan akses oracle ke acak Boolean fungsi $f:\{0,1\}^n \to \{ -1,1 \}$ , dan dua Fourier spektrum $g$ dan $h$ .

Spektrum Fourier dari fungsi $f$ didefinisikan sebagai $F:\{0,1\}^n \to R$ :

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

Salah satu dari atau h adalah spektrum Fourier sebenarnya dari f dan yang lainnya hanyalah spektrum Fourier palsu yang dimiliki oleh fungsi Boolean acak yang tidak diketahui.h $g$$h$$f$

Tidak sulit untuk menunjukkan bahwa mesin $PH$ , bahkan tidak dapat memperkirakan $F(s)$ untuk setiap $s$ .

Apa kompleksitas permintaan untuk memutuskan dengan probabilitas keberhasilan tinggi mana yang benar?

Sangat menarik bagi saya, karena jika masalah ini tidak di $PH$ , maka orang dapat menunjukkan bahwa ada oracle relatif yang $BQP$ di bukan subset dari $PH$ .

Maaf saya terlambat - ini pertanyaan yang bagus! Seperti yang telah ditunjukkan oleh orang lain, itulah tepatnya mengapa saya mengajukan pertanyaan dalam makalah BQP vs PH saya , dan mengapa saya menghabiskan 4 atau 5 bulan mengerjakannya tanpa berhasil di tahun 2008. Salah satu cara untuk menjawab pertanyaan adalah membuktikannya pernyataan yang jauh lebih umum yang saya sebut "Dugaan Linial-Nisan Umum" --- tetapi sayangnya, dugaan itu ternyata salah , setidaknya untuk sirkuit dengan kedalaman 3 dan lebih tinggi. (Saya masih berpikir itu mungkin benar untuk sirkuit kedalaman-2, yang setidaknya akan menghasilkan pemisahan oracle antara BQP dan AM.) Untuk ide-ide yang lebih baru (terbaru, sejauh yang saya tahu) menuju pemisahan oracle antara BQP dan PH, lihat karya lanjutan yang bagus dari Fefferman, Shaltiel, Umans,

Scott Aaronson mungkin orang terbaik di dunia untuk menjawab pertanyaan ini, mungkin dia akan memiliki jawaban yang lebih baik setelah ini diposting. ia mengusulkan masalah asli yang mana pertanyaan yang diposkan ini tampaknya merupakan varian yang sangat kecil, yang disebut masalah pemeriksaan Fourier (lebih banyak referensi tentang hal itu di komentar). masalah terkait erat / hampir setara dengan memisahkan dua kelas kompleksitas penting PH dan BQP yang merupakan masalah terbuka utama dari teori kompleksitas QM, dan mungkin sangat sulit. tidak tampak bahwa banyak penelitian langsung / lebih lanjut tentang hal itu telah dilakukan pada masalah sejauh ini oleh siapa pun selain Aaronson dan mungkin bahkan tidak dia (yang tampaknya hanya sedikit lebih dari 2 tahun).

namun di sini setidaknya ada satu makalah oleh orang lain selain Aaronson yang berfokus / membangun dugaan / masalah dengan beberapa hasil baru.

Speedup Eksponensial adalah Generik oleh Fernando GSL Brandão dan Michał Horodecki

Dalam makalah kami [4] kami menggeneralisasi masalah Fourier Memeriksa [1] dan menunjukkan bahwa transformasi Fourier, baik dalam definisi masalah dan dalam penyelesaian algoritma kuantum, dapat digantikan oleh kelas besar sirkuit kuantum. Ini termasuk transformasi Fourier atas setiap kelompok hingga (mungkin non-abelian) dan hampir semua sirkuit kuantum yang cukup panjang dari distribusi alami pada rangkaian sirkuit kuantum. Kami memperoleh pemisahan eksponensial dari kuantum dan kompleksitas kueri klasik terpilih untuk semua sirkuit tersebut.