Jaki jest obecny stan algorytmów sortowania kwantowego?

W wyniku doskonałej odpowiedzi na moje pytanie dotyczące bogosortu kwantowego zastanawiałem się, jaki jest obecny stan techniki w algorytmach kwantowych do sortowania.

Mówiąc ściślej, sortowanie definiuje się tutaj jako następujący problem:

Biorąc pod uwagę tablicę liczb całkowitych (możesz swobodnie wybrać swoją reprezentację , ale bądź jasne, myślę, że to już nie jest trywialne!) O rozmiarze , chcemy przekształcić tę tablicę w tablicę tak, aby tablice to wzajemne przetasowania, a jest posortowane, tzn. dla wszystkich .$A$$A$$n$$A_s$$A_s$$A_s[i]\leq A_s[j]$$i\leq j$

Co o tym wiadomo? Czy istnieją ograniczenia lub domniemania złożoności dla niektórych modeli? Czy są praktyczne algorytmy? Możemy pokonać klasycznego sortowania (nawet wiadro lub radix sort w ich własnej grze ? (Czyli w przypadkach, w których pracują dobrze?))

W przypadku sortowania opartego na porównaniu (i wyszukiwania) granice wydają się pasować do granic klasycznych komputerów: do sortowania i do wyszukiwania, jak pokazują Hoyer i in. Kilka kwantowych algorytmów sortujących wymieniono w sekcji „Powiązana praca” „Algorytmu sortowania kwantowego opartego na kubitach splątania {00, 11}” .$\Omega(N\log N)$$\Omega(\log N)$

Nowszy wynik uzyskali Robert Beals, Stephen Brierley, Oliver Gray, Aram Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather. Przedstawiono je w Tabeli 2 wydajnego obliczania rozproszonego obliczania wyników dla sortowania bąbelkowego i sortowania wstawiającego, głównie dla „sortowania sieciowego”, ale podali więcej odniesień na temat sortowania.

Krótki i bardzo krótki opis artykułu może być następujący: możemy powiedzieć, że artykuł pokazuje, jak rozwiązać kilka problemów, takich jak dostęp do pamięci kwantowej bez utraty superpozycji (i to one kosztują). Ponadto w artykule przedstawiono problem sortowania sieci pod względem ilościowym (jednym z problemów jest odwracalność operacji). Podoba mi się ten artykuł, ponieważ rodzi kilka problemów, a autorzy podali rozwiązanie niektórych problemów. Myślę, że trudno jest streścić, naprawdę polecam przeczytać.

Mam nadzieję, że pomogłem.