Saya katakan kita tidak punya alasan kuat untuk berpikir BQP ada di P / poly. Kami memang memiliki alasan untuk berpikir bahwa BQP tidak dalam P / poli, tetapi mereka lebih atau kurang identik dengan alasan kami untuk berpikir bahwa BQP ≠ BPP. Misalnya, jika BQP⊂P / poli maka Anjak dalam P / poli, yang cukup untuk memecah banyak kriptografi sesuai dengan definisi keamanan standar.
Juga, seperti yang Anda tunjukkan dengan benar, tidak ada analog kuantum trik Adleman --- memang, tidak ada cara untuk "menarik kuantum keluar dari algoritma kuantum," analog dengan bagaimana seseorang dapat menarik keacakan dari algoritma acak. Jadi saya tidak berpikir ada yang punya dugaan untuk apa saran P / poly untuk mensimulasikan komputer kuantum bahkan harus terdiri dari (lebih dari yang mereka duga, katakanlah, dalam kasus NP vs P / poly).
Catatan terakhir: pekerjaan saya dengan Alex Arkhipov (dan karya independen Bremner-Jozsa-Shepherd), dapat dengan mudah disesuaikan untuk menunjukkan bahwa jika QUANTUM-SAMPLING dalam P / poli (OK, dalam "BPP-SAMPLING / poli") , lalu P #P ⊂BPP NP / poly, dan karenanya hierarki polinomial runtuh --- dalam hal ini, saya pikir, ke tingkat keempat . Namun, saat ini, kami tidak tahu bagaimana menyesuaikan hasil semacam ini dari masalah pengambilan sampel hingga masalah keputusan.