Dapatkah komputasi kuantum adiabatik lebih cepat daripada algoritma Grover?

Telah terbukti bahwa komputasi kuantum adiabatik setara dengan "standar", atau gerbang-model komputasi kuantum. Komputasi adiabatik, bagaimanapun, menunjukkan janji-janji untuk masalah optimasi, di mana tujuannya adalah untuk meminimalkan (atau memaksimalkan) fungsi yang dalam beberapa cara terkait dengan masalah - yaitu, menemukan contoh yang meminimalkan (atau memaksimalkan) fungsi ini segera menyelesaikan masalah.

Sekarang, menurut saya algoritma Grover pada dasarnya dapat melakukan hal yang sama: dengan mencari di ruang solusi, ia akan menemukan satu solusi (mungkin dari banyak solusi) yang memenuhi kriteria oracle, yang dalam hal ini setara dengan kondisi optimalitas, dalam waktu , di manaNadalah ukuran ruang solusi.$O(\sqrt N)$$N$

Algoritma ini telah terbukti optimal: seperti Bennett et al. (1997) mengatakan, "kelas tidak dapat diselesaikan pada kuantum mesin Turing dalam waktu o ( 2 n / 2 ) ". Dalam pemahaman saya, ini berarti tidak ada cara untuk membangun algoritma kuantum yang menemukan solusi dengan mencari melalui ruang lebih cepat dari O ( $\rm NP$$o(2^{n/2})$, di manaNberskala dengan ukuran masalah.$O(\sqrt N)$$N$

Jadi pertanyaan saya adalah: sementara komputasi kuantum adiabatik sering disajikan sebagai yang unggul dalam masalah optimasi, bisakah itu benar-benar lebih cepat daripada ? Jika ya, ini tampaknya bertentangan dengan optimalitas algoritma Grover, karena algoritma adiabatik apa pun dapat disimulasikan oleh rangkaian kuantum. Jika tidak, apa gunanya mengembangkan algoritma adiabatik, jika mereka tidak akan pernah lebih cepat dari sesuatu yang secara sistematis dapat kita bangun dengan sirkuit? Atau ada yang salah dengan pemahaman saya?$O(\sqrt N)$

Pertanyaan bagus. Untuk pencarian tidak terstruktur, komputasi kuantum adiabatik memang memberikan yang sama persis mempercepat bahwa algoritma Grover berbasis gerbang standar tidak, sebagaimana dibuktikan dalammakalah pentinginioleh Roland dan Cerf. Ini setuju dengan kesetaraan antara perhitungan kuantum adiabatik dan gerbang yang Anda sebutkan.$\sqrt{N}$

(Satu koreksi kecil untuk pertanyaan Anda: Anda benar bahwa dalam pengaturan untuk masalah pencarian-oracle, Anda perlu membingkai permintaan pencarian Anda sebagai pertanyaan ya / tidak yang dapat dijawab oleh oracle. Tetapi pertanyaan itu sebenarnya tidak diambil. menjadi "apakah mengekstremkan fungsi f ( x ) ?", seperti yang Anda usulkan. Sebaliknya, itu "adalah f ( x ) kurang dari atau sama dengan M ?" Lihat slide 9 dan 10 di sini . Itu karena oracle untuk yang terakhir pertanyaan dianggap sebagai model yang lebih realistis untuk pengaturan fisik, di mana iaDapat dibayangkan bahwa seseorang dapat secara langsung menghitung atau mengukur f ( x ) untuk suatu x yang diberikan$x$$f(x)$$f(x)$$M$$f(x)$$x$ , tetapi .)$f(x) - f_\text{min}$

Namun demikian, ada dua potensi keuntungan untuk QC adiabatik, yang keduanya sulit dipelajari secara teoritis. Yang pertama adalah praktis: sebenarnya membangun sirkuit kuantum besar yang koheren jauh lebih sulit daripada hanya menggambar mereka dalam artikel jurnal. Meskipun QC adiabatik tidak memiliki keunggulan mendasar dibandingkan pengaturan tradisional, mungkin lebih mudah untuk diterapkan secara eksperimental.

Kedua, peringatan besar yang sama berlaku untuk AQC untuk algoritma Grover standar: itu hanya berlaku untuk pencarian tidak terstruktur atau "kotak hitam", di mana kami benar-benar mengabaikan korelasi antara jawaban yang diberikan oleh oracle ketika dimasukkan dalam "mirip" atau " terkait "pertanyaan. Setiap masalah pencarian aktual yang kami pedulikan akan menurut definisi memiliki beberapa struktur untuk itu, meskipun struktur ini mungkin terlalu rumit untuk kita analisis. Sebagai contoh, jika kita memikirkan fungsi untuk diekstremkan sebagai lanskap energi, tampaknya masuk akal bahwa sistem tersebut dapat lebih mudah melakukan terowongan antara minima lokal "terdekat" daripada antara yang "jauh".

Jadi untuk benar-benar membandingkan manfaat relatif dari pengaturan adiabatik vs gerbang dalam percobaan nyata, Anda perlu "mengatasi penghalang relativiasi" dan mempertimbangkan struktur fungsi spesifik yang Anda coba ekstremkan, yang biasanya sangat sulit dilakukan. Ini membuatnya sangat sulit untuk menarik kesimpulan umum tentang keuntungan relatif kedua pendekatan di dunia nyata. Itu juga mengapa sangat sulit untuk membuktikan pemisahan kompleksitas tanpa syarat secara teoritis. Sejauh yang kita tahu, untuk dunia nyata daripada masalah oracle, komputer kuantum mungkin dapat memberikan percepatan eksponensial - mungkin bahkan untuk masalah NP-lengkap, yang akan menyiratkan bahwa NP BQP , meskipun ini dianggap sangat tidak mungkin.$\subset$

Komputasi kuantum adiabatik tidak dapat melakukan apa pun lebih cepat dari perhitungan kuantum berbasis sirkuit dari perspektif kompleksitas komputasi. Ini karena ada bukti matematis bahwa perhitungan kuantum berbasis sirkuit dapat secara efisien mensimulasikan perhitungan kuantum adiabatik [lihat bagian 5 dari makalah ini ].

bisakah itu benar-benar lebih cepat daripada $\mathcal{O}(\sqrt{N})$?

Jawabannya adalah tidak. Ini karena jika AQC bisa melakukannya, katakan,$\mathcal{O}(\log{N})$, maka QC berbasis sirkuit juga bisa melakukannya $\mathcal{O}(\log{N})$oleh algoritma di bagian 5 dari makalah yang saya tautkan di atas. Ini akan melanggar optimalitas$\mathcal{O}(\sqrt{N})$ untuk pencarian tidak terstruktur.