Czy algorytm Shora kończy poszukiwania algorytmów faktoringowych w kwantowym świecie obliczeń?

Innymi słowy, czy badania faktoringowe pozostaną wyłącznie w klasycznym świecie, czy prowadzone są interesujące badania w świecie kwantowym związane z faktoringiem?

Asymptotycznie algorytm Shora jest naprawdę wydajny. Zasadniczo jest to po prostu: superpozycja, modułowe potęgowanie (najwolniejszy krok) i transformata Fouriera. Modułowe potęgowanie jest tym, co robisz, aby faktycznie korzystać z kryptosystemu RSA. Oznacza to, że dla komputera kwantowego szyfrowanie / deszyfrowanie RSA byłoby zgodne z tą samą prędkością, co użycie algorytmu Shora do złamania systemu. Jestem więc sceptycznie nastawiony do wprowadzenia ulepszeń w podstawowej idei.

To powiedziawszy, wszelkie ulepszenia dodawania liczb całkowitych, mnożenia liczb całkowitych lub kwantowej transformacji Fouriera poprawiłyby algorytm Shora, a wszystkie te są bardzo ogólnymi podprogramami, nad którymi ludzie prawie na pewno będą pracować. Krótkie wyszukiwanie w Google Scholar pokazuje wiele badań nad poprawą kwantowych obwodów arytmetycznych.

Myślę, że w algorytmie Shora będzie więcej badań nad kompromisami klasycznymi / kwantowymi. Oznacza to, że jeśli masz mały lub hałaśliwy komputer kwantowy, czy możesz zmodyfikować algorytm Shora, aby nadal działał, ale może potrzebuje znacznie więcej wstępnego i końcowego przetwarzania na klasycznym komputerze, a może ma mniejsze prawdopodobieństwo sukcesu, itp.? W tym obszarze znajdują się algorytmy kwantowe do obliczania krótkich dyskretnych logarytmów i faktorowania liczb całkowitych RSA . Jest też sito polowe z liczbą kwantową, podejście, w którym „mały” komputer kwantowy (zbyt mały, aby używać algorytmu Shora bezpośrednio) jest stosowany jako podprogram klasycznego sita pola liczbowego, nieznacznie poprawiając złożoność czasu (chociaż osobiście jestem przekonany, że korekcja błędów w tym celu będzie wymagać więcej kubity fizyczne niż algorytm waniliowy Shora).

Krótko mówiąc, nie oczekuję żadnych radykalnych nowych algorytmów faktoringu kwantowego i nie sądzę, aby ktokolwiek nad tym pracował. Ale jest wiele ciekawych poprawek, aby dopasować je do konkretnych przypadków użycia.

Jako dodatek do odpowiedzi Sama:

Nie, częściowo dlatego, że podejście Shora nie jest jedynym sposobem na faktoryzację liczb.

Faktoryzację można również zapisać jako problem optymalizacji .

Można to rozwiązać za pomocą maszyny D-Wave , ale także za pomocą bramkowego komputera kwantowego .

Dla przypomnienia algorytm Shora jest zaimplementowany w bramkowym modelu obliczeniowym.

$(N-xy)^2$$x$$y$$N$

Czas działania algorytmu adiabatycznego jest, jak rozumiem, bardzo zmienny, aby go określić, ponieważ opiera się na właściwościach spektralnych problemu hamiltonianu.

Chociaż symulacje numeryczne czasem wyglądały zachęcająco, uważam, że wciąż pozostaje otwarte pytanie, czy algorytm faktoringu adiabatycznego rzeczywiście zapewnia wykładnicze przyspieszenie w porównaniu z faktoringiem klasycznym.

Zobacz więcej szczegółów w tym artykule Peng, Liao, Xu, Gan Qin, Zhou, Suter i Du - ich RYS. 3 symulacje czasu wykonywania sugerują kwadratowe dopasowanie; jednak; Nie jestem pewien, czy miały miejsce dalsze badania w celu udowodnienia takiego dopasowania lub dostarczenia więcej dowodów nawet na wielomianowy czas wykonywania.