Mengapa komputer kuantum dalam beberapa hal lebih kuat daripada mesin Turing nondeterministic?

Akun populer-berita standar komputasi kuantum adalah bahwa komputer kuantum (QC) akan bekerja dengan memecah secara eksponensial banyak salinan paralel yang tidak berinteraksi dengan dirinya sendiri di alam semesta yang berbeda dan memiliki masing-masing upaya untuk memverifikasi sertifikat yang berbeda, kemudian pada akhir perhitungan , satu salinan yang menemukan sertifikat yang valid "mengumumkan" solusinya dan cabang lainnya secara ajaib menghilang.

Orang-orang yang tahu apa-apa tentang perhitungan kuantum teoretis tahu bahwa cerita ini benar-benar omong kosong, dan bahwa gagasan kasar yang dijelaskan di atas lebih mirip dengan mesin Turing (NTM) nondeterministic daripada komputer kuantum. Selain itu, kelas masalah dengan efisien yang dapat dipecahkan oleh NTM adalah NP dan oleh QC adalah BQP , dan kelas-kelas ini tidak diyakini sama.

Orang-orang yang mencoba mengoreksi presentasi populer dengan tepat menunjukkan bahwa narasi "banyak-dunia" yang sederhana sangat melebih-lebihkan kekuatan QC, yang diyakini tidak mampu memecahkan (katakanlah) masalah-masalah NP- lengkap. Mereka fokus pada representasi yang keliru dari proses pengukuran: dalam mekanika kuantum, yang hasil yang Anda ukur ditentukan oleh aturan Born, dan dalam kebanyakan situasi, probabilitas untuk mengukur jawaban yang salah benar-benar meningkatkan kemungkinan mengukur yang benar. (Dan dalam beberapa kasus, seperti pencarian kotak hitam, kami dapat membuktikan bahwa tidak ada sirkuit kuantum yang pintar yang dapat mengalahkan aturan Born dan memberikan percepatan eksponensial.) Jika kita bisaajaibnya "memutuskan apa yang harus diukur", maka kita akan dapat secara efisien menyelesaikan semua masalah di kelas kompleksitas PostBQP , yang diyakini jauh lebih besar daripada BQP .

Tapi saya belum pernah melihat orang yang secara eksplisit menunjukkan bahwa ada cara lain di mana karakterisasi populer salah, yang mengarah ke arah lain. BQP diyakini bukan subset ketat dari NP , tetapi bukannya tidak sebanding dengannya. Ada masalah seperti pemeriksaan Fourier yang diyakini tidak hanya terletak di luar NP , tetapi juga di luar seluruh hierarki polinomial PH . Jadi berkenaan dengan masalah seperti ini, narasi populer sebenarnya di bawah negara daripada melebih-lebihkan kekuatan QC.

Intuisi naif saya adalah bahwa jika kita dapat "memilih apa yang akan diukur", maka narasi populer akan lebih atau kurang benar, yang akan menyiratkan bahwa komputer super-kuantum ini akan mampu menyelesaikan secara efisien persis kelas NP . Tetapi kami percaya bahwa ini salah; sebenarnya PostBQP = PP , yang kami yakini sebagai superset NP yang ketat .

Apakah ada intuisi untuk apa yang terjadi di balik layar yang memungkinkan komputer kuantum (dalam beberapa hal) lebih kuat daripada mesin Turing nondeterministic? Agaknya kekuatan "inheren kuantum" ini, ketika dikombinasikan dengan postselection (yang dalam arti tertentu sudah dimiliki NTM) adalah apa yang membuat super-QC jauh lebih kuat daripada NTM. (Perhatikan bahwa saya sedang mencari beberapa intuisi yang secara langsung kontras dengan NTM dan QC dengan pasca pemilihan, tanpa "melewati" PP kelas kompleksitas klasik .)

speedup complexity-theory bqp Tparker
sumber

Jawaban:

Dari sudut pandang pseudo-fondasional, alasan mengapa BQP adalah kelas yang sangat kuat (untuk membuat frase) dari NP , adalah bahwa komputer kuantum dapat dianggap menggunakan interferensi destruktif.

Banyak kelas kompleksitas yang berbeda dapat dideskripsikan dalam hal (sifat yang kurang lebih rumit) dari jumlah cabang penerima NTM. Mengingat NTM dalam 'bentuk normal', yang berarti bahwa himpunan cabang-cabang komputasi adalah pohon biner lengkap (atau sesuatu yang mirip dengannya) dari beberapa kedalaman polinomial, kami dapat mempertimbangkan kelas bahasa yang didefinisikan dengan membuat perbedaan berikut:

