Apakah ada pernyataan umum tentang jenis masalah apa yang dapat diselesaikan dengan lebih efisien menggunakan komputer kuantum?

Apakah ada pernyataan umum tentang jenis masalah apa yang dapat diselesaikan secara lebih efisien menggunakan komputer kuantum (hanya model gerbang kuantum)? Apakah masalah yang diketahui algoritma saat ini memiliki properti yang sama?

Sejauh yang saya mengerti komputasi kuantum membantu masalah subkelompok tersembunyi (Shor); Algoritma Grover membantu mempercepat masalah pencarian. Saya telah membaca bahwa algoritma kuantum dapat memberikan percepatan jika Anda mencari 'properti global' dari suatu fungsi (Grover / Deutsch).

1. Apakah ada pernyataan yang lebih ringkas dan benar tentang di mana komputasi kuantum dapat membantu?
2. Apakah mungkin untuk memberikan penjelasan mengapa fisika kuantum dapat membantu di sana (lebih disukai sesuatu yang lebih dalam sehingga 'gangguan dapat dieksploitasi')? Dan mengapa itu mungkin tidak akan membantu untuk masalah lain (misalnya untuk masalah NP-complete)?

Apakah ada makalah yang relevan yang membahas hal itu?

Saya telah menanyakan pertanyaan ini sebelumnya di cstheory.stackexchange.com tetapi mungkin lebih cocok di sini.

Tentang manfaat komputasi secara umum

Tanpa mungkin menyadarinya, Anda mengajukan versi dari salah satu pertanyaan paling sulit yang mungkin Anda tanyakan tentang ilmu komputer teoretis. Anda dapat mengajukan pertanyaan yang sama tentang komputer klasik, hanya alih-alih bertanya apakah menambahkan 'kuantum' bermanfaat, Anda dapat bertanya:

• Apakah ada pernyataan singkat tentang di mana algoritma acak dapat membantu?

  Dimungkinkan untuk mengatakan sesuatu yang sangat kabur di sini - jika Anda berpikir bahwa solusinya berlimpah (atau bahwa jumlah solusi untuk beberapa sub-masalah banyak) tetapi mungkin sulit untuk secara sistematis membangun satu, maka akan sangat membantu untuk dapat membuat pilihan secara acak untuk melewati masalah konstruksi sistematis. Namun berhati-hatilah, kadang-kadang alasan mengapa Anda tahu bahwa ada banyak solusi untuk sub-masalah adalah karena ada bukti menggunakan metode probabilistik . Ketika hal ini terjadi, Anda tahu bahwa jumlah solusi berlimpah dengan pengurangan apa yang berlaku sebagai algoritma acak yang membantu!

  Kecuali Anda memiliki cara lain untuk membenarkan fakta bahwa jumlah solusi berlimpah untuk kasus-kasus itu, tidak ada deskripsi sederhana kapan algoritma acak dapat membantu. Dan jika Anda memiliki tuntutan 'bantuan' yang cukup tinggi (keunggulan super-polinomial), maka yang Anda tanyakan adalah apakah , yang merupakan masalah yang belum terpecahkan dalam teori kompleksitas. $\mathsf P \ne \mathsf{BPP}$
  
  

• Apakah ada pernyataan singkat tentang di mana algoritma paralel dapat membantu?

  Di sini segalanya mungkin sedikit lebih baik. Jika masalah tampak seolah-olah dapat dipecah menjadi banyak sub-masalah independen, maka dapat diparalelkan - meskipun ini samar, "Anda akan tahu ketika Anda melihatnya" semacam kriteria. Pertanyaan utamanya adalah, akankah Anda mengetahuinya saat melihatnya? Apakah Anda menduga bahwa pengujian kelayakan sistem persamaan linear atas rasional tidak hanya dapat diparalelkan, tetapi dapat diselesaikan dengan menggunakan sirkuit -depth [cf  Comput. Kompleks. 8 (hlm. 99--126), 1999 ]?$O(\log^2 n)$

  Salah satu cara di mana orang mencoba melukis intuisi gambaran besar untuk ini adalah dengan mendekati pertanyaan dari arah yang berlawanan, dan mengatakan ketika diketahui bahwa algoritma yang diparalelkan tidak akan membantu. Secara khusus, itu tidak akan membantu jika masalah memiliki aspek yang secara inheren berurutan untuk itu. Tapi ini melingkar, karena 'berurutan' hanya berarti bahwa struktur yang dapat Anda lihat untuk masalahnya adalah yang tidak diparalelkan.

  Sekali lagi, tidak ada deskripsi yang sederhana dan komprehensif tentang kapan algoritma yang diparalelkan dapat membantu. Dan jika Anda memiliki tuntutan 'menolong' yang cukup tinggi (batas atas poly-logaritmik pada jumlah waktu, dengan asumsi paralaksasi polinomial), maka yang Anda tanyakan adalah apakah $\mathsf P \ne \mathsf{NC}$ , yang lagi-lagi merupakan masalah yang tidak terpecahkan dalam teori kompleksitas .
  
  

