Jaki jest obecny stan algorytmów sortowania kwantowego?

13

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 .AAnAsAsAs[i]As[j]ij

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?))

Dyskretna jaszczurka
źródło

Odpowiedzi:

6

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.

Gustavo Banegas
źródło