Apakah komputasi kuantum adiabatik sekuat model sirkuit?

9

Banyak literatur komputasi kuantum berfokus pada model rangkaian. Komputasi kuantum adiabatik tidak didasarkan pada penerapan urutan operator kesatuan, tetapi pada perubahan Hamiltonian yang bergantung waktu. Saya mencari wawasan tentang hal-hal berikut.

  1. Apakah komputasi kuantum adiabatik sekuat model rangkaian, atau apakah secara inheren kurang kuat?
  2. Apakah ada kelas kompleksitas yang secara khusus terkait dengan komputasi adiabatik yang bertentangan dengan model rangkaian?
  3. Bagaimana seseorang mengukur secara kuantitatif kekuatan komputasi adiabatik versus kekuatan model rangkaian?
cc.complexity-theory reference-request complexity-classes quantum-computing quantum-information vzn
sumber
ok NdB ya itu tidak dirumuskan dengan sempurna, terima kasih kepada responden untuk klarifikasi, persis apa yang dicari. muncul sebagai reaksi terhadap pertanyaan orang lain di obrolan , bisa diskusi lebih lanjut di sana oleh siapa pun yang tertarik. Saya yakin orang lain dengan rep yang lebih tinggi dapat menemukan pertanyaan yang lebih baik tetapi tampaknya ada korelasi terbalik yang kuat di sana. Adapun bkg semua referensi yang mendukungnya dipotong oleh suntingan pertama. juga, mengajukan pertanyaan lain di masa lalu yang mengarah ke pertanyaan ini tetapi pertanyaan lain itu menguap. poof
vzn
2
Saya melihat hasil edit sebelumnya. Rilis berita bukan artikel penelitian. Lebih penting lagi, pada dasarnya setiap artikel penelitian akan menunjukkan kepada Anda bahwa komputasi kuantum adiabatik pada dasarnya berbasis qubit. Tidak masalah apa yang mendorongnya: pertanyaan Anda tidak menunjukkan banyak usaha - dan aktivitas demi aktivitas adalah apa yang coba dihindari oleh StackExchange .
Niel de Beaudrap
3
Vzn: intinya adalah ini: mengapa Anda tidak menyelidiki itu sendiri? Dan jika setelah benar-benar menyelidiki Anda tidak dapat menemukan referensi apapun, mengapa tidak meminta itu pertanyaan? Itu akan konstruktif, dan Anda bisa bertanya (dan menyelidiki) pertanyaan tentang komputasi kuantum secara umum, bukan hanya komputasi adiabatik.
Niel de Beaudrap
4
@NieldeBeaudrap: Bagi saya sepertinya dia hanya menggunakan "model qubit" sebagai pengganti model sirkuit, yang tentu saja bukan substitusi yang akurat, tetapi saya menganggapnya sebagai makna pertanyaan.
Joe Fitzsimons
1
@ JoFitzsimons: cukup adil - itu mungkin pendekatan yang paling praktis, karena menyiratkan bahwa pertanyaan itu memiliki jawaban yang masuk akal, yaitu yang di bawah ini. Meskipun vzn harus mengedit pertanyaan untuk benar-benar menanyakan pertanyaan itu, jika demikian, untuk anak cucu.
Niel de Beaudrap

Jawaban:

19

Dua klarifikasi cepat:

  1. Adiabatic QC biasanya "berdasarkan qubit" sama seperti QC berbasis sirkuit - Saya tidak tahu dari mana Anda mendapat ide bahwa itu bukan! (Meskipun orang juga bisa menggunakan qutrits atau blok bangunan lainnya, baik dalam sirkuit atau model adiabatik.)

  2. Seperti yang ditunjukkan Mateus, hasil adil yang terkenal dari Aharonov et al. mengatakan bahwa "adiabatik QC setara dengan QC standar." Tetapi hasil itu perlu ditafsirkan dengan sedikit perhatian. Ini berlaku jika keadaan akhir dari perhitungan adiabatik dapat berubah-ubah - sehingga, khususnya, keadaan akhir dapat menyandikan seluruh sejarah perhitungan kuantum berbasis sirkuit. Namun, jika keadaan akhir harus menjadi keadaan dasar komputasi klasik --- seperti biasanya dalam algoritma optimisasi adiabatik("asli" contoh adiabatik QC) --- maka adiabatik QC pasti dapat disimulasikan dalam model rangkaian, tetapi kebalikannya tidak diketahui dan jauh dari jelas. Jadi dengan asumsi yang terakhir, ada kemungkinan bahwa optimasi adiabatik benar-benar menimbulkan kelas kompleksitas baru antara BPP dan BQP.

Scott Aaronson
sumber
3
Makalah Bacon dan Flammia tentang perhitungan status gugus adiabatik tampaknya memberikan rute alternatif yang, sejauh yang saya bisa lihat, agak menghindari kebutuhan akan sejarah, meskipun Anda masih memiliki banyak qubit tambahan.
Joe Fitzsimons
2
Namun, skema Bacon & Flammia tidak memiliki keadaan dasar yang unik dan karenanya secara signifikan berbeda dari AQC konvensional.
Norbert Schuch
3
@NorbertSchuch: Tetapi jika Anda menambahkan ketentuan stabilizer tambahan ke Hamiltonian awal yang sesuai dengan memperbaiki keadaan awal, maka keadaan dasar adalah non-merosot.
Joe Fitzsimons