Prospek "deskripsi ringkas dan benar tentang kapan [X] membantu" tidak terlihat terlalu bagus pada titik ini. Meskipun Anda mungkin memprotes bahwa kami terlalu ketat di sini: dengan alasan menuntut lebih dari sekadar keuntungan polinomial, kami bahkan tidak dapat mengklaim bahwa mesin Turing non-deterministik itu 'membantu' (yang jelas absurd). Kita seharusnya tidak menuntut standar yang tinggi - jika tidak ada teknik untuk secara efisien menyelesaikan kepuasan, kita setidaknya harus menerima bahwa jika kita bisa mendapatkan mesin Turing yang tidak deterministik, kita memang akan merasa sangat sangat membantu . Tetapi ini berbeda dari kemampuan untuk mengkarakterisasi masalah mana yang akan kita manfaatkan.

Tentang manfaat komputer kuantum

Mengambil langkah mundur, apakah ada sesuatu yang dapat kita katakan tentang di mana komputer kuantum membantu?

Kita dapat mengatakan ini: komputer kuantum hanya dapat melakukan sesuatu yang menarik jika ia mengambil keuntungan dari struktur masalah, yang tidak tersedia untuk komputer klasik. (Ini diisyaratkan oleh komentar tentang "properti global" dari masalah, seperti yang Anda sebutkan). Tetapi kita dapat mengatakan lebih dari ini: masalah yang diselesaikan oleh komputer kuantum dalam model rangkaian kesatuan akan instantiate beberapa fitur dari masalah itu sebagai operator kesatuan . Fitur dari masalah yang tidak tersedia untuk komputer klasik adalah semua yang tidak memiliki (secara nyata) hubungan yang signifikan secara statistik dengan basis standar.

• Dalam kasus algoritma Shor, properti ini adalah nilai eigen dari operator permutasi yang didefinisikan dalam hal multiplikasi pada cincin.
• $\pm 1$

Tidak terlalu mengejutkan untuk melihat bahwa dalam kedua kasus, informasi berkaitan dengan nilai eigen dan vektor eigen. Ini adalah contoh luar biasa dari properti operator yang tidak perlu memiliki hubungan yang bermakna dengan basis standar. Tetapi tidak ada alasan khusus mengapa informasi tersebut harus merupakan nilai eigen. Semua yang diperlukan adalah untuk dapat menggambarkan operator kesatuan, mengkodekan beberapa fitur yang relevan dari masalah yang tidak jelas dari pemeriksaan dasar standar, tetapi dapat diakses dengan cara lain yang mudah dijelaskan.

Pada akhirnya, semua ini mengatakan bahwa komputer kuantum berguna ketika Anda dapat menemukan algoritma kuantum untuk menyelesaikan masalah. Tapi setidaknya itu adalah garis besar dari strategi untuk menemukan algoritma kuantum, yang tidak lebih buruk daripada garis besar strategi yang telah saya jelaskan di atas untuk algoritma acak atau paralel.

Keterangan saat komputer kuantum 'membantu'

Seperti yang dicatat orang lain di sini, "di mana komputasi kuantum dapat membantu" tergantung pada apa yang Anda maksud dengan 'bantuan'.

