vs

Masalah utama dari teori kompleksitas ini bisa dibilang vs N P .$P$$NP$

Namun, karena Alam adalah kuantum, akan terlihat lebih alami untuk mempertimbangkan kelas (masalah yaitu keputusan dipecahkan oleh sebuah komputer kuantum dalam waktu polinomial, dengan probabilitas kesalahan paling 1/3 untuk semua kasus) ans Q M A (setara kuantum dari N P ) sebagai gantinya.$BQP$$QMA$$NP$

Pertanyaan saya:

1) Apakah solusi untuk masalah vs N P memberikan solusi untuk B Q P vs Q M A ?$P$$NP$$BQP$$QMA$

2) Apakah tiga hambatan perelatifan, bukti alam dan algebrization juga berlaku untuk vs Q M A masalah?$BQP$$QMA$

1) Tidak ada implikasi yang diketahui di kedua arah. Kita tahu bahwa P = NP menyiratkan P = PH. Tapi kita tidak tahu apakah BQP dan QMA berada di PH, jadi mungkin P bisa menyamai NP namun BQP dan QMA masih tidak akan runtuh. (Di sisi lain, perhatikan bahwa QMA⊆PP⊆P ^#P , jadi tentu saja P = P ^#P akan menyiratkan BQP = QMA.) Untuk menunjukkan bahwa BQP = QMA menyiratkan P = NP tampaknya bahkan lebih tanpa harapan dalam keadaan pengetahuan saat ini .

2) Tentu saja, ketiga hambatan berlaku dengan kekuatan penuh untuk BQP vs QMA (dan bahkan untuk masalah "lebih mudah" dalam membuktikan P ≠ PSPACE). Pertama, relatif terhadap oracle PSPACE (atau bahkan ekstensi tingkat rendah dari oracle PSPACE), kami miliki

P = NP = BQP = QMA = PSPACE,

jadi tentu saja teknik nonrelativizing dan non-algebrizing akan diperlukan untuk memisahkan kelas-kelas ini. Kedua, untuk mendapatkan penghalang bukti alami untuk meletakkan barang-barang di luar BQP, yang Anda butuhkan adalah keluarga fungsi pseudorandom yang dapat dihitung dalam BQP, yang merupakan persyaratan yang secara formal lebih lemah daripada keluarga fungsi pseudorandom yang dapat dikomputasi dalam P.

Tambahan: Biarkan saya mengatakan sesuatu tentang "metaquestion" yang tidak Anda tanyakan tetapi mengisyaratkan, tentang mengapa orang masih fokus pada P vs NP meskipun kami percaya Alam adalah kuantum. Secara pribadi, saya selalu melihat P vs NP sebagai tidak lebih dari "unggulan" untuk sejumlah besar pertanyaan penghalang dalam teori kompleksitas (P vs PSPACE, P vs BQP, NP vs coNP, NP vs BQP, keberadaan fungsi satu arah, dll), tidak adayang kami tahu bagaimana menjawabnya, dan semuanya terkait dalam arti bahwa setiap terobosan dengan satu kemungkinan besar akan mengarah pada terobosan dengan yang lain (bahkan di mana kami tidak memiliki implikasi formal antara pertanyaan, yang dalam banyak kasus kami melakukan). P vs NP secara inheren tidak lebih mendasar daripada yang lain - tetapi jika kita harus memilih satu pertanyaan untuk dijadikan sebagai anak poster untuk kompleksitas, maka itu adalah pilihan yang baik.