Pytania otagowane jako complexity-theory

Na pytania dotyczące analizy złożoności algorytmów kwantowych i porównań ze złożonością algorytmów klasycznych.

2
Dobry materiał wprowadzający na temat kwantowych klas złożoności obliczeniowej
Chciałbym dowiedzieć się więcej o klasach złożoności obliczeniowej w kontekście obliczeń kwantowych. Medium nie jest tak ważne; może to być książka, notatki z wykładów online lub tym podobne. Najważniejsza jest zawartość. Materiał powinien obejmować podstawy kwantowych klas złożoności obliczeniowej i omawiać podobieństwa, różnice i relacje między nimi, a być może …
1
Algorytm kwantowy dla liczby Boga
Numer Boga jest najgorszym przypadku algorytmu Boga , który jest koncepcja wywodząca się z dyskusji na temat sposobów rozwiązania zagadki Kostka Rubika, ale która może być również zastosowana w innych łamigłówkach kombinacyjnych i grach matematycznych. Odnosi się do dowolnego algorytmu, który wytwarza rozwiązanie o możliwie najmniejszej liczbie ruchów, przy czym …
2
Czy BQP to tylko czas? Czy to ma sens?
Wydaje się, że klasa złożoności BQP (kwantowy wielomian czasowy z ograniczonym błędem) jest zdefiniowana tylko biorąc pod uwagę czynnik czasu. Czy to zawsze ma znaczenie? Czy istnieją algorytmy, w których obliczeniowy czas skaluje się wielomianowo z rozmiarem wejściowym, ale inne zasoby, takie jak pamięć skalowane wykładniczo?
1
Czego możemy się nauczyć z „kwantowego bogosortu”?
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 …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.