Jakie algorytmy są szybsze z komputerem kwantowym?

Jestem początkującym studentem CS i uczę się algorytmów. Słyszałem, że nawet w przypadku komputerów kwantowych ogólne algorytmy sortowania nigdy nie mogą mieć czasu lepszego niż . Wiem jednak również, że algorytmy faktoringowe byłyby znacznie szybsze. Ogólnie, jakie algorytmy stałyby się znacznie szybsze przy komputerach kwantowych?$n\log n$

• Algorytm Shora, który umieszcza FACTORING w BQP ( ograniczonym czasie kwantowym wielomianu czasowym , w rzeczywistości kwantowym ekwiwalencie P) może być również użyty do rozwiązania problemu DYSKRETNEGO LOGARITHM , w którym chcemy znaleźć liczbę całkowitą taką, że gdzie podano i , w (kwantowym) czasie wielomianowym. Problem DISCRETE LOGARITHM ma taki sam status jak problem FACTORING, ponieważ nie wiemy, czy można je rozwiązać w czasie wielomianowym, więc może nie być to przyspieszenie.$k$$a^{k} = b$$a$$b$
• Algorytm Grovera przyspiesza kwadratowo w wyszukiwaniu nieposortowanych list (które można wykorzystać jako przyspieszenie dla wielu algorytmów).
• Symulowanie układów kwantowych odbywa się również w BQP, ale wykładniczo wolniej na klasycznej TM.
• Rozwiązanie równania Pell (a nie jednego) jest w BQP, innym przyspieszeniu wykładniczym.
• Istnieje również wiele innych, bardziej niejasnych problemów, które występują w BQP, ale wydaje się, że nie występują u P. Wocjana, a Zhang daje dobry punkt wyjścia do ich wykopania.