Apakah jumlah cabang penerima nol, atau tidak nol? (Karakterisasi NP .)
Apakah jumlah cabang penerima kurang dari maksimum, atau persis sama dengan maksimum? (Karakterisasi coNP .)
Apakah jumlah cabang penerima paling banyak sepertiga, atau setidaknya dua pertiga dari total? (Karakterisasi BPP .)
Apakah jumlah cabang penerima kurang dari setengah, atau setidaknya setengah, dari total? (Karakterisasi PP .)
Apakah jumlah cabang penerima berbeda dari tepat setengah, atau sama dengan setengah, dari total? (Karakterisasi kelas yang disebut C ₌ P. )

Ini disebut kelas penghitungan , karena pada dasarnya mereka didefinisikan dalam hal jumlah cabang penerima.

Menafsirkan cabang-cabang suatu NTM sebagai hasil secara acak, mereka adalah pertanyaan tentang probabilitas penerimaan (bahkan jika properti ini tidak dapat diuji secara efisien dengan kepercayaan statistik). Pendekatan yang berbeda untuk menggambarkan kelas kompleksitas adalah dengan mempertimbangkan kesenjangan antara jumlah cabang penerima dan jumlah cabang menolak NTM. Jika menghitung akumulasi cabang-cabang komputasi NTM sesuai dengan probabilitas, orang dapat menyarankan bahwa membatalkan cabang-cabang yang menerima terhadap menolak cabang-cabang memodelkan pembatalan 'jalur' komputasi (seperti dalam jumlah-lintasan) dalam perhitungan kuantum - yaitu, sebagai pemodelan interferensi destruktif .

Batas atas yang paling dikenal untuk BQP , yaitu AWPP dan PP , siap didefinisikan dalam hal 'kesenjangan penerimaan' dengan cara ini. Namun NP kelas tidak memiliki karakterisasi yang jelas. Selain itu, banyak kelas yang diperoleh dari definisi dalam hal kesenjangan penerimaan tampaknya lebih kuat daripada NP . Orang dapat mengambil ini untuk menunjukkan bahwa 'gangguan destruktif nondeterministic' adalah sumber daya komputasi yang berpotensi lebih kuat daripada sekadar nondeterminisme; sehingga bahkan jika komputer kuantum tidak mengambil keuntungan penuh dari sumber daya komputasi ini, bagaimanapun ia dapat menahan kontainmen yang mudah di kelas-kelas seperti NP .

Niel de Beaudrap
sumber

Apakah P dan PSPACE menghitung kelas? Secara naif tampaknya ya untuk P , karena dapat didefinisikan sebagai serangkaian masalah sehingga setiap jalur menerima, tapi saya tidak yakin tentang PSPACE .

tparker

PSPACE bukan kelas penghitung, tidak. Anda berada di jalur yang benar dengan P --- Anda harus mengharuskan setiap jalur menerima atau setiap pah menolak (atau persyaratan yang sama kuatnya), atau Anda mungkin berakhir dengan coNP , coRP , atau kelas lain yang tidak diketahui sama P .

Niel de Beaudrap

Agaknya PH juga bukan kelas penghitungan, karena secara alami diformulasikan dalam bentuk mesin Turing bolak-balik dan bukan bersifat deterministik?

tparker

B P P \subset P P \subset N P

$\mathbf{BPP} \subset \mathbf{PP} \subset \mathbf{NP}$

B P P \subset N P \subset P P

$\mathbf{BPP} \subset \mathbf{NP} \subset \mathbf{PP}$

B P P \subseteq N P

$\mathsf {BPP \subseteq NP}$

B P P \subseteq N P^{N P} \cap c o N P^{N P}

$\mathsf {BPP \subseteq NP^{NP} \cap coNP^{NP}}$

-1

Jawaban ini 'dimigrasikan' sejak saat pertanyaan ini diajukan pada Ilmu Komputer (Penulis tetap sama)

Nah, satu alasan utama adalah bahwa tidak ada algoritma kuantum yang memecahkan masalah NP-hard dalam waktu polinomial.

Lain adalah bahwa anil kuantum adiabetik (seperti dalam Dwave) hanya bisa mengalahkan anil kuantum klasik.

$\neq$ $=$ $\neq$ $\neq$ $=$ $=$

$=$

$\neq$

Ada masalah seperti pemeriksaan Fourier yang diyakini tidak hanya terletak di luar NP, tetapi sebenarnya di luar seluruh hierarki polinomial. Jadi sehubungan dengan masalah seperti ini, narasi populer sebenarnya mengecilkan daripada melebih-lebihkan kekuatan QC.

$O(n)$ $O(n)$

Kadal diskrit
sumber