• Algoritma Shor sering digunakan dalam diskusi semacam itu, dan sesekali orang akan menunjukkan bahwa kita tidak tahu bahwa factorisation tidak dapat dipecahkan dalam waktu polinomial. Jadi, apakah kita benar-benar tahu bahwa "komputasi kuantum akan membantu untuk memfaktorkan angka"?

  Selain kesulitan dalam merealisasikan komputer kuantum, saya pikir di sini jawaban yang masuk akal adalah 'ya'; bukan karena kami tahu bahwa Anda tidak dapat memfaktorkan dengan efisien menggunakan komputer konvensional, tetapi karena kami tidak tahu bagaimana Anda akan melakukannya menggunakan komputer konvensional. Jika komputer kuantum membantu Anda melakukan sesuatu yang tidak memiliki pendekatan yang lebih baik untuk dilakukan, bagi saya tampaknya ini 'membantu'.

• $O(2^{0.386\,n})$

  Mungkin algoritma Grover seperti itu tidak terlalu membantu. Namun, mungkin berguna jika Anda menggunakannya untuk menguraikan strategi klasik yang lebih pintar di luar pencarian brute-force: menggunakan amplitude amplifikasi , generalisasi alami dari algoritma Grover ke pengaturan yang lebih umum, kita dapat meningkatkan kinerja banyak algoritma non-sepele untuk SAT (lihat misalnya [ACM SIGACT News  36 (hal.103-1010), 2005 - tautan PDF gratis ); tip topi untuk Martin Schwarz yang mengarahkan saya ke rujukan ini di komentar).

  Seperti halnya algoritma Grover, amplifikasi amplitudo hanya menghasilkan percepatan polinomial: tetapi berbicara secara praktis, bahkan percepatan polinomial mungkin menarik jika tidak dicuci oleh overhead yang terkait dengan melindungi informasi kuantum dari kebisingan.

TL; DR: Tidak, kami tidak memiliki tepat "umum" pernyataan tentang apa jenis masalah komputer kuantum dapat memecahkan , dalam hal teori kompleksitas. Namun, kami punya ide kasar.

Menurut sub-artikel Wikipedia tentang Relasi ke teori kompleksitas komputasi

Kelas masalah yang dapat diselesaikan secara efisien oleh komputer kuantum disebut BQP , untuk "kesalahan terbatas, kuantum, waktu polinomial". Komputer kuantum hanya menjalankan algoritma probabilistik , sehingga BQP pada komputer kuantum adalah lawan dari BPP ("kesalahan terbatas, probabilistik, waktu polinomial") pada komputer klasik. Ini didefinisikan sebagai serangkaian masalah yang dapat dipecahkan dengan algoritma waktu polinomial, yang probabilitas kesalahannya dibatasi dari setengahnya . Komputer kuantum dikatakan "memecahkan" masalah jika, untuk setiap contoh, jawabannya akan benar dengan probabilitas tinggi. Jika solusi itu berjalan dalam waktu polinomial, maka masalahnya ada di BQP.

BQP terkandung dalam kompleksitas kelas #P (atau lebih tepatnya di kelas terkait masalah keputusan P ^#P ), yang merupakan subkelas dari PSPACE .

BQP diduga terpisah dari NP-complete dan superset P yang ketat, tetapi itu tidak diketahui. Baik faktorisasi integer dan log diskrit berada dalam BQP. Kedua masalah ini adalah masalah NP yang diduga berada di luar BPP, dan karenanya di luar P. Keduanya diduga tidak lengkap NP. Ada kesalahpahaman umum bahwa komputer kuantum dapat menyelesaikan masalah NP-complete dalam waktu polinomial. Itu tidak diketahui benar, dan umumnya diduga salah.

Kapasitas komputer kuantum untuk mempercepat algoritma klasik memiliki batas yang kaku — batas atas kompleksitas komputasi kuantum. Bagian yang luar biasa dari perhitungan klasik tidak dapat dipercepat pada komputer kuantum. Fakta serupa terjadi untuk tugas komputasi tertentu, seperti masalah pencarian, yang algoritma Grover-nya optimal.

${\displaystyle O({\sqrt[{3}]{N}})}$$\displaystyle O({\sqrt {N}})$

