Konsekuensi dari

Sebagai seorang amatir TCS, saya membaca beberapa materi yang sangat populer tentang komputasi kuantum. Berikut adalah beberapa informasi dasar yang telah saya pelajari sejauh ini:

1. Komputer kuantum tidak dikenal untuk menyelesaikan masalah NP-complete dalam waktu polinomial.
2. "Sihir kuantum tidak akan cukup" (Bennett et al. 1997): jika Anda membuang struktur masalah, dan hanya mempertimbangkan ruang solusi yang mungkin, maka bahkan komputer kuantum membutuhkan sekitar $2^n$ langkah untuk menemukan yang benar (menggunakan algoritma Grover)$\sqrt{2^n}$
3. Jika algoritma waktu kuantum polinomial untuk masalah NP-lengkap pernah ditemukan, ia harus mengeksploitasi struktur masalah dengan cara tertentu (jika tidak, bullett 2 akan dikontradiksikan).

Saya punya beberapa pertanyaan (dasar) yang sepertinya tidak ada yang ditanyakan sejauh ini di situs ini (mungkin karena mereka mendasar). Misalkan seseorang menemukan kesalahan kuantum algoritma dibatasi waktu polinomial untuk (atau masalah NP-lengkap lainnya), sehingga menempatkan S A T di B Q P , dan menyiratkan N P ⊆ B Q P .$SAT$$SAT$$BQP$$NP \subseteq BQP$

Pertanyaan

1. Yang akan menjadi konsekuensi teoretis dari penemuan semacam itu? Bagaimana gambaran keseluruhan kelas kompleksitas akan terpengaruh? Kelas mana yang akan sama dengan kelas lainnya?
2. Hasil seperti itu tampaknya menunjukkan bahwa komputer kuantum memiliki kekuatan yang secara inheren lebih unggul daripada komputer klasik. Yang akan menjadi konsekuensi dari hasil seperti itu pada fisika? Akankah hal itu memancarkan cahaya pada masalah terbuka dalam fisika? Apakah fisika akan berubah setelah hasil yang serupa? Apakah hukum fisika yang kita kenal akan terpengaruh?
3. Kemungkinan (atau tidak) untuk mengeksploitasi struktur masalah dalam cara yang cukup umum (yaitu independen-contoh spesifik) tampaknya menjadi inti dari pertanyaan P = NP. Sekarang jika algoritma kuantum waktu polinomial kesalahan terikat untuk ditemukan, dan ia harus mengeksploitasi struktur masalah, bukankah struktur-eksploitasi-strateginya dapat digunakan juga dalam skenario klasik? Adakah bukti yang menunjukkan bahwa eksploitasi struktur seperti itu dimungkinkan untuk komputer kuantum, sementara tetap tidak mungkin untuk komputer klasik?$SAT$

Saya tidak akan mencoba menjawab pertanyaan pertama, karena seseorang seperti Scott Aaronson, Peter Shor atau John Watrous tidak diragukan lagi dapat memberi Anda jawaban yang jauh lebih komprehensif di bagian depan itu.

Mengenai pertanyaan 2, penting untuk dicatat bahwa komputer kuantum sebenarnya lebih kuat daripada komputer klasik dalam banyak hal:

1. Ada percepatan polinomial yang agak umum yang diperoleh oleh komputer kuantum daripada komputer klasik dalam sejumlah masalah. Dari sudut pandang kompleksitas, ini mungkin agak kurang menarik daripada percepatan eksponensial, tetapi merupakan sesuatu yang benar-benar dapat kita buktikan.
2. Kompleksitas komunikasi kuantum seringkali bervariasi secara dramatis dari kompleksitas komunikasi klasik untuk masalah yang sama. Sekali lagi, ini adalah sesuatu yang dapat dibuktikan (lihat misalnya game Mermin-GHZ).
3. Pertanyaan quantum ke oracle seringkali jauh lebih kuat daripada pertanyaan klasik oracle yang sama (lihat misalnya algoritma Deutsch-Josza).

Dengan pemikiran ini, sudah diketahui bahwa komputer kuantum secara fundamental lebih kuat daripada komputer klasik. Saya pikir saya akan benar dalam mengatakan bahwa mayoritas fisikawan yang mengerjakan hal-hal seperti itu sudah akan berasumsi bahwa tidak mungkin untuk menemukan algoritma klasik untuk mensimulasikan secara efisien setiap sistem kuantum, dan sementara itu hasil yang menunjukkan bahwa NP terkandung dalam BQP tentu akan mengejutkan, itu tidak akan cenderung memberikan terobosan dalam memahami fenomena fisik tertentu. Sebaliknya itu akan memberikan bukti yang agak kuat bahwa fisika kuantum sulit untuk disimulasikan.

