Mengapa anil kuantum tidak dapat dijelaskan oleh model gerbang?

Ini adalah pertanyaan yang saya terinspirasi untuk bertanya berdasarkan pertanyaan ini , yang mencatat bahwa anil kuantum adalah model yang sama sekali berbeda untuk perhitungan daripada model rangkaian biasa. Saya pernah mendengar ini sebelumnya, dan ini adalah pemahaman saya bahwa model gerbang tidak berlaku untuk kuantum-anil, tetapi saya tidak pernah benar-benar mengerti mengapa itu, atau bagaimana menguraikan perhitungan yang dapat dilakukan oleh seorang annealer. Seperti yang saya pahami dari beberapa pembicaraan (beberapa oleh D-wave sendiri!) Fakta bahwa para annealer terbatas pada permainan khusus Hamiltonian di dalamnya.

d-wave models annealing Emily Tyhurst
sumber

Jawaban:

Quantum Annealer, seperti mesin D-Wave adalah representasi fisik dari model Ising dan karena itu memiliki 'masalah' Hamiltonian dalam bentuk

H_{P} = \sum_{J = 1}^{n} h_{j} σ_{j}^{z} + \sum_{saya, j} J_{saya j} σ_{saya}^{z} σ_{j}^{z} .

$H_P = \sum_{J=1}^nh_j\sigma_j^z + \sum_{i, j}J_{ij}\sigma_i^z\sigma_j^z.$

Pada dasarnya, masalah yang harus dipecahkan dipetakan ke Hamiltonian di atas. Sistem dimulai dengan Hamiltonian dan parameter annealing, digunakan untuk memetakan Hamiltonian awal ke masalah Hamiltonian menggunakan . $H_I = \sum_{J=1}^nh'_j\sigma_j^x$ $s$ $H_I$ $H_P$ $H\left(s\right) = \left(1-s\right)H_I + sH_P$

Karena ini adalah anil, proses dilakukan cukup lambat untuk tetap berada di dekat kondisi dasar sistem sedangkan Hamiltonian bervariasi dengan masalah, menggunakan tunneling untuk tetap di dekat kondisi dasar seperti yang dijelaskan dalam jawaban Nat .

Sekarang, mengapa ini tidak bisa digunakan untuk menggambarkan model gerbang QC? Di atas adalah masalah Quadratic unconstrained binary optimization (QUBO) , yang merupakan NP-hard ... Memang, inilah artikel yang memetakan sejumlah masalah NP ke model Ising . Setiap masalah dalam NP dapat dipetakan ke masalah NP-hard dalam waktu polinomial dan factorisation integer memang merupakan masalah NP.

Nah, suhunya tidak nol, jadi tidak akan berada di kondisi dasar di seluruh anil dan akibatnya, solusinya masih hanya perkiraan. Atau, dalam istilah yang berbeda, probabilitas kegagalan lebih besar dari setengah (ini sama sekali tidak memiliki probabilitas keberhasilan yang layak dibandingkan dengan apa yang oleh QC universal dianggap 'layak' - dilihat dari grafik yang telah saya lihat, probabilitas keberhasilan untuk mesin saat ini sekitar dan ini hanya akan bertambah buruk dengan meningkatnya ukuran), dan algoritma anneal tidak dibatasi kesalahan. Sama sekali. Dengan demikian, tidak ada cara untuk mengetahui apakah Anda punya solusi yang tepat dengan sesuatu seperti factorisation integer. $0.2\%$

Apa yang (pada prinsipnya) lakukan adalah mendekati hasil yang tepat, sangat cepat, tetapi ini tidak membantu untuk apa pun di mana hasil yang tepat diperlukan karena beralih dari 'hampir benar' ke 'benar' masih merupakan hal yang sangat sulit ( yaitu mungkin masih NP secara umum, ketika masalah aslinya ada di NP) masalah dalam kasus ini, karena parameter yang / memberikan solusi 'hampir benar' tidak akan didistribusikan di dekat parameter yang / berikan solusi yang benar.

Edit untuk klarifikasi: artinya adalah bahwa kuantum annealer (QA) masih membutuhkan waktu eksponensial (meskipun berpotensi waktu eksponensial lebih cepat) untuk menyelesaikan masalah NP seperti factorisation bilangan bulat, di mana QC universal memberikan kecepatan eksponensial dan dapat menyelesaikan hal yang sama masalah dalam waktu poli. Inilah yang menyiratkan QA tidak dapat mensimulasikan QC universal dalam waktu poli (jika tidak dapat memecahkan masalah dalam waktu poli itu tidak bisa). Seperti yang ditunjukkan dalam komentar, ini tidak sama dengan mengatakan bahwa QA tidak dapat memberikan peningkatan yang sama dalam masalah lain, seperti pencarian basis data.

Mithrandir24601
sumber

Jika saya mengerti dengan benar, pada dasarnya Anda mengatakan bahwa seorang annealer kuantum tidak dapat menggambarkan rangkaian kuantum karena masalah menemukan minimum Hamiltonian sewenang-wenang adalah NP-hard. Saya tidak mengerti implikasi ini. Mensimulasikan sirkuit kuantum secara umum juga sulit untuk disimulasikan secara klasik (lihat misalnya 1610.01808 )

glS

