Pemisahan BQP dan PH

Question

Saya membaca artikel Quanta di sini yang menunjukkan bahwa ada masalah yang mencapai "pemisahan oracle antara BQP dan PH". Secara sederhana, ada masalah yang dapat diselesaikan oleh komputer kuantum dengan panggilan ke oracle yang jauh lebih sedikit daripada yang bisa dilakukan komputer klasik (bahkan di ranah di mana P = NP).

Mengapa ini merupakan hasil yang lebih kuat daripada algoritma Deutsch-Jozsa yang terkenal untuk menentukan apakah suatu fungsi konstan atau seimbang? Dalam hal itu juga, komputer klasik harus dibuat$O(n)$panggilan ke oracle (fungsi) sementara komputer kuantum dapat melakukannya dengan satu kueri. Apakah ini tidak membuktikan bahwa komputer kuantum berbeda dari komputer klasik manapun, bahkan jika P = NP?

Answer 1

Masalah Deutsch-Josza memberikan pemisahan oracle antara $\mathsf{EQP}$ (waktu kuantum-polinomial tepat) dan $\mathsf{P}$, tetapi tidak ada larangan untuk menambahkan pengacakan untuk mendapatkan algoritme klasik yang efisien.

Misalnya, masalah Deutsch-Josza masuk akal $\mathsf{BPP}$. Seseorang bisa saja melakukan sedikit panggilan ke oracle; jika Anda pernah melihat dua keluaran yang berbeda Anda tahu oracle seimbang, tetapi jika Anda selalu melihat hasil yang sama maka Anda dapat menyimpulkan bahwa oracle konstan dengan probabilitas tinggi.

Lebih lanjut ada dugaan derandomisasi yang masuk akal $\mathsf{BPP}$ adalah sama dengan $\mathsf{P}$. Jadi, masalah Deutsch-Josza masuk$\mathsf{P}$, modulo seperti dugaan derandomization.

Namun, "masalah hubungan" yang dipertimbangkan dalam makalah Raz-Tal dan dibahas dalam artikel Quanta memberikan pemisahan oracle antara $\mathsf{BQP}$ dan $\mathsf{PH}$. Masalah hubungan ini tidak mungkin di$\mathsf{BPP}$.

Misalnya, Anda tidak dapat, dengan probabilitas tinggi, menjalankan oracle Anda dengan komputer klasik dalam waktu polinomial, lalu menggunakan sesuatu yang mirip dengan ikatan Chernoff pada output untuk menentukan apakah distribusi yang diberikan adalah distribusi seragam atau distribusi forrelasi.