Konsekuensi dari ?

20

Sementara teorema Adleman menunjukkan, bahwa , saya tidak mengetahui adanya literatur yang menyelidiki kemungkinan dimasukkannya . Apa konsekuensi kompleksitas-teoretis yang akan dimiliki oleh inklusi seperti itu?BPPP/polyBQPP/poly

Teorema Adleman kadang - kadang disebut "nenek moyang argumen derandomisasi." diyakini derandomizable, sedangkan tidak ada bukti bahwa "kuantumness" entah bagaimana dapat dihapus. Apakah ini bukti yang mungkin bahwa tidak mungkin berada di ?BPPBQPBQPP/poly

Martin Schwarz
sumber

Jawaban:

14

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.

Scott Aaronson
sumber
2
Terima kasih banyak telah menjawab, Scott! Satu hal yang saya bertanya-tanya: apa hasil yang diketahui terkait P ^ # P dengan tingkat PH / poli? Apa yang sebenarnya diketahui tentang P ^ # P vs PH / poli? (mis. apakah ada versi teorema Toda yang tidak seragam?). Mengapa P ^ # P dalam PH / poly collapse PH / poly, jika kita tidak tahu PH / poli di P ^ # P? Atau apa yang saya lewatkan?
Martin Schwarz
1
Yang perlu dilakukan di sini adalah menggeneralisasi bukti Teorema Karp-Lipton. Sebagai langkah pertama, tidak sulit untuk menunjukkan (menggunakan alasan KL-style) bahwa jika coNP dalam NP / poli, maka PH runtuh ke level ke-3. Tapi kemudian itu harus relativize, untuk menunjukkan bahwa jika coNP ^ NP ^ NP dalam NP ^ NP ^ NP / poly, maka PH runtuh ke level 5. Dan tentu saja P ^ # P dalam BPP ^ NP / poly menyiratkan coNP ^ NP ^ NP dalam NP ^ NP ^ NP / poly. Tapi hmm, aku hanya jatuh ke level 5 di sini! Dengan asumsi ini benar, adakah yang bisa memperbaikinya menjadi keruntuhan tingkat 4? (Jika tidak, ini adalah keruntuhan PH "tertinggi" yang pernah saya lihat! :))
Scott Aaronson
1
Tingkat 3 akan dilakukan. Baik dan Karp-Lipton relativize, jadi pertama B P P N P / p o l y = P N P / p o l y , dan kedua, jika Σ P 2( B P ) P N P / p o l y , lalu Σ P 3 = Π PBPPP/polyBPPNP/halHaily=PNP/halHailyΣ2P(BP)PNP/halHaily . Σ3P=Π3P
Emil Jeřábek mendukung Monica
1
(Dan berbagai strengthenings dikenal dari KL juga merelatifkan hal, khususnya asumsi di atas benar-benar runtuh PH untuk , kecuali saya belum pernah melihat S P dengan subskrip selain 2, sehingga kemungkinan notasi tidak standar.)S3PZPPNPNPΣ3PΠ3PSP
Emil Jeřábek mendukung Monica