Meskipun komputer kuantum mungkin lebih cepat daripada komputer klasik untuk beberapa jenis masalah, yang dijelaskan di atas tidak dapat menyelesaikan masalah yang tidak bisa diselesaikan oleh komputer klasik. Mesin Turing dapat mensimulasikan komputer kuantum ini, jadi komputer kuantum seperti itu tidak akan pernah bisa menyelesaikan masalah yang tidak dapat dipastikan seperti masalah penghentian. Keberadaan komputer kuantum "standar" tidak membantah tesis Gereja-Turing. Telah berspekulasi bahwa teori gravitasi kuantum, seperti teori-M atau gravitasi quantum loop, dapat memungkinkan komputer yang lebih cepat dibangun. Saat ini, mendefinisikan komputasi dalam teori-teori tersebut adalah masalah terbuka karena masalah waktu, yaitu, saat ini tidak ada cara yang jelas untuk menggambarkan apa artinya bagi pengamat untuk mengirimkan input ke komputer dan kemudian menerima output.

Adapun mengapa komputer kuantum dapat secara efisien menyelesaikan masalah BQP:

1. $n$$2n$

2. Biasanya, perhitungan pada komputer kuantum berakhir dengan pengukuran. Ini mengarah pada keruntuhan keadaan kuantum ke salah satu keadaan dasar. Dapat dikatakan bahwa keadaan kuantum diukur berada dalam keadaan yang benar dengan probabilitas tinggi.

Menariknya, jika kita secara teoritis mengijinkan post-selection (yang tidak memiliki implementasi praktis yang dapat diskalakan), kita mendapatkan kelas kompleksitas post-BQP :

Dalam teori kompleksitas komputasi, PostBQP adalah kelas kompleksitas yang terdiri dari semua masalah komputasi yang dapat dipecahkan dalam waktu polinomial pada mesin Turing kuantum dengan pemilihan dan kesalahan berikat (dalam arti bahwa algoritma tersebut benar setidaknya 2/3 dari waktu pada semua) input). Namun, Postselection tidak dianggap sebagai fitur yang dimiliki komputer realistis (bahkan yang kuantum), tetapi mesin-mesin postselecting menarik dari perspektif teoretis.

Saya ingin menambahkan apa yang disebutkan kadal @ Discrete di bagian komentar. Anda belum secara eksplisit mendefinisikan apa yang Anda maksud dengan "dapat membantu", namun, aturan praktis dalam teori kompleksitas adalah bahwa jika komputer kuantum "dapat membantu" dalam hal penyelesaian dalam waktu polinomial (dengan batas kesalahan) jika kelas Masalahnya itu bisa memecahkan kebohongan di BQP tetapi tidak di P atau BPP. Hubungan umum antara kelas kompleksitas yang kita bahas di atas diduga adalah:

$\text{P $\subseteq$ BPP $\subseteq$ BQP $\subseteq$ PSPACE}$

Namun, P = PSPACE, adalah masalah terbuka dalam Ilmu Komputer . Juga, hubungan antara P dan NP belum diketahui.

Tidak ada pernyataan umum seperti itu dan tidak mungkin akan ada satu segera. Saya akan menjelaskan mengapa ini terjadi. Untuk jawaban parsial untuk pertanyaan Anda, melihat masalah dalam dua kelas kompleksitas BQP dan PostBQP mungkin membantu.

Kelas kompleksitas yang paling dekat dengan masalah yang dapat diselesaikan secara efisien oleh komputer kuantum dari model gerbang kuantum adalah

1. BQP ; dan
2. PostBQP

BQP terdiri dari masalah yang dapat diselesaikan dalam waktu polinomial pada sirkuit kuantum. Algoritma kuantum yang paling penting, seperti algoritma Shor, memecahkan masalah dalam BQP.

$=$

Namun, saat ini tidak ada metode untuk secara praktis menerapkan pemilihan, sehingga PostBQP lebih menarik secara teoritis.

Hubungan antara P, NP dan BQP saat ini tidak diketahui; dan masalah terbuka pada urutan P vs. NP. Sebagai pernyataan umum tentang jenis masalah apa yang dapat dipecahkan dengan lebih efisien menggunakan komputer kuantum harus menjawab pertanyaan BQP vs P (jika BQP = P, maka tampaknya komputer kuantum tidak lebih efisien (setidaknya untuk teoretikus kompleksitas, setidaknya))

Mirip dengan gambar Blue, saya lebih suka yang ini dari Quanta Magazine , karena sepertinya secara visual merangkum apa yang kita bicarakan.