Akankah masalah P vs NP menjadi sepele sebagai akibat dari pengembangan komputer kuantum universal?

Jika seseorang membangun komputer kuantum universal, akankah hal itu berimplikasi pada masalah P vs NP?

Tidak, sama sekali tidak ada implikasi, karena beberapa alasan:

1. Masalah P vs NP adalah tentang perhitungan klasik daripada perhitungan kuantum. Bahkan jika komputer kuantum dapat memecahkan masalah NP-hard dalam waktu polinomial (yang kami tidak harapkan mereka dapat lakukan), itu masih bisa menjadi kasus bahwa komputer klasik tidak dapat menyelesaikannya dalam waktu polinomial.

2. Komputer kuantum universal, dalam pengertian teoretis, sudah (setahu saya) sudah diketahui keberadaannya. Ini hanyalah analog kuantum dari mesin Turing universal: mereka dapat menjalankan "program" kuantum apa pun.

3. Baik komputasi kuantum dan masalah P vs NP adalah gagasan teoretis. Apa yang dapat dikonstruksikan seseorang di dunia fisik sama sekali tidak ada hubungannya dengan apa pun yang berkaitan dengan mereka.

Lieuwe Vinkhuijzen memberikan interpretasi berbeda untuk pertanyaan Anda:

Apakah komputer kuantum dapat menyelesaikan masalah NP-complete secara efisien?

Jawaban yang diharapkan adalah: tidak. Jadi, bahkan dalam hal ini, komputer kuantum fisik tidak akan memungkinkan kita untuk menyelesaikan masalah NP-complete sesuka hati.

Tidak ada implikasi yang diketahui: simulasi klasik komputer kuantum tidak memberi tahu kita tentang seberapa sulit masalah pencarian NP; solusi cepat untuk masalah pencarian NP tidak memberi tahu kami tentang seberapa cepat komputer kuantum dapat disimulasikan secara klasik. Skenario berikut dimungkinkan:

• $P=NP=BQP$
• $P=NP\subsetneq BQP$
• $P\subsetneq NP=BQP$
• $P\subsetneq NP\subsetneq BQP$
• $P\subsetneq NP$ , tetapi$P\subsetneq BQP$ dan N P yang tak tertandingi$BQP$$NP$
• Masalah NP membutuhkan brute force secara klasik, tetapi diselesaikan dengan algoritma kuantum yang cepat (walaupun tidak harus polinomial)

Blog seorang ilmuwan komputer kuantum teoretis yang berpengaruh, Scott Aaronson, memiliki tajuk " Jika Anda hanya mengambil satu informasi dari blog ini: Komputer Quantum tidak akan menyelesaikan masalah pencarian yang sulit secara instan dengan hanya mencoba semua solusi sekaligus ".

Dalam satu skenario (dianggap tidak mungkin), membangun komputer kuantum universal memang akan berimplikasi pada masalah P vs NP.

Ini berkembang pada kasus yang disebutkan oleh Yuval Filmus, "jika komputer kuantum dapat memecahkan masalah NP-hard dalam waktu polinomial".

Dalam situasi seperti itu, membangun komputer kuantum universal vs hanya secara teoretis tentang satu, akan memiliki implikasi untuk masalah P vs NP. Ini akan memungkinkan untuk kemungkinan hanya menggunakan komputer kuantum untuk mencari / menemukan bukti yang menyelesaikan P vs NP, yang kemudian dapat diverifikasi oleh komputer klasik.

Namun, seperti yang disebutkan oleh jawaban lain, sementara tidak ada bukti yang memisahkan BQP dan NP-lengkap, saat ini bukti dan harapan adalah bahwa komputer kuantum tidak akan dapat menyelesaikan masalah NP-complete secara efisien.