Tidak ada fisika fundamental yang bergantung pada kompleksitas komputasi untuk mensimulasikannya, jadi menemukan algoritma kuantum yang efisien untuk masalah NP-complete tidak akan memiliki konsekuensi mendasar untuk kebenaran pemahaman kita saat ini tentang bagaimana fungsi alam semesta (meskipun saya cenderung setuju dengan saran Scott Aaronson bahwa menarik untuk melihat apakah Anda dapat memiliki hukum fisik yang muncul dari asumsi komputasi).

Sangat menggoda untuk mengatakan bahwa ini akan memiliki konsekuensi untuk evolusi adiabatik dari sistem kuantum (dan saya kira Anda mungkin mendapatkan satu atau dua jawaban yang menyarankan itu), dll., Tetapi ini akan salah, karena mereka diatur oleh proses fisik tertentu , dan dengan demikian menunjukkan bahwa pada prinsipnya mungkin untuk menyelesaikan SAT dalam waktu polinomial pada komputer kuantum, tidak akan mengatakan apa-apa tentang evolusi spesifik mereka.

Mengenai pertanyaan terakhir Anda, kami sudah memiliki contoh di mana struktur masalah dieksploitasi untuk menghasilkan algoritma kuantum polinomial, tetapi yang tidak mengarah pada algoritma klasik seperti itu (misalnya, anjak piutang). Jadi, sejauh pemahaman kita saat ini berjalan, masalah dengan struktur yang dapat dieksploitasi untuk menghasilkan algoritma kuantum waktu polinomial tidak menyiratkan bahwa struktur dapat dieksploitasi untuk menghasilkan algoritma waktu polinomial klasik.

Scott Aaronson sering senang menunjukkan (dan mungkin masih suka menunjukkan, dengan asumsi ia tidak bosan melakukannya) bahwa proses fisik tidak selalu menemukan minimum global dari lanskap energi . Secara khusus, jika Anda merumuskan contoh masalah optmisasi NP- lengkap sebagai masalah minimisasi energi untuk sistem fisik, tidak ada alasan - baik teoretis atau empiris - untuk percaya bahwa sistem fisik seperti itu akan "rileks" setelah beberapa waktu untuk solusi masalah ( yaitu  konfigurasi energi yang merupakan minimum global). Ini akan lebih cenderung santai ke minumum lokal: yang konfigurasi yang sedikit berbeda memerlukan lebih banyak energi, tetapi di mana konfigurasi yang jauh berbeda mungkin memiliki lebih sedikit energi.

Jadi, sementara membuktikan NP  ⊆  BQP akan menjadi kemenangan dari urutan pertama - untuk semua teori kompleksitas, tidak hanya untuk teori kuantum komputasi - itu akan menyarankan bahwa ada teori baru tentang model "fisik" perhitungan yang menunggu untuk ditemukan. Mengapa? Model komputasi dapat ditafsirkan sebagai model fisika (walaupun sangat terspesialisasi): yaitu, sumber daya komputasi apa yang secara fisik masuk akal. Salah satu 'slogan' dari komputasi kuantum adalah bahwa Nature isn't classical, [darn] it^† - jadi kecuali Anda dapat mensimulasikan mekanika kuantum pada komputer klasik, apa yang Anda secara fisik dapat menghitung secara efisien hampir pasti lebih kuat dari P . Namun, kami memiliki bukti bahwa itu kurang kuat daripada NP; jadi itu harus menjadi kurang kuat dari BQP juga, jika itu terjadi maka NP  ⊆  BQP .

Jadi, bukti NP  ⊆  BQP akan memberi kita trilemma: baik

1. sirkuit kuantum dapat disimulasikan secara efisien pada komputer klasik, membuktikan NP  ⊆  BQP  ⊆  P , dengan demikian melampaui mimpi atau mimpi terburuk setiap ahli teori;
2. Sirkuit kuantum tidak dapat disimulasikan pada komputer klasik, tetapi komputer kuantum yang dapat diskalakan dapat dibangun untuk menyelesaikan masalah dalam NP , sehingga menimbulkan minat yang sangat eksplosif dalam komputasi kuantum dan memastikan bahwa fisikawan eksperimental memiliki keamanan karir untuk masa yang akan datang;
3. ada model komputasi lain yang menunggu untuk ditemukan, antara antara P dan BQP berkuasa, yang menggambarkan (atau lebih tepatnya, perkiraan yang lebih baik ) apa yang secara fisik dapat dihitung.

Saya menduga bahwa uang pintar akan berada di # 3, sama menyenangkannya dengan # 1 atau # 2 dari perspektif akademis.

^†  Dengan permintaan maaf kepada Feynman, yang saya curigai tidak sering memotong kutukannya.