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

10

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?

R. Chopin
źródło
1
znajomość jednego algorytmu w celu skutecznego rozwiązania problemu nie oznacza, że ​​nie można znaleźć innych algorytmów, które byłyby lepsze (ogólnie lub w konkretnych okolicznościach)
glS
2
Pytasz, czy algorytm Shora okazał się optymalny, czy pytasz, czy badania klasycznych algorytmów faktoringowych są nadal przydatne?
ahelwer
Pytam o to drugie. Jestem pewien, że poszukiwania będą kontynuowane w klasycznym świecie, ponieważ nikt nie wie, czy istnieje szybkie rozwiązanie, ale co z obliczeniami kwantowymi? Czy wszyscy są zadowoleni z algorytmu Shora do tego stopnia, że ​​przechodzą na inne pola?
R. Chopin
1
Myślę, że masz na myśli „czy badania faktoringowe pozostaną wyłącznie w klasycznym świecie ...”
Mark S

Odpowiedzi:

7

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.

Sam Jaques
źródło
1
Uważam, że post-kwantowa RSA będzie interesującą lekturą. Bardzo dziękuję za interesujące odniesienia dodane w odpowiedzi.
R. Chopin
2

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 .

Nippon
źródło
1

Dla przypomnienia algorytm Shora jest zaimplementowany w bramkowym modelu obliczeniowym.

(N.-xy)2)xyN.

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.

Znaki
źródło