Protokol apa yang telah diusulkan untuk mengimplementasikan RAM kuantum?

16

Peran penting dari memori akses acak (RAM) dalam konteks perhitungan klasik membuatnya wajar untuk bertanya-tanya bagaimana seseorang dapat menggeneralisasi konsep seperti itu ke domain kuantum.

Karya yang paling terkenal (dan pertama?) Yang mengusulkan arsitektur QRAM yang efisien adalah Giovannetti et al. 2007 . Dalam karya ini ditunjukkan bahwa pendekatan "bucket brigate" mereka memungkinkan akses ke konten memori dengan operasi , di mana adalah jumlah slot memori. Ini adalah peningkatan eksponensial sehubungan dengan pendekatan alternatif, yang memerlukan operasi . Menerapkan arsitektur ini bagaimanapun sangat tidak penting dari sudut pandang eksperimental.O(logN)NO(Nα)

Apakah cara di atas hanya diketahui untuk mengimplementasikan QRAM? Atau ada karya teoretis lain ke arah ini? Jika demikian, bagaimana mereka membandingkan (pro dan kontra) dengan Giovannetti et al. usul?

glS
sumber

Jawaban:

7

Ringkasan yang baik tentang keadaan QRAM saat ini (per 2017) dapat ditemukan dalam makalah ini , dan perbandingannya dengan metode klasik dapat ditemukan dalam pembicaraan ini . Jenis "ember brigade" Giovannetti QRAM tampaknya masih menjadi yang terbaik yang diketahui, meskipun ada modifikasi. Ada peringatan serius untuk penggunaan QRAM semacam itu, dan tidak ada alternatif yang menghindari ini telah diusulkan (selain menggunakan komputer klasik paralel paralel).

QRAM "bucket brigade" dikodekan dalam superposisiN dcatatan(Nd)HAI(catatan(Nd))

Masalahnya tergantung pada berapa banyak komponen yang harus aktif sekaligus. Idealnya, jumlah komponen aktif hanya perlu linier dengan jumlah qubit dalam memori. Namun, implementasi aktual biasanya jauh dari ideal.

Makalah ini , misalnya, melihat efek kebisingan, dan menyimpulkan bahwa kebutuhan untuk koreksi kesalahan dapat menghilangkan kelebihan dari sejumlah kecil komponen aktif. Tingkat keparahan masalah potensial ini tergantung pada algoritma apa yang digunakan oleh komputer kuantum, dan berapa kali QRAM harus ditanyai. Untuk jumlah polinomial kueri, toleransi kesalahan penuh dapat dihindari. Tetapi untuk pertanyaan superpolinomial, seperti untuk pencarian Grover, toleransi penuh tampaknya diperlukan.

Sejauh membandingkan dengan kemungkinan lain, telah diperdebatkan bahwa jumlah sumber daya eksponensial untuk QRAM harus dibandingkan dengan arsitektur paralel klasik dengan jumlah prosesor yang eksponensial. Algoritma kuantum tidak tampak hebat dengan perbandingan ini. Seperti yang dijelaskan di sini , beberapa algoritma yang kami harapkan mempercepat kuantum sebenarnya lebih lambat ketika paralelisme ini diperhitungkan.

Meskipun tidak secara umum dalam cakupan, proposal lain untuk menempatkan data klasik ke dalam superposisi juga diusulkan di sini dan karenanya layak disebutkan.

James Wootton
sumber