Juga, beberapa masalah yang dapat dipecahkan melalui algoritma yang dinyatakan sebagai sirkuit kuantum diketahui juga dapat diselesaikan melalui anil kuantum. Contoh penting adalah pencarian basis data (lihat misalnya bagian II dari 1006.1696 ). Ini berarti bahwa dalam beberapa hal seseorang dapat dalam beberapa keadaan memetakan sirkuit aq menjadi masalah q anil. Bukankah ini juga membatalkan paragraf ketiga Anda (khususnya, klaim bahwa [ini] tidak dapat digunakan untuk menggambarkan model gerbang QC )

glS

@ GLS tidak, tidak sama sekali - masih membutuhkan waktu eksponensial untuk menemukan min (sesuai kertas di komentar kedua Anda) dari masalah NP-hard, jadi sementara ada masalah dalam P (misalnya pencarian database) di mana speedup mungkin dapat mencocokkan dengan QC universal, menyelesaikan masalah NP masih membutuhkan waktu yang eksponensial untuk berada dalam batas kesalahan, di mana QC universal mungkin dapat menyelesaikan masalah yang sama dalam waktu poli, misalnya factoration integer. Karena QA tidak dapat melakukan ini, QA tidak dapat mensimulasikan QC universal dalam waktu poli

Mithrandir24601

Ok, tapi bukan itu yang Anda katakan dalam jawaban (atau setidaknya, tidak secara eksplisit). Dari jawaban sepertinya Anda mengatakan bahwa QA tidak pernah dapat digunakan untuk memecahkan masalah yang diselesaikan melalui model gerbang QC. Hal ini sangat berbeda dengan mengatakan bahwa QA tidak dapat secara efisien memecahkan masalah NP-keras (yang bisa kadang-kadang dapat diselesaikan dengan sirkuit kuantum ... meskipun saya tidak berpikir ini telah terbukti, karena kita tidak tahu apakah Anjak benar-benar NP-hard, dan sebagian besar masalah lain di mana keuntungan kuantum telah ditunjukkan bukan masalah keputusan, setahu saya).

glS

Saya telah mengedit yang diharapkan bisa menjelaskan banyak hal. Tidak diketahui apakah P = NP atau tidak, pasti, tapi itu masih merupakan contoh spesifik dari QC yang secara eksponensial lebih cepat, menurut pengetahuan saat ini

Mithrandir24601

Annealing lebih merupakan taktik analog.

Intinya adalah Anda memiliki beberapa fungsi aneh yang ingin Anda optimalkan. Jadi, Anda bangkit di sekitarnya. Pada awalnya, " suhu " sangat tinggi, sehingga titik yang dipilih dapat memantul banyak. Kemudian ketika algoritma " dingin ", suhu turun, dan memantul menjadi kurang agresif.

Pada akhirnya, ia menetap pada optima lokal yang, idealnya, lebih disukai seperti optima global.

Berikut ini adalah animasi untuk anil simulasi (non-kuantum):

Tapi, itu konsep yang hampir sama untuk anil kuantum :

Sebaliknya, gerbang-logika jauh lebih digital daripada analog. Ini berkaitan dengan qubit dan operasi logis daripada hanya menemukan hasil setelah kekacauan memantul.

Nat
sumber

Terima kasih, ini menjelaskan batasan tertentu untuk saya. Apakah Anda tahu ada masalah yang tidak mungkin untuk diulangi sebagai masalah anil (Saya tahu Wikipedia menyatakan bahwa algoritma Shor tidak mungkin karena itu adalah masalah "mendaki bukit", tetapi jika Anda tahu lebih banyak tentang hal spesifik itu, saya akan sangat senang mendengar mereka :)

Emily Tyhurst

@ EmilyTyhurst Secara teknis, masalah apa pun dapat dijelaskan dalam istilah mendaki bukit. Ini lebih merupakan pertanyaan tentang bagaimana kelihatannya masalah terlihat ketika dijelaskan dalam format mendaki bukit. Masalah yang tidak pas bisa sangat jelek. Untuk masalah yang sepenuhnya non-cembung, mendaki bukit, paling banter, pada dasarnya adalah pencarian yang kasar.

Nat

@EmilyTyhurst Hah opps, salah baca komentar Anda di arah yang berlawanan. xD Tapi, ya, Anda dapat melakukan anil simulasi pada komputer kuantum sama seperti Anda dapat melakukannya pada komputer klasik. Lalu, saya kira apakah kita menyebutnya " anil kuantum " atau tidak, lebih menjadi soal semantik.

Nat

@EmilyTyhurst Ya, mereka pasti semua antar-convertible. Maksud saya, ini mirip dengan konsep kelengkapan Turing - jika kita memiliki logika yang lengkap, kita dapat membangun apa saja dengan itu.

Nat

Poin penting dari anil kuantum adalah mengubah Hamiltonian secara adiabatik sehingga negara tetap menjadi dasar dari (mengubah) Hamiltonian setiap saat, dan Anda berakhir dengan gs Hamiltonian terakhir, yang merupakan tujuan protokol . Bagaimana ini berhubungan dengan "melompat" yang Anda gambarkan di sini? Makalah ini ( 1006.1696 ) mungkin menarik tentang hal ini (khususnya, bagian terakhir dari kolom kedua dari halaman pertama).

glS