Jika P = NP benar, apakah komputer kuantum bermanfaat?

29

Misalkan P = NP benar. Apakah kemudian akan ada aplikasi praktis untuk membangun komputer kuantum seperti memecahkan masalah tertentu lebih cepat, atau akankah perbaikan seperti itu menjadi tidak relevan berdasarkan fakta bahwa P = NP benar? Bagaimana Anda mengkarakterisasi peningkatan efisiensi yang akan terjadi jika komputer kuantum dapat dibangun di dunia di mana P = NP, yang bertentangan dengan dunia di mana P! = NP?

Berikut adalah contoh yang dibuat-buat tentang apa yang saya cari:

Jika P! = NP, kita melihat bahwa kelas kompleksitas ABC sama dengan kompleksitas kelas kuantum XYZ ... tetapi jika P = NP, kelas ABC runtuh ke kelas terkait UVW.

(Motivasi: Saya ingin tahu tentang ini, dan relatif baru dalam komputasi kuantum; silakan migrasi pertanyaan ini jika tidak cukup maju.)

cc.complexity-theory complexity-classes quantum-computing Philip White
sumber
9
Kita tidak tahu apakah menyiratkan B Q P = P , sehingga mungkin ada beberapa masalah dalam B Q P yang tidak dalam P bahkan jika P = N P .... Itu juga merupakan pertanyaan terbuka apakah atau tidak B Q P adalah P H ....P=NPBQP=PBQPPP=NPBQPPH
Tayfun Bayar
4
Lebih dasarnya, kelas menangkap "efisien" algoritma quantum (dibatasi-kesalahan kuantum waktu polinomial). Itulah sebabnya formalisasi Tayfun ini dari pertanyaan Anda adalah salah satu alam, misalnya jika P = N P , ada masalah masih belum di P , namun dalam B Q P ? Dan ternyata itu sesuai dengan pengetahuan kita saat ini bahwa ini terjadi. BQPP=NPPBQP
usul

Jawaban:

30

Makalah " BQP dan Hirarki Polinomial " oleh Scott Aaronson secara langsung menjawab pertanyaan Anda. Jika P = NP, maka PH akan runtuh. Jika lebih jauh BQP berada di PH, maka tidak ada peningkatan kuantum akan mungkin dalam kasus itu. Di sisi lain, Aaronson memberikan bukti untuk masalah dengan percepatan kuantum di luar PH, sehingga percepatan seperti itu akan selamat dari keruntuhan PH.

Martin Schwarz
sumber
10
Sebenarnya Aaronson sendiri membuktikan bahwa dugaan bahwa ia didasarkan pada karya ini adalah salah. Lihat scottaaronson.com/papers/glnfalse.pdf
Alex Grilo
5
@AlexGrilo Beberapa hasil dalam makalah ini tanpa syarat dan masih berdiri: ada pemisahan oracle antara versi relasional BQP dan PH.
Sasho Nikolov
8
Klarifikasi: sementara "Dugaan Linial-Nisan Umum" ternyata salah, dugaan bahwa masalah Fourier Memeriksa / "Hubungan" tidak ada dalam PH masih berdiri. Hanya saja beberapa pendekatan lain akan diperlukan untuk membuktikannya. Juga, saya dapat memperkuat hasil saya bahwa ada oracle relatif yang ada masalah hubungan BQP tidak dalam BPP ^ PH, untuk menunjukkan bahwa ada oracle relatif yang P = NP, tetapi masih ada masalah hubungan BQP tidak dalam BPP . Ini ekstensi langsung, tapi sayangnya saya belum menulisnya.
Scott Aaronson
9

Jawabannya adalah ya tegas. Komputer kuantum pasti masih bermanfaat.

Komputer kuantum bukanlah ramalan untuk BQP, melainkan perangkat yang memproses status kuantum, dan dapat berkomunikasi menggunakan status kuantum. Sama seperti kemampuan untuk membuat permintaan non-deterministik secara fundamental lebih kuat daripada kemampuan untuk membuat pertanyaan murni deterministik, terlepas dari status P vs NP (dan memang ini adalah akar dari pemisahan oracle), kemampuan untuk membuat kueri kuantum dan untuk berkomunikasi menggunakan keadaan kuantum secara fundamental lebih kuat daripada lawannya yang murni klasik.

Ini mengarah pada keuntungan dalam berbagai aplikasi

  1. Kemampuan untuk menanyai oracle atau database eksternal dalam superposisi memberikan pemisahan yang dapat dibuktikan antara komputer kuantum dan komputer klasik dalam hal kompleksitas kueri.
  2. Ada berbagai tugas komunikasi yang melihat pengurangan drastis dalam biaya komunikasi yang digunakan komunikasi kuantum.
  3. Pemrosesan informasi kuantum memungkinkan protokol informasi yang secara teoritis aman untuk berbagai masalah yang lebih luas daripada yang dimungkinkan secara klasik. Tentu saja QKD tidak memerlukan komputer kuantum universal untuk diimplementasikan, tetapi banyak protokol untuk tugas lain melakukannya.
  4. Pra-dan pasca pemrosesan keadaan kuantum terjerat besar memungkinkan Anda untuk melanggar batas kebisingan tembakan dalam metrologi, menghasilkan pengukuran yang lebih tepat.

Selain argumen kompleksitas, ada alasan praktis lain untuk menginginkan komputer kuantum. Banyak data yang diproses pada komputer klasik dewasa ini berasal dari penginderaan terhadap dunia alami (misalnya melalui CCD dalam kamera digital). Namun, pengukuran seperti itu tentu membuang beberapa informasi tentang sistem untuk membuat hasil pengukuran sebagai string bit klasik (misalnya runtuh superposisi spasial foton), dan tidak selalu jelas informasi mana yang kemudian akan dianggap paling penting ketika awalnya merekam data. Oleh karena itu, masuk akal untuk percaya bahwa kemampuan untuk menyimpan dan memproses keadaan kuantum secara langsung, daripada meruntuhkannya dalam beberapa basis sebelum pemrosesan akan menjadi semakin diinginkan.

Joe Fitzsimons
sumber
4

Mengatasi bagian praktis.

P=NPO(n2103)

O(n1010000)

Sejauh yang saya tahu komputer kuantum yang cukup kuat akan menarik minat praktis dalam kasus ini.

joro
sumber
n2103
@SashoNikolov saya membahas praktis . Komputer kuantum yang faktor bilangan bulat 2048 bit secara efisien akan menarik bagi saya pada saat ini karena kunci RSA;).
joro
Saya percaya bahwa seseorang bisa mendapatkan algoritma pengurutan waktu linear dengan komputer kuantum.
Baby Dragon
2

Ada studi dalam hubungan antara BQP dan polinomial hierachy PH. Sebagai contoh, ada masalah yang relatif dimana BQP tidak terkandung dalam PH ( http://arxiv.org/abs/0910.4698 ), dan dugaan yang membuktikan hasil yang sama di dunia yang tidak ter-relativisasi ( http://arxiv.org /abs/1007.0305P#P⊆BPPPH

Kesimpulannya, kita tidak tahu apa sebenarnya kekuatan komputer kuantum tetapi ada hasil yang menunjukkan bahwa BQP mungkin berada di luar PH.

orang baru
sumber