Ostatnio czytałem o „kwantowym bogosortie” na niektórych wiki. Podstawową ideą jest to, że podobnie jak bogosort, po prostu tasujemy naszą tablicę i mamy nadzieję, że zostanie ona posortowana „przypadkowo” i ponowna próba awarii.

Różnica polega na tym, że teraz mamy „ magiczny kwant”, więc możemy po prostu wypróbować wszystkie permutacje na raz w „równoległych wszechświatach” i „zniszczyć wszystkie złe wszechświaty” tam, gdzie ten rodzaj jest zły.

To oczywiście nie działa. Kwant to fizyka, a nie magia. Główne problemy to

1. „Równoległe wszechświaty” są jedynie interpretacją efektów kwantowych, a nie czymś, co wykorzystuje przetwarzanie kwantowe. Chodzi mi o to, że moglibyśmy użyć tutaj twardych liczb, myślę, że interpretacja tylko myli tutaj sprawy.

2. „Niszczenie wszystkich złych wszechświatów” przypomina korekcję błędów kubitowych, bardzo trudny problem w obliczeniach kwantowych.

3. Bogo sort pozostaje głupi. Jeśli możemy przyspieszyć sortowanie przez kwant, dlaczego nie oprzeć go na dobrym algorytmie sortowania ? (Ale potrzebujemy losowości, protestuje mój sąsiad! Tak, ale czy nie możesz wymyślić lepszego klasycznego algorytmu, który opiera się na losowości ?)

Chociaż ten algorytm jest głównie żartem, może być żartem edukacyjnym, takim jak „klasyczny” bogosort, ponieważ różnica między najlepszym przypadkiem, najgorszym przypadkiem i średnią złożonością przypadku dla algorytmów losowych jest tutaj łatwa i bardzo wyraźna. (dla przypomnienia, najlepszym przypadkiem jest$\Theta(n)$, mamy wielkie szczęście, ale wciąż musimy sprawdzić, czy nasza odpowiedź jest poprawna, skanując tablicę, oczekiwany czas jest po prostu okropny (IIRC, proporcjonalny do liczby permutacji, więc$O(n!)$), a najgorsze jest to, że nigdy nie skończymy)

Czego więc możemy się nauczyć z „kwantowego bogosortu”? W szczególności, czy istnieją prawdziwe algorytmy kwantowe, które są podobne, czy jest to teoretyczna lub praktyczna niemożliwość? Ponadto, czy przeprowadzono badania nad „algorytmami sortowania kwantowego”? Jeśli nie to dlaczego?

ZASTRZEŻENIE: Kwantowy bogosort jest algorytmem żartów

Pozwólcie, że pokrótce przedstawię algorytm:

• Krok 1: Korzystając z algorytmu kwantowej randomizacji, randomizuj listę / tablicę, tak aby nie można było ustalić, w jakiej kolejności jest lista, dopóki nie zostanie zaobserwowana. To podzieli wszechświat$O(N!)$wszechświaty; jednak podział nie wiąże się z żadnymi kosztami, ponieważ i tak dzieje się stale.

• Krok 2: Sprawdź, czy lista jest posortowana. Jeśli nie, zniszcz wszechświat (zaniedbując rzeczywistą fizyczną możliwość).

Teraz wszystkie pozostałe wszechświaty zawierają sortowane listy / tablice.

Najgorsza złożoność przypadku :$O(N)$

(rozważamy tylko te wszechświaty, które mogą zaobserwować, że lista jest posortowana)

Średnia / najlepsza złożoność przypadku :$O(1)$

Jednym z głównych problemów związanych z tego algorytmu jest ogromna możliwość powiększenia błędów jak wspomina Nick Johnson tutaj :

Ten algorytm ma jednak znacznie większy problem. Załóżmy, że raz na 10 miliardów razy omyłkowo dojdziesz do wniosku, że lista jest posortowana, gdy nie jest. Jest 20! sposoby sortowania listy 20 elementów. Po sortowaniu pozostałe wszechświaty będą tymi, w których lista została poprawnie posortowana, a 2,4 miliona wszechświatów, w których algorytm błędnie stwierdził, że lista została poprawnie posortowana. To, co tu masz, to algorytm do masowego powiększania poziomu błędu maszyny.

„Równoległe wszechświaty” to bardzo uproszczona interpretacja efektów kwantowych , a nie coś, co wykorzystuje Quantum Computing.

Nie bardzo wiem, co rozumiesz przez „bardzo uproszczoną interpretację efektów kwantowych”. Źródła ( to i to ), które znalazłem w Internecie na temat bogosortu kwantowego , nie wspominają wprost, że używają alternatywnej interpretacji QM, tj . Interpretacji Everetta, o której być może myślisz. W rzeczywistości nie jestem nawet pewien, jak skleić interpretację Everetta i bogosort kwantowy (używając selekcji końcowej, jak niektórzy komentowali). W każdym razie, tylko dla przypomnienia: w kosmologii głównego nurtu powszechnie uważa się, że istnieje więcej niż jeden wszechświat i istnieją nawet dla nich klasyfikacje, zwane czterema poziomami Maxa Tegmarka i Brianem Greene'em.Teorie cykliczne . Przeczytaj artykuł Wiki na temat Multiverse, aby uzyskać więcej informacji.

„Niszczenie wszystkich złych wszechświatów” przypomina korekcję błędów kubitowych, bardzo trudny problem w obliczeniach kwantowych.

Jasne, w rzeczywistości jest o wiele trudniej i nie oczekujemy dosłownie niszczenia wszechświatów. Bogosort kwantowy jest tylko koncepcją teoretyczną, bez praktycznych zastosowań (o których wiem).

Bogo sort pozostaje głupi. Jeśli możemy przyspieszyć sortowanie przez kwant, dlaczego nie oprzeć go na dobrym algorytmie sortowania? (Ale potrzebujemy losowości, protestuje mój sąsiad! Tak, ale czy nie możesz wymyślić lepszego klasycznego algorytmu, który opiera się na losowości?)

Tak, to jest głupie . Wygląda na to, że zaczął się od „żartu edukacyjnego”, jak pan powiedział. Próbowałem znaleźć pochodzenie tego rodzaju lub odpowiednie artykuły akademickie, ale nie znalazłem żadnego. Jednak nawet klasyczny bogosort jest głupi w tym sensie, że jest powszechnie uważany za jeden z najbardziej nieefektywnych algorytmów sortowania. Nadal był badany, wyłącznie w celach edukacyjnych.

W szczególności, czy istnieją prawdziwe algorytmy kwantowe, które są podobne, czy jest to teoretyczna lub praktyczna niemożliwość?

Brak, o którym wiem. Takie algorytmy są rzeczywiście teoretycznymi możliwościami, ale zdecydowanie niepraktycznymi (przynajmniej jeszcze nie).

Ponadto, czy przeprowadzono badania nad „algorytmami sortowania kwantowego”? Jeśli nie to dlaczego?

Rzeczywiście przeprowadzono badania nad „sortowaniem kwantowym”. Problem z takimi algorytmami sortowania polega jednak na tym, że dowolny algorytm sortowania kwantowego oparty na porównaniu zająłby co najmniej$\Omega (N\log N)$kroki, które są już osiągalne za pomocą klasycznych algorytmów. Zatem do tego zadania komputery kwantowe nie są lepsze od klasycznych. Jednak w rodzajach ograniczonych przestrzenią algorytmy kwantowe przewyższają swoje klasyczne odpowiedniki. To i to są dwa odpowiednie dokumenty.