Bagaimana keadaan terkini dalam algoritma pengurutan kuantum?

Sebagai hasil dari jawaban yang bagus untuk pertanyaan saya tentang bogosort kuantum , saya bertanya-tanya bagaimana keadaan terkini dalam algoritma kuantum untuk pengurutan.

Lebih tepatnya, penyortiran di sini didefinisikan sebagai masalah berikut:

Diberikan array $A$ dari bilangan bulat (jangan ragu untuk memilih representasi $A$ , tetapi jelas tentang ini, saya pikir ini sudah non-sepele!) Dari ukuran $n$ , kami ingin mengubah array ini menjadi array $A_s$ sedemikian rupa sehingga array 'adalah reshufflings dari masing-masing yang lain dan $A_s$ diurutkan, yaitu $A_s[i]\leq A_s[j]$ untuk semua $i\leq j$ .

Apa yang diketahui tentang ini? Apakah ada batasan kompleksitas atau dugaan untuk model tertentu? Apakah ada algoritma praktis ? Bisakah kita mengalahkan sortasi klasik (bahkan bucket atau radix sort di game mereka sendiri ? (Yaitu dalam kasus di mana mereka bekerja dengan baik?))

$\Omega(N\log N)$$\Omega(\log N)$

Ada hasil yang lebih baru dari Robert Beals, Stephen Brierley, Oliver Gray, Aram Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather. Mereka hadir pada Tabel 2 dari Quantum Terdistribusi Efisien Komputasi hasil untuk jenis gelembung dan jenis penyisipan, terutama untuk "penyortiran jaringan" tetapi mereka memberikan lebih banyak referensi tentang penyortiran.

Deskripsi yang cepat dan sangat singkat dari makalah ini adalah: Kita dapat mengatakan bahwa makalah tersebut menunjukkan bagaimana menyelesaikan beberapa masalah seperti mengakses memori kuantum tanpa kehilangan superposisi (dan mereka memberikan biaya untuk itu). Juga, makalah ini menyajikan masalah penyortiran jaringan melakukannya secara kuantitatif (salah satu masalahnya adalah reversibilitas operasi). Saya suka kertas karena menimbulkan beberapa masalah dan penulis memberikan solusi untuk beberapa masalah. Saya pikir sulit untuk merangkum, saya sangat merekomendasikan untuk membaca.

Saya harap saya telah membantu.