Model adiabatik
Model perhitungan kuantum ini dimotivasi oleh ide-ide dalam teori kuantum banyak-tubuh, dan berbeda secara substansial dari model sirkuit (dalam hal ini adalah model waktu kontinu) dan dari berjalan kuantum waktu kontinu (dalam hal ia memiliki waktu- evolusi tergantung).
Perhitungan adiabatik biasanya mengambil bentuk berikut.
- Mulailah dengan beberapa set qubit, semuanya dalam beberapa kondisi sederhana seperti . Panggil keadaan global awal .| ψ 0 ⟩| + ⟩| ψ0⟩
- Subjek qubit ini ke interaksi Hamiltonian yang adalah keadaan dasar yang unik (keadaan dengan energi terendah). Sebagai contoh, mengingat , kita dapat memilih . | ψ 0 ⟩ | ψ 0 ⟩ = | + ⟩ ⊗ n H 0 = - ∑ k σ ( x ) kH0| ψ0⟩| ψ0⟩ = | + ⟩⊗ nH0= - ∑kσ( x )k
- Pilih Hamiltonian akhir , yang memiliki kondisi dasar unik yang menyandikan jawaban untuk masalah yang Anda minati. Misalnya, jika Anda ingin menyelesaikan masalah kepuasan kendala, Anda dapat menentukan Hamiltonian , di mana jumlah diambil atas kendala dari masalah klasik, dan di mana setiap adalah operator yang mengenakan penalti energi (kontribusi energi positif) ke setiap negara basis standar yang mewakili tugas klasik yang tidak memenuhi kendala .H 1 = ∑ c h c c h c cH1H1= ∑chcchcc
- Tentukan interval waktu dan Hamiltonian yang bervariasi sehingga dan . Pilihan umum tetapi tidak perlu adalah dengan mengambil interpolasi linier .H ( t ) H ( 0 ) = H 0 H ( T ) = H 1 H ( t ) = tT⩾ 0H( t )H( 0 ) = H0H( T) = H1H( t ) = tTH1+ ( 1 - tT) H0
- Untuk waktu hingga , izinkan sistem untuk berevolusi di bawah Hamiltonian bervariasi , dan ukur qubit pada output untuk mendapatkan hasil .t = T H ( t ) y ∈ { 0 , 1 } nt = 0t = TH( t )y∈ { 0 , 1 }n
Dasar dari model adiabatik adalah teorema adiabatik , di mana ada beberapa versi. Versi oleh Ambainis dan Regev [ arXiv: quant-ph / 0411152 ] (contoh yang lebih ketat) menyiratkan bahwa jika selalu ada "celah energi" setidaknya antara keadaan dasar dan keadaan tereksitasi pertama untuk semua , dan norma operator dari turunan pertama dan kedua dari cukup kecil (yaitu,λ > 0H( t )0 ⩽ t ⩽ THH( t )tidak bervariasi terlalu cepat atau tiba-tiba), maka Anda dapat membuat probabilitas untuk mendapatkan output yang Anda inginkan sebesar yang Anda inginkan hanya dengan menjalankan perhitungan dengan cukup lambat. Selain itu, Anda dapat mengurangi kemungkinan kesalahan dengan faktor konstan apa pun hanya dengan memperlambat keseluruhan perhitungan dengan faktor yang terkait secara polinomi.
Meskipun sangat berbeda dalam presentasi dari model rangkaian kesatuan, telah ditunjukkan bahwa model ini setara waktu polinomial dengan model rangkaian kesatuan [ arXiv: quant-ph / 0405098 ]. Keuntungan dari algoritma adiabatik adalah bahwa ia menyediakan pendekatan yang berbeda untuk membangun algoritma kuantum yang lebih dapat menerima masalah optimasi. Salah satu kelemahannya adalah tidak jelas bagaimana melindunginya dari kebisingan, atau untuk mengetahui bagaimana kinerjanya menurun di bawah kendali yang tidak sempurna. Masalah lain adalah bahwa, bahkan tanpa ketidaksempurnaan dalam sistem, menentukan seberapa lambat untuk menjalankan algoritma untuk mendapatkan jawaban yang andal adalah masalah yang sulit - itu tergantung pada kesenjangan energi, dan itu tidak mudah secara umum untuk mengetahui apa energi gap adalah untuk Hamiltonian statisH, apalagi yang bervariasi waktu .H( t )
Namun, ini adalah model kepentingan teoretis dan praktis, dan memiliki perbedaan menjadi yang paling berbeda dari model rangkaian kesatuan pada dasarnya apa pun yang ada.
Model Sirkuit Kesatuan
Ini adalah model perhitungan kuantum yang paling terkenal. Dalam model ini seseorang memiliki kendala seperti berikut:
Detail kecil dapat berubah (misalnya, set unitaries satu dapat melakukan, apakah satu memungkinkan persiapan di negara-negara murni lain seperti , | + ⟩ , | - ⟩ , apakah pengukuran harus dalam dasar standar atau juga bisa dalam beberapa dasar lain), tetapi ini tidak membuat perbedaan penting.| 1 ⟩ | + ⟩ | - ⟩
sumber
Berjalan kuantum waktu-diskrit
"Jalan kuantum waktu diskrit" adalah variasi kuantum pada jalan acak, di mana terdapat 'walker' (atau beberapa 'walker') yang mengambil langkah-langkah kecil dalam grafik (misalnya rantai node, atau grid persegi panjang) ). Perbedaannya adalah bahwa ketika walker acak mengambil langkah ke arah yang ditentukan secara acak, walker kuantum mengambil langkah ke arah yang ditentukan oleh register "koin" kuantum, yang pada setiap langkah "dibalik" oleh transformasi kesatuan daripada diubah dengan sampel ulang variabel acak. Lihat [ arXiv: quant-ph / 0012090 ] untuk referensi awal.
Demi kesederhanaan, saya akan menggambarkan jalan kuantum pada siklus ukuran ; meskipun kita harus mengubah beberapa detail untuk mempertimbangkan berjalan kuantum pada grafik yang lebih umum. Dalam model perhitungan ini, seseorang biasanya melakukan hal berikut.2n
Perbedaan utama antara ini dan jalan acak adalah bahwa "lintasan" jalan yang berbeda yang mungkin dari pejalan kaki dilakukan secara koheren dalam superposisi, sehingga mereka dapat mengganggu secara destruktif. Ini mengarah pada perilaku pejalan kaki yang lebih mirip gerak balistik daripada difusi. Memang, presentasi awal model seperti ini dibuat oleh Feynmann, sebagai cara untuk mensimulasikan persamaan Dirac.
Model ini juga sering digambarkan dalam hal mencari atau menemukan elemen 'ditandai' dalam grafik, dalam hal ini seseorang melakukan langkah lain (untuk menghitung apakah node walker ditandai, dan kemudian untuk mengukur hasil perhitungan itu. ) sebelum kembali ke Langkah 2. Variasi lain dari jenis ini masuk akal.
Untuk melakukan quantum walk pada grafik yang lebih umum, seseorang harus mengganti register "position" dengan yang bisa mengekspresikan semua node grafik, dan register "coin" dengan yang bisa mengekspresikan insiden tepi ke sebuah titik. "Operator koin" kemudian juga harus diganti dengan yang memungkinkan pejalan kaki untuk melakukan superposisi menarik lintasan yang berbeda. (Apa yang dianggap sebagai 'menarik' tergantung pada apa motivasi Anda: fisikawan sering mempertimbangkan cara-cara mengubah operator koin mengubah evolusi kepadatan probabilitas, bukan untuk tujuan komputasi tetapi sebagai cara menyelidiki fisika dasar menggunakan quantum walks sebagai model mainan yang wajar dari gerakan partikel. ] berjalan kuantum waktu-diskrit.
Model perhitungan ini secara tegas merupakan kasus khusus dari model rangkaian kesatuan, tetapi dimotivasi dengan intuisi fisik yang sangat spesifik, yang telah mengarah pada beberapa wawasan algoritmik (lihat misalnya [ arXiv: 1302.3143 ]) untuk speedup waktu polinomial di bounded-error algoritma kuantum. Model ini juga merupakan kerabat dekat dari berjalan kuantum waktu kontinu sebagai model perhitungan.
sumber
Sirkuit kuantum dengan pengukuran perantara
Ini adalah sedikit variasi pada "sirkuit kesatuan", di mana satu memungkinkan pengukuran di tengah algoritma serta akhirnya, dan di mana orang juga memungkinkan operasi di masa depan bergantung pada hasil pengukuran tersebut. Ini merupakan gambaran realistis dari prosesor kuantum yang berinteraksi dengan perangkat kontrol klasik, yang antara lain adalah antarmuka antara prosesor kuantum dan pengguna manusia.
Pengukuran perantara secara praktis diperlukan untuk melakukan koreksi kesalahan, dan karenanya pada prinsipnya ini adalah gambaran yang lebih realistis dari perhitungan kuantum daripada model rangkaian kesatuan. tetapi tidak jarang bagi ahli teori dari jenis tertentu untuk lebih memilih pengukuran dibiarkan sampai akhir (menggunakan prinsip pengukuran yang ditangguhkan untuk mensimulasikan pengukuran 'perantara'). Jadi, ini mungkin perbedaan yang signifikan untuk dibuat ketika berbicara tentang algoritma kuantum - tetapi ini tidak mengarah pada peningkatan teoritis dalam kekuatan komputasi dari algoritma kuantum.
sumber
Anil kuantum
Anil kuantum adalah model komputasi kuantum yang, secara umum, generalisasi model komputasi adiabatik. Ini telah menarik perhatian populer - dan komersial - sebagai hasil dari pekerjaan D-WAVE pada subjek.
Tepatnya apa yang terdiri dari anil kuantum tidak didefinisikan dengan baik seperti model komputasi lainnya, pada dasarnya karena lebih menarik bagi teknologi kuantum daripada ilmuwan komputer. Secara umum, kita dapat mengatakan bahwa hal itu biasanya dianggap oleh orang-orang dengan motivasi insinyur, daripada motivasi ahli matematika, sehingga subjek tampaknya memiliki banyak intuisi dan aturan praktis tetapi hanya sedikit hasil 'formal'. Bahkan, dalam jawaban untuk pertanyaan saya tentang anil kuantum ,
Andrew O
lebih jauh mengatakan bahwa " anil kuantum tidak dapat didefinisikan tanpa pertimbangan algoritma dan perangkat keras". Namun demikian," anil kuantum "tampaknya cukup terdefinisi dengan baik untuk digambarkan sebagai cara mendekati bagaimana menyelesaikan masalah dengan teknologi kuantum dengan teknik spesifik - dan meskipun adaAndrew O
penilaian, saya pikir itu mewujudkan beberapa model yang didefinisikan secara implisit dari perhitungan. Saya akan mencoba untuk menggambarkan model itu di sini.Intuisi di balik model
Anil kuantum yang 'tepat' (dengan demikian) mengandaikan bahwa evolusi mungkin tidak dilakukan dalam rezim adiabatik, dan memungkinkan untuk kemungkinan transisi diabetes, tetapi hanya meminta peluang tinggi untuk mencapai yang optimal - atau bahkan lebih pragmatis, mencapai hasil yang akan sulit ditemukan menggunakan teknik klasik. Tidak ada hasil resmi tentang seberapa cepat Anda dapat mengubah Hamiltonian Anda untuk mencapai ini: subjek tampaknya sebagian besar terdiri dari bereksperimen dengan heuristik untuk melihat apa yang berhasil dalam praktiknya.
Perbandingan dengan annealing simulasi klasik
Terlepas dari terminologinya, tidak segera jelas bahwa ada banyak kesamaan anil yang kuantum dengan anil klasik. Perbedaan utama antara anil kuantum dan anil simulasi klasik tampaknya adalah:
Dalam anil kuantum, keadaan dalam beberapa hal idealnya adalah keadaan murni, bukan keadaan campuran (sesuai dengan distribusi probabilitas dalam anil klasik);
Dalam anil kuantum, evolusi didorong oleh perubahan eksplisit dalam parameter Hamilton daripada parameter eksternal.
Pada tingkat yang murni operasional, tampak bahwa anil kuantum memberikan keunggulan kinerja daripada anil klasik (lihat misalnya slide ini tentang perbedaan kinerja antara anil kuantum vs klasik , dari grup Troyer di ETH, ca. 2014).
Anil kuantum sebagai fenomena, tidak seperti model komputasi
Karena anil kuantum lebih dipelajari oleh para teknolog, mereka berfokus pada konsep mewujudkan anil kuantum sebagai efek daripada mendefinisikan model dalam hal prinsip-prinsip umum. (Sebuah analogi kasar akan mempelajari model rangkaian kesatuan hanya karena itu merupakan sarana untuk mencapai 'efek' estimasi nilai eigen atau amplitude amplifikasi.)
Oleh karena itu, apakah sesuatu dianggap sebagai "anil kuantum" digambarkan oleh setidaknya beberapa orang sebagai perangkat keras, dan bahkan bergantung pada input: misalnya, pada tata letak qubit, tingkat kebisingan mesin. Tampaknya bahkan mencoba mendekati rezim adiabatik akan mencegah Anda mencapai anil kuantum, karena gagasan tentang apa yang termasuk anil kuantum bahkan mencakup gagasan bahwa kebisingan (seperti dekoherensi) akan mencegah anil terealisasi: sebagai efek komputasi , berlawanan dengan model komputasi , anil kuantum pada dasarnya mensyaratkan bahwa jadwal anil lebih pendek daripada waktu dekoherensi sistem kuantum.
Beberapa orang kadang-kadang menggambarkan kebisingan sebagai sesuatu yang penting untuk proses anil kuantum. Misalnya, Boixo et al. [ arXiv: 1304.4595 ] tulis
Mungkin akurat untuk menggambarkannya sebagai fitur sistem yang tak terhindarkan di mana seseorang akan melakukan annealing (hanya karena noise adalah fitur yang tak terhindarkan dari sistem di mana Anda akan melakukan pemrosesan informasi kuantum dalam bentuk apa pun ): seperti
Andrew O
menulis " pada kenyataannya tidak ada mandi benar - benar membantu anil kuantum ". Ada kemungkinan bahwa proses disipatif dapat membantu anil kuantum dengan membantu sistem membangun populasi pada keadaan berenergi lebih rendah (seperti yang disarankan oleh pekerjaan oleh Amin et al. , [ ArXiv: cond-mat / 0609332 ]), tetapi ini tampaknya pada dasarnya menjadi efek klasik, dan secara inheren membutuhkan lingkungan suhu rendah yang tenang daripada 'keberadaan kebisingan'.Garis bawah
Dapat dikatakan - khususnya oleh mereka yang mempelajarinya - bahwa anil kuantum adalah efek, bukan model perhitungan. Suatu "annealer kuantum" akan lebih baik dipahami sebagai "sebuah mesin yang menyadari efek dari anil kuantum", daripada sebuah mesin yang mencoba untuk mewujudkan model perhitungan yang dikenal sebagai ' anil kuantum '. Namun, hal yang sama dapat dikatakan tentang perhitungan kuantum adiabatik, yang - menurut pendapat saya dengan benar - digambarkan sebagai model perhitungan dalam dirinya sendiri.
Mungkin akan adil untuk menggambarkan anil kuantum sebagai pendekatan untuk mewujudkan heuristik yang sangat umum , dan bahwa ada model implisit perhitungan yang dapat dikarakteristikkan sebagai kondisi di mana kita dapat mengharapkan heuristik ini berhasil. Jika kita menganggap anil kuantum dengan cara ini, itu akan menjadi model yang mencakup rezim adiabatik (dengan nol-noise) sebagai kasus khusus, tetapi pada prinsipnya mungkin lebih umum.
sumber